Le Monde puzzle [#887bis]
As mentioned in the previous post, an alternative consists in finding the permutation of {1,…,N} by “adding” squares left and right until the permutation is complete or no solution is available. While this sounds like the dual of the initial solution, it brings a considerable improvement in computing time, as shown below. I thus redefined the construction of the solution by initialising the permutation at random (it could start at 1 just as well)
perfect=(1:trunc(sqrt(2*N)))^2 perm=friends=(1:N) t=1 perm[t]=sample(friends,1) friends=friends[friends!=perm[t]]
and then completing only with possible neighbours, left
out=outer(perfectperm[t],friends,"==") if (max(out)==1){ t=t+1 perm[t]=sample(rep(perfect[apply(out,1, max)==1],2),1)perm[t1] friends=friends[friends!=perm[t]]}
or right
out=outer(perfectperm[1],friends,"==") if (max(out)==1){ t=t+1 perf=sample(rep(perfect[apply(out,1, max)==1],2),1)perm[1] perm[1:t]=c(perf,perm[1:(t1)]) friends=friends[friends!=perf]}
(If you wonder about why the rep in the sample step, it is a trick I just found to avoid the insufferable feature that sample(n,1) is equivalent to sample(1:n,1)! It costs basically nothing but bypasses reprogramming sample() each time I use it… I am very glad I found this trick!) The gain in computing time is amazing:
> system.time(for (i in 1:50) pick(15)) utilisateur système écoulé 5.397 0.000 5.395 > system.time(for (i in 1:50) puck(15)) utilisateur système écoulé 0.285 0.000 0.287
An unrelated point is that a more interesting (?) alternative problem consists in adding a toroidal constraint, namely to have the first and the last entries in the permutation to also sum up to a perfect square. Is it at all possible?
November 20, 2014 at 11:48 pm
In case you are interested: Here is the first ‘toroidal’, as you call it, or Hamiltonian cycle for N = 32 (the smallest possible case):
21, 28, 8, 1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29,
7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4
where 21 + 4 is also a (perfect) square.
The possibility of such cycles grows with N, but I admit I cannot see any direct connection of numbertheoretic properties of N.
November 20, 2014 at 1:34 am
This question appears best to be expressed as a graphtheoretical problem. Then no combinations have to be generated and the combinatorial explosion is somewhat avoided.
Take the set {1, …, N} as the set of nodes of a graph. Tho nodes n, m are connected by an edge iff n+m is a (perfect) square. You can draw this graph for N = 15 within a minute or so:
8

15 — 1 — 3 — 13 — 12 — 4 — 5 — 11 — 14 — 2 — 7 — 9
 
10 —— 6
to see there is only one admissible path through this graph touching all nodes (exaxctly) ones, and there is no “toroidal”, i.e. closed, path.
With R, it is easy to set up these graphs and to visualize a 2dim. layout applying, for instance, the ‘igraph’ package. This package also is able to efficiently find a Hamiltonian path, a path that meets each node exactly ones — even for huge values of N.
By the way, there are no such Hamiltonian cycles for N <= 30.
HW
November 20, 2014 at 7:22 am
Thanks Hans, for bringing an answer to my extra question. That there is no solution for N<31 is the most interesting thing. Now, two more posts using graphs on the original problem and written by guests are coming up this weekend. One relies on a travelling salesman optimiser and managed to get an answer for large values of N.