Here are my favorite puzzles. I haven't been at all diligent about providing solutions, since the fun is in solving the puzzle. Sometimes, however, a hint about the solution makes the puzzle more interesting, so I provide some links to hints that might pique your curiosity.
![[ missing pebblerook.gif ]](pebblerook.gif)
Credit: Bob Holmes, sometime in the 1960's.
This game is played on an infinite chess board, and is parameterized by two numbers, P and R. In the course of one turn, one player -- the Pebble Placer -- places P pebbles on P squares of the chess board, and then his adversary, the Rook Driver, moves a rook up or down in its present column, or right or left in its present row, by any number of squares from 1 to R inclusive. Once placed on the board, pebbles stay forever, and on every move, the Pebble Placer gets P fresh pebbles to place. The rook is not allowed to cross squares with pebbles, nor to occupy them. The Pebble Placer wins when there are pebbles on the four squares adjacent to the rook, in which case the rook cannot make a legal move.
The puzzle is to find values of P and R for which the game is interesting. For example, values of P greater than 3 are obviously uninteresting, since the Pebble Placer will trap the rook on the first move. One can also discover pretty quickly that the P=3 case is not very challenging, no matter how large the rook's range, R, is.
If this seems too easy to pique your interest,
perhaps this additional
information will help.
![[ missing swimrun.gif ]](swimrun.gif)
Credit: Josh Jaffe, circa 2002.
Sam is swimming in a circular lake. Rosa is running around the shore, hoping to catch Sam. Rosa can't chase Sam into the water, because she is carrying a chainsaw, which would make swimming hard, and the water would make the engine stall. If Sam can reach some point on the shore before Rosa, he can run to safety, and Rosa can't catch him, because she can't run so fast, carrying the chainsaw. But Rosa, carrying the chainsaw, can run X times faster than Sam can swim, so she's trying to ensure that whenever Sam approaches a point on the shore, she's there first, with the chainsaw.
If X is very large, Sam is doomed: he can't reach any point on the shore before Rosa. If X is small, Sam can escape. What is the largest value of X for which Sam can construct a sure-fire strategy for escape?
If you want to compare your answer with mine,
look here.
I take a deck of N blank index cards, and write numbers on them. Then I shuffle the deck, and present it to you face down. Your goal is to turn the cards over, one at a time, and stop immediately after turning over the card with the highest number. Obviously, no strategy will guarantee success; but what strategy maximizes the chance of winning?
What makes this puzzle interesting is that you have no idea of the distribution of values on the card. What's more, I might try to mislead you by using numbers from a distribution that I think you don't expect: for example, when the first card has "-100000000", you might think that's a pretty low number, and continue, only to find that the other cards have "-10^10^10", "-10^10^10^10", and so forth. You do, however, have a guarantee that I have shuffled the deck fairly.
This is also called the "wife choosing problem"
or "secretary hiring problem", since those two
situations also involve selecting an element from a
population whose distribution is (largely) unknown,
in a context where backing up is difficult.
(To do: credit the inventor. This puzzle turned up around 2002.)
The popular way of presenting this puzzle has me putting randomly selected hats on the heads of people sitting around a table. Unfortunately, that simple presentation ends up in a mire of speculation about information leaks and communications channels. So:
There is a team of N cooperating players. Each player is put into an isolation room. I mark the outside of the door of each room with a white mark or a black mark, chosen randomly on the basis of a coin flip. I then slip under the door of each room a paper revealing the colors of the marks on all the other doors. Each player then slips back under the door a ballot on which he may guess the color of the mark on his own door, the options being (1) white, (2) black, or (3) no guess. The team wins if at least one player guesses the color of his door correctly and no player guesses the wrong color.
The players are allowed to collaborate beforehand to agree upon a strategy, but once the game has begun, no communication is possible.
This puzzle is fun because it's obvious that anybody guessing his color has exactly a 50% chance of being right. Nonetheless, with the right strategy, the team's chance of winning is greater than 50%, and increases as the number of players increases.
Not sufficiently intrigued? What if I told you
this?
(I heard this from Susan Langford in 2006.)
In this game, a group of 100 people work together. They assemble in Waiting Room A and plan their strategy. One by one, they are taken into the Examination Room, where their 100 names have been written on 100 index cards that have been fairly shuffled and have been laid face-down on a table. Each player turns over 50 of the index cards. We note whether or not he turned over the card with his name, then we restore the cards to their original face-down orientations in their original positions and send the player to Waiting Room B, where he cannot communicate with the players in Waiting Room A.
The players win or lose as a team. They win if every player turns over the card with his name.
This puzzle is fun because it's obvious that each player has
exactly a 50% chance of turning over the card with his name,
so one would guess that the team's chance of winning cannot
be much better than 2^-100. But in fact, a team following
a good strategy has about a 30% chance of winning. What's
more, that chance of winning stays pretty much constant
for any large (even) number of players, each turning
over half the cards.
A cable of 26 wires passes under a freeway. Unfortunately, the wires all look alike, so you don't know which end on the north side of the freeway connects to which end on the south side of the freeway. Your predecessor randomly labelled the north ends with letters A through Z, and randomly labelled the south ends with numbers 1 through 26, but then was killed while trying to cross the freeway to figure out the mapping between the numbers and the letters.
Your job is to find the mapping and record it by filling out a table of the form "A=21, B=6, ..." You have a continuity tester (goes buzz when its probes are electrically connected) and the ability to connect the ends of the wires by twisting them together. What is the smallest number of crossings of the freeway sufficient to complete the job?
I think the answer is surprisingly
small.
(The Opaque Square problem)
Given a square whose sides are of length 1 unit, we want to build a fence in such a way that any line that intersects the square also intersects the fence. (We're using "line" in the geometric sense, so it extends forever in two directions.) What is the smallest length of fencing sufficient to accomplish this goal?
Restated: Given a square field and the ability to dig trenches, what is the least amount of trench-digging sufficient to guarantee that the line segment connecting two points on different sides of the field must cross a trench?
Progressive hints: Clearly, length 4 is sufficient.
Almost equally clearly, length 3 is sufficient.
Other approaches give lengths of
2.732, 2.707, and 2.64.
2007-10-13
My email address: