Le Monde puzzle [#820]

The current puzzle is… puzzling:

Given the set {1,…,N} with N<61, one iterates the following procedure: take (x,y) within the set and replace the pair with the smallest divider of x+y (bar 1). What are the values of N such that the final value in the set is 61?

I find it puzzling because the way the pairs are selected impacts the final value. Or not, depending upon N. Using the following code (with factors() from the pracma package):

library(pracma)
endof=function(N){
  coll=1:N
  for (t in 1:(N-1)){

    pair=sample(1:length(coll),2)
    dive=min(factors(sum(coll[pair])))
    coll=coll[-pair]
    coll=c(coll,dive)
    }
  print(dive)
  }

I got:

> for (t in 1:10) endof(10)
[1] 5
[1] 3
[1] 3
[1] 5
[1] 7
[1] 5
[1] 5
[1] 7
[1] 3
[1] 3> for (t in 1:10) endof(16)
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2
[1] 2

For N of the form 4k or 4k-1, the final number is always 2 while for N‘s of the form 4k-2 and 4k-3, the final number varies, sometimes producing 61′s. Although I could not find solutions for N less than 17…  Looking more closely into the sequence leading to 61, I could not see a pattern, apart from producing prime numbers as, in, e.g.

61 = 2 + [12 +  (4 + {14 + [13 + 16]})]

for N=17.  (Another puzzle is that 61 plays no particular role: a long run of random calls to endof() return all prime numbers up to 79…)

Udate: Looking at the solution in today’s edition, there exist a solution for N=13 and a solution for N=14. Even though my R code fails to spot it. Of course, an exhaustive search would be feasible in these two cases.  (I had also eliminated values below as not summing up to 61.) The argument for eliminating 4k and 4k-1 is that there must be an odd number of odd numbers in the collection, otherwise, the final number is always 2.

Le Monde puzzle [#818]

The current puzzle is as follows:

Define the symmetric of an integer as the integer obtained by inverting the order of its digits, eg 4321 is the symmetric of 1234. What are the numbers for which the square is equal to the symmetric of the square of the symmetric?

I first consulted stackexchange to find a convenient R function to create the symmetric:

int2digit=function(x){
as.numeric(sapply(sequence(nchar(x)),
  function(y) substr(x, y, y)))}

digit2int=function(a){
as.numeric(paste(a,collapse=""))}

flip=function(x){
  digit2int(rev(int2digit(x)))}

and then found that all integers but the multiples of 10 are symmetric! only some integers involving 1,2,3 and sometimes zero would work:

> for (i in 1:1000){
+   if (i^2==flip(flip(i)^2)) print(i)}
[1] 1
[1] 2
[1] 3
[1] 11
[1] 12
[1] 13
[1] 21
[1] 22
[1] 31
[1] 101
[1] 102
[1] 103
[1] 111
[1] 112
[1] 113
[1] 121
[1] 122
[1] 201
[1] 202
[1] 211
[1] 212
[1] 221
[1] 301
[1] 311

If I am not (again) confused, the symmetric integers would be those (a) not ending with zero and (b) only involving digits whose products are all less than 10.

interesting puzzle

In addition to its weekly mathematics puzzles, Le Monde is now publishing a series of vulgarisation books on mathematics, under the patronage of Cédric Villani. Jean-Michel Marin brought me two from the series, one on the golden number and one on Pythagoras’ theorem. (This is actually a translation of a series published by El Pais last year.) Those books are a bit stretched given the topic, even though I enjoyed the golden number (the second one having a lot of redundancy with the first one.) However, I came upon an interesting question, namely about the maximum size of a cube that could fit through a tunnel drilled through the unit cube. Sadly, I could not find an answer to this problem on the web, even though the book mentions a solution with a side larger than one…

Le Monde puzzle [#817]

The weekly Le Monde puzzle is (again) a permutation problem that can be rephrased as follows:

Find

where denotes the set of permutations on {0,…,10} and is defined modulo 11 [to turn {0,...,10} into a torus]. Same question for

and for

This is rather straightforward to code if one adopts a brute-force approach::

perminmax=function(T=10^3){
  mins=sums=rep(500,3)
  permin=matrix(0:10,ncol=11,nrow=3,byrow=TRUE)

  for (t in 1:T){
    perms=sample(0:10)
    adde=perms+perms[c(11,1:10)]
    sums[1]=max(adde)
    adde=adde+perms[c(10,11,1:9)]
    sums[2]=max(adde)
    adde=adde+perms[c(9:11,1:8)]+perms[c(8:11,1:7)]
    sums[3]=max(adde)
    for (j in 1:3)
     if (sums[j]<mins[j]){
       mins[j]=sums[j];permin[j,]=perms}
    }

  print(mins)
  print(permin)
  }

(where I imposed the first term to be zero because of the invariance by permutation), getting the solutions

> perminmax(10^5)
[1] 11 17 28
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,]    0   10    1    6    5    4    7    3    8     2     9
[2,]    0   10    4    3    5    1    9    6    2     8     7
[3,]    0    2    9    6    7    3    1    4   10     8     5

for 2, 3, and 5 terms.  (Since 10! is a mere 3.6 million, I checked with an exhaustive search, using the function permutation from the gtools package.)

Le Monde puzzle [#815]

The last puzzle was as follows:

Take a card stack with 32 cards and divide it into five non-empty piles. A move consists in doubling a pile size by taking card from a single and larger pile. Is it possible to recover the original stack by repeatedly using moves? Same question for 100 cards and five piles.

I first defined a recursive R function to check if this was obvious:

destock=function(stock){

 vale=FALSE
 if (max(stock)==32){ #success
         vale=TRUE}else{
 #empty piles must remain empty
 i0=min((1:4)[stock[1:4]>0])

 for (i in i0:4){
 for (j in (i+1):5){
 stuck=stock
 stuck[i]=2*stock[i] #doubling
 stuck[j]=stuck[j]-stock[i] #borrowing
 stuck=sort(stuck)
 vale=vale||destock(stuck)
 if (vale) break()
 }
 if (vale) break()
 }}
 return(vale)
 }

Then I launched the R code with random starting values:

stack=sample(1:5,27,rep=TRUE)
stock=rep(1,5)
for (i in 1:5) stock[i]=1+sum(stack==i)
stock=sort(stock)

obtaining either a solution or “infinite recursion” warnings. In the first case, getting a sequence like

> destock(stock)
[1]  5  5  7  7  8
[1]  0  7  7  8 10
[1]  0  0  8 10 14
[1]  0  0  2 14 16
[1]  0  0  4 12 16
[1]  0  0  8  8 16
[1]  0  0  0 16 16
[1]  0  0  0  0 32
[1] TRUE

and, in the second, observing an infinite cycle like

> destock(stock)
[1]  3  4  7  8 10
[1]  1  6  7  8 10
[1]  2  5  7  8 10
[1]  3  4  7  8 10
[1]  1  6  7  8 10
[1]  2  5  7  8 10
[1]  3  4  7  8 10
[1]  1  6  7  8 10
Error: evaluation nested too deeply:
infinite recursion / options(expressions=)?

The above shows that there exist pile configurations that do not allow for this recursive algorithm to converge. I then thought of introducing randomness in the exploration of the tree as possibly avoiding infinite regress

    for (i in sample(i0:4)){

and, lo and behold!, it worked for every attempt:

> destock(stock)
[1]  3  4  7  8 10
[1]  3  3  8  8 10
[1]  0  6  8  8 10
[1]  0  2  8 10 12
[1]  0  2  2 12 16
[1]  0  2  2  4 24
[1]  0  2  2  4 24
[1]  0  0  4  4 24
[1]  0  0  4  8 20
[1]  0  0  4  8 20
[1]  0  0  4  8 20
[1]  0  0  4  8 20
[1]  0  0  4 12 16
[1]  0  0  8  8 16
[1]  0  0  0 16 16
[1]  0  0  0 16 16
[1]  0  0  0 16 16
[1]  0  0  0 16 16
[1]  0  0  0 16 16
[1]  0  0  0 16 16
[1]  0  0  0  0 32
[1] TRUE

It is rather straightforward to prove that the scheme works for a size equal to a power of two like 32 while it cannot work for sizes different from a power of 2. Like 100.