## Le Monde puzzle [#865]

**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 minutes of 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. (And, as Jean-Louis Fouley commented, it does not even work for N=6.) Monte Carlo effect or true discrepancy?

May 6, 2014 at 10:48 pm

I have a slight discrepancy through the first 10 numbers. For n = 9, I have W = 30 using {6,1,5,9,7,2,8,3,4}. For n = 11, W is 51 using {4,9,11,6,10,7,8,2,1,3,5}.

If we say D is the W(n)-W(n-1) and U is the number of unique solutions, we get

n W D U

1 0 – 1

2 1 1 1

3 2 1 2

4 4 2 1

5 7 3 1

6 10 3 5

7 16 6 2

8 22 6 1

9 30 8 1

10 38 8 1

11 51 13 1

It’s interesting to consider the probability of happening upon the correct solution given that you are simulating a million random permutations. For instance, since there is only 1 unique solution out of the 39,916,800 permutations at n = 11, the probability of getting this one combination by chance is 2.47%, which is a considerable drop from the 24.1% chance at n = 10 and the 93.6% chance at n = 9. It would seem that the probability of getting the correct answer for n = 2014 through simulation would be astronomical even for several orders of magnitude the number of simulations, so there has to be a better way.

The online encyclopedia of integer sequences (http://oeis.org/A000376) gives W for n up to 20 as 0, 1, 2, 4, 7, 10, 16, 22, 30, 38, 51, 63, 80, 101, 112, 130, 159, 191, 207, 231.

Fitting a line based on the model W = a*n^b + c to these 20 points gives estimates of a = 0.136, b = 2.50, and c = -1.03. Extrapolating to n = 2014 gives an estimate of just over 25 million for W. No idea how close that might be though.

May 6, 2014 at 10:56 pm

Slight typo: it should be a = 0.132, leading to an estimate of between 24 and 25 million.

May 6, 2014 at 11:51 pm

You are absolutely right: W=30 for n=9. I just checked it using more simulations than previously. Today, E Busser & G Cohen in their reply in “Le Monde” do not provide any figure for W of n>5 and especially for W(2014).

May 8, 2014 at 10:37 pm

Jean-Louis, would you have the text of the new puzzle? I am in England and cannot buy Le Monde on the Warwick campus…

May 6, 2014 at 2:55 am

[…] article was first published on Xi'an's Og » R, and kindly contributed to […]

May 9, 2014 at 10:29 am

No problem. I am sending you the text of Game No 866 in the mail. In summary, here it is:

Givens of the problem: A,B,C, D stand for Alice, Bob, Charlotte and Daniel’s house locations.

angle(ACB)=2 angle(ABC); DC=DB and AC=AD

Question: What about the relationship between angle(BAD) and angle(CAD) ?

This is an elementary problem of Greek geometry which should not present much difficulty.

May 6, 2014 at 2:02 am

A colleague of mine, André Neau suggested to me the same recurrence formula as yours W(n)=W(n-1)+n-2 which looks fine at first glance and can be integrated as W(n)=(n(n-3)/2)+2. Unfortunately it does not work for n=6 having W(6)=10 instead of 11 as predicted.

Let m be the first digit in the k step ie S(n,k)=m, by construction this digit is in the m th position at the next step S(k+1,m)=m. Using that property, one can proceed backwards as in the coalescence theory of population genetics, from the final stage to the starting one as shown below for n=5

K 1 2 3 4 5

K-1 2 1 3 4 5

K-2 3 1 2 4 5

K-3 4 2 1 3 5

K-4 2 4 1 3 5

K-5 5 3 1 4 2

K-6 4 1 3 5 2

K-7 3 1 4 5 2

However, this algorithm leads also to some difficulties when there are several possible choices for numbers in the right positions. Finally using both simulation and exhaustive testing of all possible permutations, I found the following solutions.

n 1 2 3 4 5 6 7 8 9 10

W 0 1 2 4 7 10 16 22 29 38

Using simulation on 300000 permutations I went not so far from you to W=21675 for n=2014 but far below 2 025 079 predicted by the previous formula.

May 6, 2014 at 6:34 am

Thank you for the immediate “strike”, Jean=Louis!