[Computational Complexity] Puzzles That Keep You Awake at Night
Dartmouth Professor Peter Winkler visited our department yesterday and today, the first stop of a two-week five-university tour. Winkler gives great seminar talks and is easy to talk to about hard combinatorial problems. Unfortunately whenever I see him he also brings very tantalizing puzzles that you have to work hard at not thinking about, lest they consume you. For example Love in Kleptopia
Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands?From Seven Puzzles You Think You Must Not Have Heard Correctly (with solutions). For the more mathematically minded here is the Infinite Hats Problem that he told me earlier this year.
A countable number of people each have either a white hat or black hat on their heads. Each person can see everyone's hats except their own. Each person simultaneously announces a guess for the color of their hat. Is there a strategy for the people so that no matter what the arrangement of hats, only a finite number will incorrectly guess their hat color?For more check out his book Mathematical Puzzles: A Connoisseur's Collection.
Posted by Lance to Computational Complexity at 11/14/2006 05:02:00 PM