Archive for mathematical puzzle

Le Monde puzzle [#1009]

Posted in Books, Kids with tags , , , , on May 26, 2017 by xi'an

An incomprehensible (and again double) Le Monde mathematical puzzle (despite requests to the authors! The details in brackets are mine.):

  1. A [non-circular] chain of 63 papers clips can be broken into sub-chains by freeing one clip [from both neighbours] at a time. At a given stage, considering the set of the lengths of these sub-chains, the collection of all possible sums of these lengths is a subset of {1,…,63}. What is the minimal number of steps to recover the entire set {1,…,63}?  And what is the maximal length L of a chain of paper clips that allows this recovery in 8 steps?
  2.  A tri-colored chain of 200 paper clips starts with a red, a blue and a green clip. Removing one clip every four clips produces a chain of 50 removed clips identical to the chain of 50 first clips of the original chain and a chain of remaining 150 clips identical to the 150 first clips of the original chain. Deduce the number of green, red, and blue clips.

The first question can be easily tackled by random exploration. Pick one number at random between 1 and 63, and keep picking attached clips until the set of sums is {1,…,63}. For instance,

rebreak0]
 sumz=cumsum(sample(difz))
 for (t in 1:1e3)
  sumz=unique(c(sumz,cumsum(sample(difz))))
 if (length(sumz)<63)
    brkz=rebreak(sort(c(brkz,sample((1:63)[-brkz],1))))
 return(brkz)}

where I used sampling to find the set of all possible partial sums. Which leads to a solution with three steps, at positions 5, 22, and 31. This sounds impossibly small but the corresponding lengths are

1 1 1 4 8 16 32

from which one can indeed recover by summation all numbers till 63=2⁶-1. From there, a solution in 8 steps can be found by directly considering the lengths

1 1 1 1 1 1 1 1 9 18=9+8 36=18+17+1 72 144 288 576 1152 2303

whose total sum is 4607. And with breaks

10 29 66 139 284 573 1150 2303

The second puzzle is completely independent. Running another R code reproducing the constraints leads to

tromcol=function(N=200){
  vale=rep(0,N)
  vale[1:3]=1:3
  while (min(vale)==0){
    vale[4*(1:50)]=vale[1:50]
    vale[-(4*(1:50))]=vale[1:150]}
  return(c(sum(vale==1),sum(vale==2),sum(vale==3)))}

and to 120 red clips, 46 blue clips and 34 green clips.

Le Monde puzzle [#1008]

Posted in Books, Kids with tags , , , , on May 16, 2017 by xi'an

An arithmetic Le Monde mathematical puzzle (or two independent ones, rather):

  1. The set of integers between 1 and 2341 is partitioned into sets such that a given set never contains both n and 3n. What is the largest possible size of one of these sets?
  2.  Numbers between 1 and 2N are separated in two sets A and B of size N. Alice takes the largest element out of A and the smallest element out of B, records the absolute difference as S, and then repeats the sampling, adding the absolute difference to S at each draw. Bob does the same with numbers between 1 and 2P, with P<N, obtaining a total value of R. Alice points out that S-R=2341. What are the values of N and P?

The first question seems hard to solve by brute force simulation. My first idea is to take all prime numbers [except 3!] less than 2341, which is itself a prime number, and all combinations of these numbers less than 2341, since none of those is divisible by 3. Adding 3 as a final item keeps the constraint fine if 1 is not part of it (but 1 is not a prime number, so this is under control). Adding instead 1 to the set has the same impact but seems more natural. The number of prime numbers is 346, while the total size of the set thus constructed is 1561. Equal to 1+2×2340/3. However, the constraint in the puzzle does not exclude m and 9m. Or m and 9²m, or m and 9³m. Considering such multiples within {1,…,2341} leads to a set with 1765 integers.

The second puzzle is indeed independent and actually straightforward when one realises that the sums S and R are always equal to N² and P², respectively. (This is easily proven by invariance under a permutation turning the lowest entries to B and the largest ones to A. But there must be a rank statistic identity behind this result!) Hence it boils down to figuring out a pair (N,P) such that N²-P²=2341. Since 2341=(N-P)(N+P) is prime, this implies N=P+1. And N²-(N-1)²=N²-N²+2N-1=2341. Which leads to (N,P)=(1171,1170) as the only solution.

Le Monde puzzle [#1006]

Posted in Kids, R with tags , , , , , , , on May 3, 2017 by xi'an

Once the pseudo-story [noise] removed, a linear programming Le Monde mathematical puzzle:

For the integer linear programming problem

max 2x¹+2x²+x³+…+x¹⁰

under the constraints

x¹>x²+x³, x²>x³+x⁴, …, x⁹>x¹⁰+x¹, x¹⁰>x¹+x²

find a solution with the maximal number of positive entries.

Expressed this way, it becomes quite straightforward to solve with the help of a linear programming R code like lpSolve. Indeed, a simple iteration of the constraints shows that positive entries are necessarily bracketed by negative entries, since, e.g.,

x²<-88x¹/55, x¹⁰<-33x¹/55

(which applies to all consecutive triplets since the constraints are invariant by transposition). Hence there are at most five positive entries but calling lpSolve with this option

> lp (direction="max", 
objective.in=c(2,2,rep(1,8)),
const.mat=A, 
const.dir=rep(">=",10), 
const.rhs=rep(1,10)+A%*%c(rep(c(20,-1),5)), 
all.int=TRUE) 
Error: no feasible solution found

shows this is not possible. (The added vector is my way of getting around the constraint that lpSolve only considers positive entries. I therefore moved the negative entries by 20, meaning they are assumed to be larger than -20. Using the larger bound 50 does not change the outcome.) From there, there are 10 possible versions of vectors with four positive entries and a simple loop returns

> masume
[1] -90
> topast
 [1] -11 1 -13 1 -15 1 -17 1 -19 -9

as the maximal criterion and argument of this maximum with four positive entries.

As an aside, the previous Le Monde puzzle [#1005] was also provided by a linear system: given 64 cubes, each of the 384 faces being painted in one of four colours, with exactly 40 of these cubes exhibiting the four colours,  the question was about the number of cubes that could be bicolour so that a mono-colour super-cube could be reconstituted for all colours.  Which amounted to solve the four equations

4a+2b=24,4c+2d=40, b+c=8,d+3a=24,

leading to 40 quadri-colour, 16 tri-colour, and 8 bi-colour cubes.

a secretary problem with maximum ability

Posted in Kids, R with tags , , , , on April 28, 2017 by xi'an

The Riddler of today has a secretary problem, where one measures sequentially N random variables until one deems the current variable to be the largest of the whole sample. The classical secretary problem has a counter-intuitive solution where one first measures N/e random variables without taking any decision and then and only then picks the first next outcome larger than the largest in the first group. (For large values of N.) The added information in the current riddle is that the distribution of those iid random variables is set to be uniform on {1,…,M}, which begs for a modification in the algorithm. As for instance when observing M on the current draw.

The approach I devised is certainly suboptimal, as I decided to pick the currently observed value if the (conditional) probability it is the largest is larger than the probability subsequent draws. This translates into the following R code:

M=100 #maximum value
N=10  #total number of draws
hyprob=function(m){
# m is sequence of draws so far
n=length(m);mmax=max(m)
if ((m[n]<mmax)||(mmax-n<N-n)){prob=0
  }else{
  prob=prod(sort((1:mmax)[-m],dec=TRUE)
   [1:(N-n)]/((M-n):(M-N+1))}
return(prob)}

decision=function(draz=sample(1:M,N)){
  i=0
  keepgoin=TRUE
  while ((keepgoin)&(i<N)){
   i=i+1
   keepgoin=(hyprob(draz[1:i])<0.5)}
  return(c(i,draz[i],(draz[i]<max(draz))))}

which produces a winning rate of around 62% when N=10 and M=100, hence much better than the expected performances of the (asymptotic) secretary algorithm, with a winning frequency of 1/e. (For N=10 and M=100, the winning frequency is only 27%.)

Le Monde puzzle [#1003]

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

A purely arithmetic Le Monde mathematical puzzle:

Find the four integers w, x, y, z such that the four smallest pairwise sums among the six pairwise sums are 59, 65, 66, and 69. Similarly, find the four smallest of the five integers v, x, y, z such that the five smallest pairwise sums among the ten pairwise sums are 56, 64 , 66, 69 and 70.

The first question is rather straightforward since there are only two possible orderings when x≤y≤z≤w :

x+y≤x+z≤x+w≤y+z≤y+w≤z+w and x+y≤x+z≤y+z≤x+w≤y+w≤z+w

which means

x+y=59, x+z=65, x+w=66, y+z=69, and x+y=59, x+z=65, y+z=66, x+w=69

but since the first system does not allow for an integer solution, the only possibility is the second system, with solution (x,y,z,w)=(29,30,36,40). And the second question is of the same complexity, with, when x≤y≤z≤w≤v :

x+y=56, x+z=64, y+z=66, x+w=69, x+v=70 or x+y=56, x+z=64, x+w=66, x+v=69, y+z=70

with solutions (x,y,z,w,v)=(27,29,37,42,43) and (x,y,z,w,v)=(25,31,39,41,44).

optimultiplication [a riddle]

Posted in Books, Kids, R, Statistics with tags , , , , , on April 14, 2017 by xi'an

The riddle of this week is about an optimisation of positioning the four digits of a multiplication of two numbers with two digits each and is open to a coding resolution:

Four digits are drawn without replacement from {0,1,…,9}, one at a time. What is the optimal strategy to position those four digits, two digits per row, as they are drawn, toward minimising the average product?

Although the problem can be solved algebraically by computing E[X⁴|x¹,..] and E[X⁴X³|x¹,..]  I wrote three R codes to “optimise” the location of the first three digits: the first digit ends up as a unit if it is 5 or more and a multiple of ten otherwise, on the first row. For the second draw, it is slightly more variable: with this R code,

second<-function(i,j,N=1e5){draw
drew=matrix(0,N,2)
for (t in 1:N)
  drew[t,]=sample((0:9)[-c(i+1,j+1)],2)
conmean=(45-i-j)/8
conprod=mean(drew[,1]*drew[,2])
if (i<5){ #10*i
 pos=c((110*i+11*j)*conmean,
       100*i*j+10*(i+j)*conmean+conprod,
       (100*i+j)*conmean+10*i*j+10*conprod)}else{
 pos=c((110*j+11*i)*conmean,
       10*i*j+(100*j+i)*conmean+10*conprod,
       10*(i+j)*conmean+i*j+100*conprod)
 return(order(pos)[1])}

the resulting digit again ends up as a unit if it is 5 (except when x¹=7,8,9, where it is 4) or more and a multiple of ten otherwise, but on the second row. Except when x¹=0, x²=1,2,3,4, when they end up on the first row together, 0 obviously in front.

For the third and last open draw, there is only one remaining random draw, which mean that the decision only depends on x¹,x²,x³ and E[X⁴|x¹,x²,x³]=(45-x¹-x²-x³)/7. Attaching x³ to x² or x¹ will then vary monotonically in x³, depending on whether x¹>x² or x¹<x²:

fourth=function(i,j,k){
comean=(45-i-j-k)/7
if ((i<1)&(j<5)){ pos=c(10*comean+k,comean+10*k)}
if ((i<5)&(j>4)){ pos=c(100*i*comean+k*j,j*comean+100*i*k)}
if ((i>0)&(i<5)&(j<5)){ pos=c(i*comean+k*j,j*comean+i*k)} 
if ((i<7)&(i>4)&(j<5)){ pos=c(i*comean+100*k*j,j*comean+100*i*k)} 
if ((i<7)&(i>4)&(j>4)){ pos=c(i*comean+k*j,j*comean+i*k)}
if ((i>6)&(j<4)){ pos=c(i*comean+100*k*j,j*comean+100*i*k)} 
if ((i>6)&(j>3)){ pos=c(i*comean+k*j,j*comean+i*k)}
return(order(pos)[1])}

Running this R code for all combinations of x¹,x² shows that, except for the cases x¹≥5 and x²=0, for which x³ invariably remains in front of x¹, there are always values of x³ associated with each position.

Le Monde puzzle [#1002]

Posted in Kids, R with tags , , , , , , , on April 4, 2017 by xi'an

For once and only because it is part of this competition, a geometric Le Monde mathematical puzzle:

Given both diagonals of lengths p=105 and q=116, what is the parallelogram with the largest area? and when the perimeter is furthermore constrained to be L=290?

This made me jump right away to the quadrilateral page on Wikipedia, which reminds us that the largest area occurs when the diagonals are orthogonal, in which case it is A=½pq. Only the angle between the diagonals matters. Imposing the perimeter 2s in addition is not solved there, so I wrote an R code looking at all the integer solutions, based on one of the numerous formulae for the area, like ½pq sin(θ), where θ is the angle between both diagonals, and discretising in terms of the fractions of both diagonals at the intersection, and of the angle θ:

p=105
q=116
s=145
for (alpha in (1:500)/1000){
 ap=alpha*p;ap2=ap^2;omap=p-ap;omap2=omap^2
 for (beta in (1:999)/1000){
  bq=beta*q;bq2=bq^2;ombq=q-bq;ombq2=ombq^2
  for (teta in (1:9999)*pi/10000){
   d=sqrt(ap2+bq2-2*ap*bq*cos(teta))
   a=sqrt(ap2+ombq2+2*ap*ombq*cos(teta))
   b=sqrt(omap2+ombq2-2*omap*ombq*cos(teta))
   c=sqrt(omap2+bq2+2*omap*bq*cos(teta))
   if (abs(a+b+c+d-2*s)<.01){
     if (p*q*sin(teta)<2*maxur){
       maxur=p*q*sin(teta)/2
       sole=c(a,b,c,d,alpha,beta,teta)}}}}

This code returned an area of 4350, to compare with the optimal 6090 (which is recovered by the above R code when the diagonal lengths are identical and the perimeter is the one of the associated square). (As Jean-Louis Foulley pointed out to me, this area can be found directly by assuming the quadrilateral is a parallelogram and maximising in the length of one side.)