Archive for mathematical puzzle

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

Le Monde puzzle [#872]

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

An “mildly interesting” Le Monde mathematical puzzle that eventually had me running R code on a cluster:

Within the set {1,…,56}, take 12 values at random, x1,…,x12. Is it always possible to pick two pairs from those 12 balls such that their sums are equal?

Indeed, while exhaustive search cannot reach the size of the set,

fowler=function(i=1,pred=NULL){
  pred=c(pred,i)
  for (j in (1:N)[-pred]){
     a=outer(c(pred,j),c(pred,j),"+")
     if ((sum(duplicated(a[lower.tri(a)]))>0)){
        val=FALSE
        }else{
          if (length(pred)==n-1){
            print(c(pred,j))
            val=TRUE
            }else{
            val=fowler(j,pred)}}
     if (val) break()
     }
  return(val)
  }
fowler(i=N,pred=1)

with N=35 being my upper limit (and n=9 the largest value inducing double sums), the (second) easiest verification goes by sampling as indicated and checking for duplicates.

mindup=66
for (t in 1:10^7){
#arguing that extremes should be included
  x=c(1,56,sample(2:55,10))
  A=outer(x,x,"+")
  mindup=min(mindup,sum(duplicated(A[lower.tri(A)])))
  if (mindup==0) break()}

The values of mindup obtained by running this code a few times are around 5, which means a certain likelihood of a positive answer to the above question…

This problem raises a much more interesting question, namely how to force simulations of those 12-uplets towards the most extreme values of the target function, from simulated annealing to cross-entropy to you-name-it… Here is my simulated annealing attempt:

target=function(x){
  a=outer(x,x,"+")
  return(sum(duplicated(a[lower.tri(a)])))}
beta=100
Nmo=N-1
nmt=n-2
nmo=n-1
x=sort(sample(2:Nmo,nmt))
cur=c(1,x,N)
tarcur=target(cur)
for (t in 1:10^6){
  dex=sample(2:nmo,2)
  prop=sort(c(cur[-dex],sample((2:Nmo)[-(cur-1)],2)))
  tarprop=target(prop)
  if (beta*log(runif(1))<tarprop -tarcur){
     cur=prop;tarcur=tarprop}
  beta=beta*.9999
  if (tarcur==0) break()}

Apart from this integer programming exercise, a few items of relevance in this Le Monde Science & Medicine leaflet.  A portrait of Leslie Lamport for his Turing Prize (yes, the very same Leslie Lamport who created LaTeX!, and wrote this book which stood on most mathematicians’ bookshelves for decades, with the marginally annoying lion comics at the head of each chapter!). A tribune on an interesting book, The Beginning and the End, by Clément Vidal, discussing how to prepare for the end of the Universe by creating a collective mind. And the rise of biobanks…

Le Monde sans puzzle

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

This week, Le Monde mathematical puzzle: is purely geometric, hence inappropriate for an R resolution. In the Science & Médecine leaflet, there is however an interesting central page about random generators, from the multiple usages of those in daily life to the consequences of poor generators on cryptography and data safety. The article is compiling an interview of Jean-Paul Delahaye on the topic with recent illustrations from cybersecurity. One final section gets rather incomprehensible: when discussing the dangers of seed generation, it states that “a poor management of the entropy means that an hacker can saturate the seed and take over the original randomness, weakening the whole system”. I am sure there is something real behind the imagery, but this does not make sense… Another insert mentions a possible random generator built out of the light detectors on a smartphone. And quantum physics. The society IDQ can indeed produce ultra-rapid random generators that way. And it also ran randomness tests summarised here. Using in particular George Marsaglia’s diehard battery.

Another column report that a robot passed the Turing test last week, on Turing‘s death anniversary. Meaning that 33% of the jury was convinced the robot’s answers were given by a human. This reminded me of the Most Human Human book sent to me by my friends from BYU. (A marginalia found in Le Monde is that the test was organised by Kevin Warwick…from the University of Coventry, a funny reversal of the University of Warwick sitting in Coventry! However, checking on his website showed that he has and had no affiliation with this university, being at the University of Reading instead.)

 

Le Monde puzzle [#869]

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

An uninteresting Le Monde mathematical puzzle:

Solve the system of equations

  • a+b+c=16,
  • b+c+d=12,
  • d+c+e=16,
  • e+c+f=18,
  • g+c+a=15

for 7 different integers 1≤a,…,g9.

Indeed, the final four equations determine d=a-4, e=b+4, f=a-2, g=b-1 as functions of a and b. While forcing 5≤a, 2b≤5, and  7a+b≤15. Hence, 5 possible values for a and 4 for b. Which makes 20 possible solutions for the system. However the fact that a,b,c,d,e,f,g are all different reduces considerably the possibilities. For instance, b must be less than a-4. The elimination of impossible cases leads in the end to consider b=a-5 and b=a-7. And eventually to a=8, b=3… Not so uninteresting then. A variant of Sudoku, with open questions like what is the collection of the possible values of the five sums, i.e. of the values with one and only one existing solution? Are there cases where four equations only suffice to determine a,b,c,d,e,f,g?

Apart from this integer programming exercise, a few items of relevance in this Le Monde Science & Medicine leaflet.  A description of the day of a social sciences worker in front of a computer, in connection with a sociology (or sociometry) blog and a conference on Big Data in sociology at Collège de France. A tribune by the physicist Marco on data sharing (and not-sharing) illustrated by an experiment on dark matter called Cogent. And then a long interview of Matthieu Ricard, who argues about the “scientifically proven impact of meditation”, a sad illustration of the ease with which religions permeate the scientific debate [or at least the science section of Le Monde] and mingle scientific terms with religious concepts (e.g., the fusion term of “contemplative sciences”). [As another "of those coincidences", on the same day I read this leaflet, Matthieu Ricard was the topic of one question on a radio quizz.]

Le Monde puzzle [#868]

Posted in Books, Kids, Statistics with tags , , , on June 1, 2014 by xi'an

Another permutation-based Le Monde mathematical puzzle:

Given the integers 1,…n, a “perfect” combination is a pair (i,j) of integers such that no other pair enjoys the same sum. For n=33, what is the maximum of perfect combinations one can build? And for n=214? 

A rather straightforward problem, or so it seemed: take the pairs (2m,2m+1), their sums all differ, and we get the maximal possible number of sums, ⌊n/2⌋… However, I did not read the question properly (!) and the constraint is on the sum (i+j), namely

How many mutually exclusive pairs (i,j) can be found with different sums all bounded by n=33? n=2014?

In which case, the previous and obvious proposal works no longer… The dumb brute-force search

T=10^6
sol=0
for (t in 1:T){
  perm=sample(1:sample(seq(20,32,2),1))
  sal=sum(unique(apply(matrix(perm,ncol=2),1,sum))<33)
  if (sal>sol){
     sol=sal;laperm=perm}
  }

leads to a solution of

> sol
[1] 12
> laperm
 [1]  6  9  1 24 13 20  4  7 21 14 17  3 16 11 19 25 23 18 12 26 15  2  5 10 22
[26]  8
> unique(apply(matrix(laperm,ncol=2),1,sum))
[1] 17 28 26 47 31 32 30 22 23 19 27 25 24

which is close of the solution sol=13 proposed in Le Monde… It is obviously hopeless for a sum bounded by 2014. A light attempt at simulated annealing did not help either.

Follow

Get every new post delivered to your Inbox.

Join 598 other followers