**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 w_{N} should be satisfy w_{N}=w_{N-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

*Related*

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...