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", 
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.

4 Responses to “Le Monde puzzle [#1006]”

  1. FOULLEY Jean-Louis Says:

    Sorry Christian for this messy stuff. It seems that there is a problem with the transcription of symbols. For more details see

  2. […] article was first published on R – Xi'an's Og, and kindly contributed to […]

  3. FOULLEY Jean-Louis Says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s