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