Archive for mathematical puzzle

Le Monde puzzle [#887quater]

Posted in Books, Kids, R, Statistics, University life with tags , , on November 28, 2014 by xi'an

And yet another resolution of this combinatorics Le Monde mathematical puzzle: that puzzle puzzled many more people than usual! This solution is by Marco F, using a travelling salesman representation and existing TSP software.

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?

For instance, take n=199, you should first calculate the “friends”. Save them on a symmetric square matrix:

m1 <- matrix(Inf, nrow=199, ncol=199)
diag(m1) <- 0
for (i in 1:199) m1[i,friends[i]] <- 1

Export the distance matrix to a file (in TSPlib format):

library(TSP)
tsp <- TSP(m1)
tsp
image(tsp)
write_TSPLIB(tsp, "f199.TSPLIB")

And use a solver to obtain the results. The best solver for TSP is Concorde. There are online versions where you can submit jobs:

0 2 1000000
2 96 1000000
96 191 1000000
191 168 1000000
  ...

The numbers of the solution are in the second column (2, 96, 191, 168…). And they are 0-indexed, so you have to add 1 to them:

3  97 192 169 155 101 188 136 120  49 176 148 108 181 143 113 112  84  37  63 18  31  33  88168 193  96 160 129 127 162 199  90  79 177 147  78  22 122 167 194 130  39 157  99 190 13491 198  58  23  41 128 196  60  21 100 189 172 152 73 183 106  38 131 125 164 197  59 110 146178 111 145  80  20  61 135 121  75  6  94 195166 123 133 156  69  52 144  81  40   9  72 184  12  24  57  87  82 62  19  45  76 180 109 116 173 151  74  26  95 161 163 126  43 153 17154  27 117 139  30  70  11  89 107 118 138 186103  66 159 165 124 132  93  28   8  17  32  45  44  77 179 182 142  83  86  14  50 175 114 55 141 115  29  92 104 185  71  10  15  34   27  42 154 170 191  98 158  67 102 187 137 119 25  56 65  35  46 150 174  51  13  68  53  47 149 140  85  36  64 105  16  48

Le Monde puzzle [#887ter]

Posted in Books, Kids, Statistics, University life with tags , , , , on November 27, 2014 by xi'an

Here is a graph solution to the recent combinatorics Le Monde mathematical puzzle, proposed by John Shonder:

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?

Consider an undirected graph GN with N vertices labelled 1 through N. Draw an edge between vertices i and j if and only if i + j is a perfect square. Then N is golden if GN contains a Hamiltonian path — that is, if there is a connected path that visits all of the vertices exactly once.g25I wrote a program (using Mathematica, though I’m sure there must be an R library with similar functionality) that builds up G sequentially and checks at each step whether the graph contains a Hamiltonian path. The program starts with G1 — a single vertex and no edges. Then it adds vertex 2. G2 has no edges, so 2 isn’t golden.

Adding vertex 3, there is an edge between 1 and 3. But vertex 2 is unconnected, so we’re still not golden.

The results are identical to yours, but I imagine my program runs a bit faster. Mathematica contains a built-in function to test for the existence of a Hamiltonian path.

g36Some of the graphs are interesting. I include representations of G25 and G36. Note that G36 contains a Hamiltonian cycle, so you could arrange the integers 1 … 36 on a roulette wheel such that each consecutive pair adds to a perfect square.

A somewhat similar problem:

Call N a “leaden” number if the sequence {1,2, …, N} can be reordered so that the sum of any consecutive pair is a prime number. What are the leaden numbers between 1 and 100? What about an arrangement such that the absolute value of the difference between any two consecutive numbers is prime?

[The determination of the leaden numbers was discussed in a previous Le Monde puzzle post.]

Le Monde puzzle [#887bis]

Posted in Kids, R, Statistics, University life with tags , , on November 16, 2014 by xi'an

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?

Le Monde puzzle [#887]

Posted in Books, Kids, R, Statistics with tags , , , on November 15, 2014 by xi'an

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[1]=sample((1:N),1)
for (perm in 1:N){
  friends[[perm]]=friends[[perm]]
              [friends[[perm]]!=orderin[1]]
  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[1]]])==0)
        break()
  orderin[2:(t+1)]=orderin[1:t]
  if (length(friends[[orderin[2]]])>1){
    orderin[1]=sample(friends[[orderin[2]]],1)}else{
    orderin[1]=friends[[orderin[2]]]
    }
  for (perm in 1:N){
    friends[[perm]]=friends[[perm]]
       [friends[[perm]]!=orderin[1]]
    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.)

Le Monde puzzle [#882]

Posted in Books, Kids, Statistics, University life with tags , , on October 14, 2014 by xi'an

A terrific Le Monde mathematical puzzle:

All integers between 1 and n² are written in an (n,n)  matrix under the constraint that two consecutive integers are adjacent (i.e. 15 and 13 are two of the four neighbours of 14). What is the maximal value for the sum of the diagonal of this matrix?

Indeed, when considering a simulation resolution (for small values of m), it constitutes an example of self-avoiding random walk: when inserting the integers one by one at random, one produces a random walk over the (n,n) grid.

While the solution is trying to stick as much as possible to the diagonal vicinity for the descending sequence n²,n²-1, &tc., leaving space away from the diagonal for the terminal values, as in this example for n=5,

25 22 21 14 13
24 23 20 15 12
01 02 19 16 11
04 03 18 17 10
05 06 07 08 09

simulating such a random walk is a bit challenging as the brute force solution does not work extremely well: Continue reading

Le Monde puzzle [#879]

Posted in Books, Kids with tags , , on September 21, 2014 by xi'an

Here is the last week puzzle posted in Le Monde:

Given an alphabet with 26 symbols, is it possible to create 27 different three-symbol words such that

  1. all symbols within a word are different
  2. all triplets of symbols are different
  3. there is no pair of words with a single common symbol

Since there are

28x27x26/3×2=2925

such three-symbol words, it could be feasible to write an R code that builds the 27-uplet, assuming it exists. However, by breaking those words into primary words [that share no common symbols] and secondary words [that share two symbols with one primary word], it seems to me that there can be a maximum of 26 words under those three rules…

Le Monde puzzle [#875]

Posted in Kids, R, Statistics, University life with tags , , , , on July 12, 2014 by xi'an

I learned something in R today thanks to Le Monde mathematical puzzle:

A two-player game consists in A picking a number n between 1 and 10 and B and A successively choosing and applying one of three transforms to the current value of n

  • n=n+1,
  • n=3n,
  • n=4n,

starting with B, until n is larger than 999. Which value(s) of n should A pick if both players act optimally?

Indeed, I first tested the following R code

sole=function(n){
  if (n>999){ return(TRUE)
  }else{
     return((!sole(3*n))&(!sole(4*n))&(!sole(n+1)))
}}

which did not work because of too many calls to sole:

>sole(1)
Error: evaluation nested too deeply: infinite recursion
/ options(expressions=)?

So I included a memory in the calls to sole so that good and bad entries of n were saved for later calls:

visit=rep(-1,1000) #not yet visited
sole=function(n){
  if (n>999){ return(TRUE)
  }else{
     if (visit[n]>-1){ return(visit[n]==1)
     }else{
       visit[n]<<-((!sole(3*n))&(!sole(4*n))&
    (!sole(n+1)))
       return(visit[n]==1)
  }}}

Trying frontal attack

>sole(1)
Error: evaluation nested too deeply: infinite recursion
/ options(expressions=)?

did not work, but one single intermediary was sufficient:

> sole(500)
[1] FALSE
> for (i in 1:10)
+ print(sole(i))
[1] FALSE
[1] FALSE
[1] FALSE
[1] TRUE
[1] FALSE
[1] TRUE
[1] FALSE
[1] FALSE
[1] FALSE
[1] FALSE

which means that the only winning starters for A are n=4,6. If one wants the winning moves on top, a second counter can be introduced:

visit=best=rep(-1,1000)
sole=function(n){
  if (n>999){ return(TRUE)
  }else{
     if (visit[n]>-1){ return(visit[n]==1)
     }else{
       visit[n]<<-((!sole(3*n))&(!sole(4*n))&
       (!sole(n+1)))
       if (visit[n]==0) best[n]<<-max(
         3*n*(sole(3*n)),
         4*n*(sole(4*n)),
         (n+1)*(sole(n+1)))
       return(visit[n]==1)
  }}}

From which we can deduce the next values chosen by A or B as

> best[1:10]
 [1]  4  6  4 -1  6 -1 28 32 36 40

(where -1 means no winning choice is possible).

Now, what is the R trick I learned from this toy problem? Simply the use of the double allocation symbol that allows to change global variables within functions. As visit and best in the latest function. (The function assign would have worked too.)

Follow

Get every new post delivered to your Inbox.

Join 706 other followers