Le Monde puzzle [48: resolution]

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 a_{1i} equal to c. Among those (at least) 66 rows, if a pair (i,j) satisfies a_{ij}=c, the problem is over. Otherwise, all a_{ij} 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 a_{ij} are equal to d. Again, either there is at least one a_{jk}=d 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 a_{ij}‘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 a_{ij}‘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!

4 Responses to “Le Monde puzzle [48: resolution]”

  1. [...] 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 [...]

  2. [...] 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 [...]

  3. 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 1963=327\times 6+1 is minimal. I, for one, cannot be bothered to look for a network with 1962 nodes, 6 colours, and no monochromatic triangle.

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

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

Follow

Get every new post delivered to your Inbox.

Join 640 other followers