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(perfect-perm[t],friends,"==")
if (max(out)==1){
  t=t+1
  perm[t]=sample(rep(perfect[apply(out,1,
   max)==1],2),1)-perm[t-1]
  friends=friends[friends!=perm[t]]}

or right

out=outer(perfect-perm[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:(t-1)])
  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?

3 Responses to “Le Monde puzzle [#887bis]”

  1. Hans Werner Says:

    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 number-theoretic properties of N.

  2. Hans Werner Says:

    This question appears best to be expressed as a graph-theoretical 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 2-dim. 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

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

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