Following a day of fun in NYC (which included seeing KOOZA and visiting Yahoo! New York), I spent much of the five hour drive back to Ithaca exchanging fun math puzzles with Ymir. And so, what else could I do but share them here? Some of these are harder than others.
Problem 1. There are N prisoners (N even) and a sadistic warden. The warden places N boxes in a room, all identical except that each is labeled with a unique number from 1 to N. Each box contains exactly one of the prisoner's names (assume distinct names) and each prisoner's name is in one of the boxes (a bijection). When the game starts, each prisoner is allowed to open half of the boxes and observe the names. One cannot tell from observing the room which boxes had been opened previously. Afterward opening half the boxes, without communicating with any other prisoners, each prisoner must guess which box (i.e., which number) contains their name. If all the prisoners guess correctly, then they win and are set free. Devise a strategy such that the probability that all the prisoners win is bounded below away from zero (as N grows), or prove that one does not exist.
Problem 2. Suppose we have an NxN checkerboard, and suppose that two diagonally opposite corner tiles have been removed. Devise a way to exactly tile the remainder using 2x1 domino pieces, or prove that it is impossible to do so.
Problem 3. Suppose you are placing N lemmings on a flat and finite one dimensional surface (i.e., the lemmings can fall off the edges). All lemmings behave the same: they move at a fixed speed in their direction of travel (since this is a one dimensional surface, there are only two possible directions). If two lemmings bump into each other, then they both reverse their direction of travel. There are no other obstacles on this surface. You are allowed to control the initial position and direction of travel for each lemming. Devise a strategy that maximizes the total time that lemmings spend on the surface (i.e., the sum of the time that each lemming spends on the surface before falling off).
Problem 4. Suppose you have two strings of different length and an unlimited number of matches (as in, for burning). Each string burns in exactly one hour, but the burn rate of each string is non-uniform and unknown in advance. For example, one string might burn through 99% of its length in 1 minute and the remaining 1% in 59 minutes. Devise a way of counting 45 minutes using the two strings and the matches.