Le Monde puzzle [46]
This week puzzle in Le Monde does not make much sense, unless I miss the point: in an undirected graph with 2011 nodes, each node is linked with at least 1005 other nodes. Is there always a node that is linked with all the nodes? If I take the first two nodes, 1 and 2, if there were no common node, the 1005 nodes linked with 1 would differ from the 1005 nodes linked with 2 and would not include 2. This corresponds to 1+1005+1005+1=2012 nodes… Sounds too easy, doesn’t it?!
Update (111810): Easy, too easy! Robin pointed out to me yesterday that this proves that 1 and 2 share a neighbour, nothing more. His counterexample to the existence of a common neighbour is to create nodes from node i to any node but (i-1) mod n and (i+1) mod n, which makes a graph with n-3 edges leaving from each node and still no common neighhbour! Conclusion: I should not try to quick-solve puzzles at 4:38am…
October 21, 2011 at 12:14 am
[…] puzzle in Le Monde this weekend is not that clear (for a change!), so I may be confused in the following […]
November 25, 2010 at 12:49 am
[…] connection with Le Monde puzzle #46, I eventually managed to write an R program that generates graphs with a given number n of nodes […]