The 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…
This 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!
This entry was posted on December 4, 2010 at 7:37 am and is filed under R, Statistics with tags graphs, Le Monde, mathematical puzzle, R. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
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 a and then, if no pair in those 327 was linked with this colour ,em>a, we would be back to the previous problem…