Le Monde puzzle [#28]

July 22, 2011
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

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 bubble sort 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(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.


Filed under: R Tagged: mathematical puzzle, R, rank

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.