Le Monde puzzle [#865]
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
A Le Monde mathematical puzzle in combinatorics:
Given a permutation σ of {1,…,5}, if σ(1)=n, the n first values of σ are inverted. If the process is iterated until σ(1)=1, does this always happen and if so what is the maximal number of iterations? Solve the same question for the set {1,…,2014}.
I ran the following basic R code:
N=5 tm=0 for (i in 1:10^6){ sig=sample(1:N) #random permutation t=0;while (sig[1]>1){ n=sig[1] sig[1:n]=sig[n:1] t=t+1} tm=max(t,tm)}
obtaining 7 as the outcome. Here is the evolution of the maximum as a function of the number of terms in the set. If we push the regression to N=2014, the predicted value is around 600,000. .. Running a million simulations of the above only gets me to 23,871!A wee reflection lead me to conjecture that the maximum number of steps wN should be satisfy wN=wN-1+N-2. However, the values resulting from the simulations do not grow as fast. Monte Carlo effect or true discrepancy?
Filed under: Books, Kids, R Tagged: Le Monde, mathematical puzzle, R
![](https://i0.wp.com/stats.wordpress.com/b.gif?resize=1%2C1)
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.