Archive for bubblesort

Le Monde puzzle [#855]

Posted in Books, Kids, Statistics with tags , , , , , , on March 7, 2014 by xi'an

A Le Monde mathematical puzzle that reminds me of an earlier one:

Given ten tokens with different unknown weights, and a scale that can rank three tokens at a time, starting with ranking three tokens, what is the minimum number of actions necessary to rank the ten of them if (a) one token at a time is added, (b) one or two tokens are added? If no restriction is imposed on the token introduction, is there a more efficient strategy?

It indeed relates to earlier posts on sorting and ternary sorting. Checking further on StackOverflow I found this reply to a question about ternary sorting:

Average number of comparisons:

in ternary search = ((1/3)*1+(2/3)*2)*ln(n)/ln(3)~1.517*ln(n)
in binary search  =                 1*ln(n)/ln(2)~1.443*ln(n)

Worst number of comparisons:

in ternary search = 2*ln(n)/ln(3)~1.820*ln(n)
in binary search  = 1*ln(n)/ln(2)~1.443*ln(n)

albeit with no reference. So this somewhat answers part (c) of the question. (If asymptotically since this does not work for n=10! Even for n=100, it is way too large.) Looking for a solution to part (a), I looked at the performances of a dyadic sorting algorithm, partitioning recursively the already sorted part of the sample into three parts to locate each time the proper position of the new token. This led me to the following code



  if (locrk[3]==1) return(ifelse(i1>3,
  if (locrk[3]==2) return(ifelse(i2-i1>4,
  if (locrk[3]==3) return(ifelse(mag-i2>2,


for (ul in (4:length(toke))){




which produces a minimum of eight (of course!) and a maximum of 20 uses of the scale (based on 10⁶ random permutations of (1,…,10)). Unsurprisingly, the solution proposed in Le Monde the week after does better as it obtains 16 as the worst case figure. Repeating the experiment with n=100 values, the maximum was 303 (with a mean of 270 and a minimum of 240 ternary comparisons).

Moving to an insertion two tokens at a time, I tested a scheme where two new tokens were tested against the current median, then the median of one half, and so on until they split on both sides of this median. Here is the corresponding R code



if (locrk[1]==3) return(ifelse(i1>2,
if (locrk[1]==2) return(ifelse(mag>4,
if (locrk[1]==1) return(ifelse(mag-i1>2,



for (ul in -1+2*(3:(length(toke)/2))){



leading to a value of 13.

This Feb. 19 issue of Le Monde Science&Médecine leaflet also contains a two page report on growing psychological work-related issues like stress, burn-out and depression, in research labs, mostly connected with the increase in administrative duties and grant writing, duties most of us have not been trained for. There is also a short column by Etienne Gys telling about the short lived claim by Moukhtarbaï Otelbaev to have solved the Navier-Stokes problem. Until Terry Tao wrote a paper stating why the proof could not work.

Le Monde puzzle [#28]

Posted in R with tags , , , , on July 22, 2011 by xi'an

The puzzle of last weekend in Le Monde was about finding the absolute rank of x9 when given the relative ranks of x1,….,x8 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 x9 in the list. If x9 is an extreme value, calling for its rank relative to x1 and x8  is sufficient to find its position. Else repeating with the rank relative to x2 and x7, then relative to x3 and x6  , etc., produces the absolute rank of x9 in at most 4 steps. However, if we first get the rank relative to x1 and x8,  then the rank relative to x4 and x5, we only need at most an extra step to find the absolute rank of x9 in thus at most 3 steps. Yet however, if we start with the rank relative to x3 and x6, we are left with a single rank call to determine the absolute rank of x9 since, whatever the position of x9 relative to x3 and x6, there are only two remaining numbers to compare x9 with. So we can find the absolute rank of x9 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(x1,x2,x3)) to obtain rank(x). Of course, the dumb solution is to check all 82160 triplets, but I presume a sort of bubblesort would do better, even though Wikipedia tells me that bubble sort has worst-case and average complexity both О(n2), while quicksort has an average (if not worse-case) O(n log(n)) complexity…. If we follow the one-step procedure obtained in the first part to insert a new number, starting with three numbers whose relative rank is obtained with one  single 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. (This is also the solution proposed in Le Monde, however there is no proof inserting one number at a time is the optimal solution.)

%d bloggers like this: