## Le Monde puzzle [48: resolution]

**T**he solution to puzzle 48 given in * Le Monde* this weekend is rather direct (which makes me wonder why the solution for 6 colours is still unavailable..) Here is a quick version of the solution: Consider one column, 1 say. Since

*326=5×65+1*, there exists one value

*c*with at least

*66*equal to

*c*. Among those (at least)

*66*rows, if a pair

*(i,j)*satisfies , the problem is over. Otherwise, all are different from

*c*for those (at least)

*66*rows, hence equal to one of the four remaining values. Since

*65=4×16+1*, for a given row

*i*in this group, there exists

*d*different from

*c*for which at least

*17*are equal to

*d*. Again, either there is at least one in this group of indices, else they all are different from

*c*and

*d*, hence equal to one of the three remaining values. Then

*16=3×5+1*, and for a given index

*j*within this group there exists

*e*different from

*c*and

*d*for which at least

*6*‘s are equal to

*e*. Again, either there is a triplet or they all take a value different from

*c,d,e*. Since

*5=2×2+1*, there exists

*f*different from

*c,d,e*, for which at least

*3*‘s are equal to

*f*. Again, either end of the story or they all three take the final value

*g*, but then constitute a triplet…

**T**his week * Le Monde* weekend puzzle [49] is:

*in a lottery, 999<N<10000 tickets numbered 1,2,…,N have been sold. All ticket numbers involving a 1 and a 3 to the right of the 1 are winning numbers. The percentage of winning tickets is 10%. How many tickets are there?*A manageable problem for R, obviously!

December 7, 2010 at 1:17 pm

[…] Monde puzzle [49] Here is a quick-and-dirty solution to Le Monde puzzle posted a few days ago: the R code counts the number of winning tickets between 1 and N, and stops when there is a […]

December 7, 2010 at 1:17 pm

[…] is a quick-and-dirty solution to Le Monde puzzle posted a few days ago: the R code counts the number of winning tickets between 1 and N, and stops when there is a […]

December 4, 2010 at 11:29 am

The reason the solution for 6 is not known (I am guessing) is that this solution does not show that 327 is minimal. For that, you would also need to exhibit a network with 326 nodes and no monochromatic triangle. Apparently, such a network has been found, but I suppose that no one knows whether is minimal. I, for one, cannot be bothered to look for a network with 1962 nodes, 6 colours, and no monochromatic triangle.

December 4, 2010 at 3:26 pm

Ok, Robin: I see your point as indeed the proof in Le Monde is that 327 is acceptable, not that it is the lowest bound. An upper bound for 6 colours would rather be 6×326+2=1958, as each node would then be connected to at least 327 other nodes for the most frequent colour

aand then, if no pair in those 327 was linked with this colour ,em>a, we would be back to the previous problem…