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?
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