Archive for Le Monde

Le Monde puzzle [#1051]

Posted in Books, Kids, R with tags , , , , , , on May 18, 2018 by xi'an

A combinatoric Le Monde mathematical puzzle of limited size:
When the only allowed move is to switch two balls from adjacent boxes, what is the minimal number of moves to return all balls in the above picture to their respective boxes? Same question with six boxes and 12 balls.

The question is rather interesting to code as I decided to use recursion (as usual!) but wanted to gain time by storing the number of steps needed by any configuration to reach its ordered recombination. Meaning I had to update an external vector within the recursive function for each new configuration I met. With help from Julien Stoehr, who presented me with the following code, a simplification of a common R function

v.assign <- function (i,value,...) {
  temp <- get(i, pos = 1)
  temp[...] <- value
  assign(i, temp, pos = 1)}

which assigns one or several entries to the external vector i. I thus used this trick in the following R code, where cosz is a vector of size 5¹⁰, much larger than the less than 10! values I need but easier to code. While n≤5.

n=5;tn=2*n
baz=n^(0:(tn-1))
cosz=rep(-1,n^tn)
swee <- function(balz){
  indz <- sum((balz-1)*baz)
  if (cosz[indz]==-1){ 
  if (min(diff(balz))==0){ #ordered
     v.assign("cosz",indz,value=1)}else{
       val <- n^tn
       for (i in 2:n)
       for (j in (2*i-1):(2*i))
       for (k in (2*i-3):(2*i-2)){
         calz <- balz
         calz[k] <- balz[j];calz[j] 0) 
           val <- min(val,1+swee(calz))}
     v.assign("cosz",indz,value=val)
  }}
 return(cosz[indz])}

which returns 2 for n=2, 6 for n=3, 11 for n=4, 15 for n=5. In the case n=6, I need a much better coding of the permutations of interest. Which is akin to ranking all words within a dictionary with letters (1,1,…,6,6). After some thinking (!) and searching, I came up with a new version, defining

parclass=rep(2,n)
rankum=function(confg){
    n=length(confg);permdex=1
    for (i in 1:(n-1)){
      x=confg[i]
      if (x>1){
        for (j in 1:(x-1)){
            if(parclass[j]>0){
                parclass[j]=parclass[j]-1
                permdex=permdex+ritpermz(n-i,parclass)
                parclass[j]=parclass[j]+1}}}
        parclass[x]=parclass[x]-1}
    return(permdex)}

ritpermz=function(n,parclass){
    return(factorial(n)/prod(factorial(parclass)))}

for finding the index of a given permutation, between 1 and (2n)!/2!..2!, and then calling the initial swee(p) with this modified allocation. The R code was still running when I posted this entry… and six days later, it returned the answer of 23.

Le Monde puzzle [#1045]

Posted in Books, Kids with tags , , , , , , on May 13, 2018 by xi'an

An minor arithmetic Le Monde mathematical puzzle:

Take a sequence of 16  integers with 4 digits each, separated by 2,  such that it contains a perfect square and its sum is a perfect cube. What are the possible squares and cubes?

The question is dead easy to code in R

for (x in as.integer(1e3:(1e4-16))){
  if (max(round(sqrt(x+2*(0:15)))^2==x+2*(0:15))==1) {
    b=sqrt((x+2*(0:15))[round(sqrt(x+2*(0:15)))^2==x+2*(0:15)])
  if ((round((2*x+30)^(1/3)))^3==(2*x+30)) 
   print(c(x,b,(16*(x+15))^(1/3)))}}

and return the following solutions:

[1] 1357   37   28
[1] 5309   73   44

Nothing that exciting…!

Le Monde puzzle [#1049]

Posted in Books, Kids, R with tags , , , on April 18, 2018 by xi'an

An algorithmic Le Monde mathematical puzzle with a direct

Alice and Bob play a game by picking alternatively one of the remaining digits between 1 and 10 and putting it in either one of two available stacks, 1 or 2. Their respective gains are the products of the piles (1 for Alice and 2 for Bob).

The problem is manageable by a recursive function

facten=factorial(10)
pick=function(play=1,remz=matrix(0,2,5)){
 if ((min(remz[1,])>0)||(min(remz[2,])>0)){#finale
  remz[remz==0]=(1:10)[!(1:10)%in%remz]
  return(prod(remz[play,]))
  }else{
   gainz=0
   for (i in (1:10)[!(1:10)%in%remz]){
     propz=rbind(c(remz[1,remz[1,]>0],i,
     rep(0,sum(remz[1,]==0)-1)),remz[2,])
     gainz=max(gainz,facten/pick(3-play,remz=propz))}
   for (i in (1:10)[!(1:10)%in%remz]){
     propz=rbind(remz[1,],c(remz[2,remz[2,]>0],i,
     rep(0,sum(remz[2,]==0)-1)))
     gainz=max(gainz,facten/pick(3-play,remz=propz))}
return(gainz)}}

that shows the optimal gain for Alice is 3360=2x5x6x7x 8, versus Bob getting 1080=1x3x4x9x10. The moves ensuring the gain are 2-10-…

Le Monde puzzle [#1048]

Posted in Books, Kids, R with tags , , , , , on April 1, 2018 by xi'an

An arithmetic Le Monde mathematical puzzle:

A magical integer m is such that the remainder of the division of any prime number p by m is either a prime number or 1. What is the unique magical integer between 25 and 100? And is there any less than 25?

The question is dead easy to code

primz=c(1,generate_primes(2,1e6))
for (y in 25:10000)
  if (min((primz[primz>y]%%y)%in%primz)==1) print(y)

and return m=30 as the only solution. Bon sang but of course!, since 30=2x3x5… (Actually, the result follows by dividing the quotient of the division of a prime number by 2 by 3 and then the resulting quotient by 5: all possible cases produce a remainder that is a prime number.) For the second question, the same code returns 2,3,4,6,8,12,18,24 as further solutions. There is no solution beyond 30.

gender gaps

Posted in Statistics, University life with tags , , , , , , , , , , on March 31, 2018 by xi'an

Two of my colleagues [and co-authors] at Dauphine, Elyès Jouini and Clotilde Napp, published a paper in Science last week (and an associated tribune in Le Monde which I spotted first) about explaining differences in national gender inequalities in maths (as measured by PISA) in terms of the degree of overall inequality in the respective countries. Gaps in the highest maths performer sex ratio. While I have no qualm about the dependency or the overall statistical cum machine learning analysis (supported by our common co-author Jean-Michel Marin), and while I obviously know nothing about the topic!, I leisurely wonder at the cultural factor (which may also partly explain for the degree of inequality) when considering that the countries at the bottom of the above graphs are rather religious (and mostly catholic). I also find it most intriguing that the gender gap is consistently reversed when considering higher performer sex ratio for reading, because mastering the language should be a strong factor in power structures and hence differences therein should also lead to inequalities…

Le Monde puzzle [#1045]

Posted in Books, Kids with tags , , , on March 19, 2018 by xi'an

An arithmetic Le Monde mathematical puzzle of limited proportions (also found on Stack Exchange):

  1. If x,y,z are distinct positive integers such that x+y+z=19 and xyz=p, what is the value of p that has several ordered antecedents?
  2.  If the sum is now x+y+z=22, is there a value of p=xyz for which there are several ordered antecedents?
  3. If the sum is now larger than 100, is there a value of p with this property?

The first question is dead easy to code

entz=NULL
for (y in 1:5) #y<z<x
for (z in (y+1):trunc((18-y)/2))
 if (19-y-z>z) entz=c(entz,y*z*(19-y-z))

and return p=144 as the only solution (with ordered antecedents 2 8 9 and 3 4 12). The second question shows no such case. And the last one requires more than brute force exploration! Or the direct argument that a multiple by κ of a non-unique triplet produces a sum multiplied by κ and a product multiplied by κ³. Hence leads to another non-unique triplet with an arbitrary large sum.

Le Monde puzzle [#1044]

Posted in Books, Kids with tags , , , , , , on March 12, 2018 by xi'an

A dynamic programming Le Monde mathematical puzzle:

Bob and Alice are playing a game where Alice fills a one-litre bottle from a water fountain, and empties it between four buckets. Bob then empties two of the four buckets. Alice then fills again her bottle and empties it again in the buckets. Alice wins if she manages to fill one bucket after a finite number of steps. What is the maximum capacity of a bucket for Alice to find a winning strategy?

The question sounded too complex to solve by an R code so I somewhat simplified it by deciding that Alice could not allocate any portion of the litre to a bucket but instead only 0,¼,⅓,½,⅔,¾,1. And then looked at a finite horizon to see how much she could fill a bucket when Bob was trying to minimise this amount: a crude R code just took too long for an horizon of 6 steps and hence I tried to reduce the number of calls to my recursive function

solfrak=c(0,.25,.333,.5,.667,.75,1)
petifil=function(buck=rep(0,4),hor=3){
#eliminate duplicates
 albukz=NULL
 for (a in solfrak)
 for (b in solfrak[!(solfrak+a>1)])
 for (c in solfrak[!(solfrak+a+b>1)]){
   if (a+b+c<=1){ albukz=rbind(albukz,
      c(a,b,c,1-a-b-c))}} 
   albukz=t(apply(buck+albukz,1,sort)) 
   albukz=albukz[!duplicated(albukz),] 
   if (is.matrix(albukz)){ 
    bezt=max(apply(albukz,1,petimpty,hor=hor-1)) 
    }else{ 
      bezt=petimpty(albukz,hor-1)} 
    return(bezt)} 

petimpty=function(buck,hor){ 
  if (hor>1){
    albukz=NULL
     for (i in 1:3)
     for (j in (i+1):4)
      albukz=rbind(albukz,c(buck[-c(i,j)],0,0))
     albukz=t(apply(albukz,1,sort))
     albukz=albukz[!duplicated(albukz),]
     if (is.matrix(albukz)){
       bezt=min(apply(albukz,1,petifil,hor))}else{
        bezt=petifil(albukz,hor)}
     }else{
      bezt=sort(buck)[2]+1}
   return(bezt)}

which led to a most surprising outcome:

> petifil(hor=2)
[1] 1.333
> petifil(hor=3)
[1] 1.5
> petifil(hor=4)
[1] 1.5
> petifil(hor=5)
[1] 1.5

that is no feasible strategy to beat the value 1.5 liters. Which actually stands way below two liters, the maximum content of the bucket produced in the solution!