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 wN should be satisfy wN=wN-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?
Xi'an's Og 
July 29, 2014 at 1:45 am
[…] So, there is to be a better solutions. After writing my little code I looked at Xi’an solution since he did this puzzle, and he used a sampling over a million solution that make way more sens […]
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!