Le Monde puzzle [#1006]
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.
May 3, 2017 at 5:33 pm
Sorry Christian for this messy stuff. It seems that there is a problem with the transcription of symbols. For more details see
https://www.researchgate.net/publication/316655944_Solution_to_Le_Monde_Puzzle_1006
May 3, 2017 at 1:47 pm
[…] article was first published on R – Xi'an's Og, and kindly contributed to […]
May 3, 2017 at 1:26 am
Thanks Christian for stimulating our interest in this special Le Monde puzzle competition. Here is my way to recover your solution.
Let us assume that positive and negative values alternate ; start with a negative one and take the positive value being constant and equal to one; The 12 values are
-a 1 -b 1 -c 1 -d 1 -e f -a 1
One has to verify
-a>1-b ie b-1>a
which means that a minima b=a+2. Next 1>-b+1 means b>0 and
-b>1-c ie b<c-1
and a minima in c, c=b+2=a+4
Continuing this way,
d=c+2=a+6 and e=d+2=a_8
and since e<f-a
a+8< a-f
and -f=8
The last condition is
f>-a+1 or -f<a-1
and combined with the previous one
8<-f<a-1,
which means that a minima
a=11 and f=-9
so that the final solution is
-11 1 -13 1 -15 1 -17 1 -19 -9 -11 1
May 3, 2017 at 4:34 pm
Merci, Jean-Louis! Some bits of the arguments did not make it through though…