## Le Monde puzzle [#887] A simple combinatorics Le Monde mathematical puzzle:

N is a golden number if the sequence {1,2,…,N} can be reordered so that the sum of any consecutive pair is a perfect square. What are the golden numbers between 1 and 25?

Indeed, from an R programming point of view, all I have to do is to go over all possible permutations of {1,2,..,N} until one works or until I have exhausted all possible permutations for a given N. However, 25!=10²⁵ is a wee bit too large… Instead, I resorted once again to brute force simulation, by first introducing possible neighbours of the integers

```  perfect=(1:trunc(sqrt(2*N)))^2
friends=NULL
le=1:N
for (perm in 1:N){
amis=perfect[perfect>perm]-perm
amis=amis[amis<N]
le[perm]=length(amis)
friends=c(friends,list(amis))
}
```

and then proceeding to construct the permutation one integer at time by picking from its remaining potential neighbours until there is none left or the sequence is complete

```orderin=0*(1:N)
t=1
orderin=sample((1:N),1)
for (perm in 1:N){
friends[[perm]]=friends[[perm]]
[friends[[perm]]!=orderin]
le[perm]=length(friends[[perm]])
}
while (t<N){
if (length(friends[[orderin[t]]])==0)
break()
if (length(friends[[orderin[t]]])>1){
orderin[t+1]=sample(friends[[orderin[t]]],1)}else{
orderin[t+1]=friends[[orderin[t]]]
}
for (perm in 1:N){
friends[[perm]]=friends[[perm]]
[friends[[perm]]!=orderin[t+1]]
le[perm]=length(friends[[perm]])
}
t=t+1}
```

and then repeating this attempt until a full sequence is produced or a certain number of failed attempts has been reached. I gained in efficiency by proposing a second completion on the left of the first integer once a break occurs:

```while (t<N){
if (length(friends[[orderin]])==0)
break()
orderin[2:(t+1)]=orderin[1:t]
if (length(friends[[orderin]])>1){
orderin=sample(friends[[orderin]],1)}else{
orderin=friends[[orderin]]
}
for (perm in 1:N){
friends[[perm]]=friends[[perm]]
[friends[[perm]]!=orderin]
le[perm]=length(friends[[perm]])
}
t=t+1}
```

(An alternative would have been to complete left and right by squared numbers taken at random…) The result of running this program showed there exist permutations with the above property for N=15,16,17,23,25,26,…,77.  Here is the solution for N=49:

25 39 10 26 38 43 21 4 32 49 15 34 30 6 3 22 42 7 9 27 37 12 13 23 41 40 24 1 8 28 36 45 19 17 47 2 14 11 5 44 20 29 35 46 18 31 33 16 48

As an aside, the authors of Le Monde puzzle pretended (in Tuesday, Nov. 12, edition) that there was no solution for N=23, while this sequence

22 3 1 8 17 19 6 10 15 21 4 12 13 23 2 14 11 5 20 16 9 7 18

sounds fine enough to me… I more generally wonder at the general principle behind the existence of such sequences. It sounds quite probable that they exist for N>24. (The published solution does not bring any light on this issue, so I assume the authors have no mathematical analysis to provide.)

### 5 Responses to “Le Monde puzzle [#887]”

1. I didn’t get the idea of the line

perfect=(1:trunc(sqrt(2*N)))^2

Can you explain it?

• xi'an Says:

These are the perfect squares between 1 and 2N. If I consider integers between 1 and N, their sum is at most 2N-1, so I do not need to consider perfect squares larger than that.

2. xi'an Says:

Just found a solution for N=99 (took about one hour on my laptop):
 57 64 80 41 59 62 19 81 40 60 84 37 63 18 31 69 12 88 56 25 75 6 58 23 98
 2 34 30 51 49 72 97 24 1 35 46 54 90 10 26 95 5 44 20 61 3 22 99 70 74
 47 17 8 28 21 43 38 83 86 14 67 77 92 52 48 33 16 9 55 45 36 85 15 66 78
 91 53 11 89 32 4 96 73 27 94 50 71 29 7 93 76 68 13 87 82 39 42 79 65

• John Says:

I think it’s better to use graph theory to solve this.

• xi'an Says:

Please send me your solution and I will publish it as a guest post!

This site uses Akismet to reduce spam. Learn how your comment data is processed.