Friday, May 15, 2009

Fun Math Puzzles

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.

John Carrino said...

For #1, can the prisoners move the boxes around? Also do they know in what order they enter the room?

John Carrino said...

For problem 3, bumping is identical to passing through. The results at delta t of passing through is identical to that of bumping, so we can treat the system as though no lemming interaction is occuring at all. Stack them all up one one side and you get that each one spends an average time of length/velocity.

John Carrino said...

I like problem 4. Light string one from both end and string 2 at one end. When string 1 is completely burned (30 min), light the other end of string 2. String 2 will burn for 15 more minutes.

Yisong said...

For #1, the prisoners cannot move the boxes around and don't know their order.

John Carrino said...

So they can't communicate once the process begins and we can assume the room is reset to the ideal state after each leaves so no data is left behind?

Yisong said...

That's right.