Le Monde puzzle [#28]

The puzzle of last weekend in Le Monde was about finding the absolute rank of x₉ when given the relative ranks of x₁,….,x₈ and the possibility to ask for relative ranks of three numbers at a time. In R terms, this means being able to use

> rank(x[-9])
[1] 1 7 4 6 8 3 2 5
> rank(x[1:3])
[1] 1 3 2

or yet being able to sort the first 8 components of x

> x[-9]=sort(x[-9])
> rank(x[c(1,8,9)])
[1] 1 3 2

and then use rank() over triplets to position x₉ in the list. If x₉ is an extreme value, calling for its rank relative to x₁ and x₈  is sufficient to find its position. Else repeating with the rank relative to x₂ and x₇, then relative to x₃ and x₆  , etc., produces the absolute rank of x₉ in at most 4 steps. However, if we first get the rank relative to x₁ and x₈,  then the rank relative to x₄ and x₅, we only need at most an extra step to find the absolute rank of x₉ in thus at most 3 steps. Yet however, if we start with the rank relative to x₃ and x₆, we are left with a single rank call to determine the absolute rank of x₉ since, whatever the position of x₉ relative to x₃ and x₆, there are only two remaining numbers to compare x₉ with. So we can find the absolute rank of x₉ in exactly two calls to rank.

The second part of the puzzle is to determine for an unknown series x of 80 numbers the maximum number of calls to rank(c(x₁,x₂,x₃)) to obtain rank(x). Of course, the dumb solution is to check all 82160 triplets, but I presume a sort of bubble sort would do better, even though Wikipedia tells me that bubble sort has worst-case and average complexity both О(n²), while quicksort has an average (if not worse-case) O(nlogn) complexity…. If we follow the one-step procedure obtained in the first part, starting with three numbers whose relative rank is obtained with one call, we need in toto

1 + (9-3)*2 + ((1+3*8+2)-9)*3+(80-27)*4 =279

calls to rank since 80<1+3*(3*8+2)+2=81.