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!lemonde865A 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?

lemonde865b

9 Responses to “Le Monde puzzle [#865]”

  1. […] 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 […]

  2. Sam Dickson Says:

    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.

    • Sam Dickson Says:

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

    • Jean Louis FOULLEY Says:

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

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

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

    • Jean Louis FOULLEY Says:

      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.

  4. Jean Louis FOULLEY Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 717 other followers