Le Monde puzzle [#817]

April 18, 2013

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

The weekly Le Monde puzzle is (again) a permutation problem that can be rephrased as follows:


\min_{\sigma\in\mathfrak{S}_{10}} \max_{0\le i\le 10}\ \sigma_i+\sigma_{i+1}

where \mathfrak{S}_{10} denotes the set of permutations on {0,…,10} and \sigma_i is defined modulo 11 [to turn {0,…,10} into a torus]. Same question for

\min_{\sigma\in\mathfrak{S}_{10}} \max_{0\le i\le 10}\ \sigma_i+\sigma_{i+1}+\sigma_{i+2}

and for

\min_{\sigma\in\mathfrak{S}_{10}} \max_{0\le i\le 10}\ \sigma_i+\cdots+\sigma_{i+5}

This is rather straightforward to code if one adopts a brute-force approach::


  for (t in 1:T){
    for (j in 1:3)
     if (sums[j]

(where I imposed the first term to be zero because of the invariance by permutation), getting the solutions

> perminmax(10^5)
[1] 11 17 28
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,]    0   10    1    6    5    4    7    3    8     2     9
[2,]    0   10    4    3    5    1    9    6    2     8     7
[3,]    0    2    9    6    7    3    1    4   10     8     5

for 2, 3, and 5 terms.  (Since 10! is a mere 3.6 million, I checked with an exhaustive search, using the function permutation from the gtools package.)

Filed under: Books, Kids, R Tagged: gtools, Le Monde, mathematical puzzle, permutations, R

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

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, 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...

Comments are closed.

Search R-bloggers


Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)