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…

2 Responses to “Le Monde puzzle [46]”

  1. […] puzzle in Le Monde this weekend is not that clear (for a change!), so I may be confused in the following […]

  2. […] connection with Le Monde puzzle #46, I eventually managed to write an R program that generates graphs with a given number n of nodes […]

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: