### Dr. Donald Simon

Graduate Director, Associate Professor of Computer Science
Mathematics and Computer Science
416 College Hall McAnulty College
600 Forbes Ave
Pittsburgh, PA 15282
Email: compmath@mathcs.duq.edu
Phone: 412.396.6472

A A Email Print Share

#### Set 1:

Hat Strategy

You are one of three prisoners held by a deranged but brilliant statistics professor. You are told that in a little while the three of you will be put to sleep; when you awake, each of you will be wearing either a white or black hat, where the color of each hat will be chosen by flipping a fair coin (heads is black). Each of you, knowing only the color of the other two hats but not your own, must then secretly write down either a color or "pass," and at least one of you must not pass. If each of the written colors matches the wearer's hat, then all of you will be set free; otherwise... What strategy should the three of you agree to use in order to maximize your chance of freedom?

Answer: If I see different colors of hats, I pass. If both hats I see have the same color, I write down the opposite color.

Isle of Blue Eyes

An anthropologist visits a small island where everyone is in daily contact with one another. The inhabitants, brilliant logicians, have a custom that anyone with blue eyes must leave the island forever at midnight of the day when they learn that they have blue eyes. However, the inhabitants are compassionate people and would never tell someone that they have blue eyes, and there are no mirrored surfaces on the island. The anthropologist, as she leaves, expresses to the assembled inhabitants her sadness, as she is sure that someone listening will someday learn that they have blue eyes and have to leave the island. What happens after she leaves, and when?

Answer: If N inhabitants have blue eyes, they will all leave on the Nth midnight after the anthropologist departs.

Four-Footed Bridge

Four people need to quickly cross a rickety wooden bridge over a deep ravine. The bridge can only hold two of them at once. Also, it is a pitch black night and the bridge is missing many floor planks; they have one flashlight that must be carried with whoever is crossing in order to avoid plunging into the ravine. Furthermore, some of them can move faster than others: Paul can get across in one minute, John takes two minutes, George takes five, and Ringo takes 10. How quickly can all four get safely across?

Open-and-Shut Case

You live alone on an island, and your friend, who lives on another island, calls to say that he is ill and needs the medicine that you have. There is one boat that travels between your islands several times each day, but its captain is not trustworthy: she will take anything that is not securely locked in the boat's treasure chest. This chest has a large clasp, and you have a lock that can be fastened to the loop of this clasp in order to secure the chest. Your friend also has his own lock that could similarly secure the chest. However, each of you only has a key to your own lock, and the keys do not fit the other locks. How can you safely get the medicine to your friend?

Answer: You lock the medicine in the chest. When the boat arrives at the other island, your friend adds their lock. You remove your lock when the boat returns to your island. Finally, when the boat is back at the other island, your friend removes their lock and takes the medicine.

Question Time

You find yourself in a room with two doors and two guards. You know that one of the guards always tells the truth and that the other always lies, but you do not know which is which. You also know that one door leads to freedom, the other to, well, something bad. You are allowed to ask one guard one question, after which you will be allowed to go through one door. What question should you ask?

Burning to Know

You are given two length of string and one match. Each string burns for exactly one minute, but they might not burn at a uniform rate (each might burn faster in some portions of the length, slower in others). Use these strings to measure a duration of 45 seconds.

Answer: Lay one string down in a circle with its ends touching. Lay the other string out in a line, with one end touching the point where the ends of the first string meet and the other end pointed away from the circle formed by the first string. At the point where the two strings meet, simultaneously light them both (including both ends of the first string). At the moment when the first string is completely burned, wrap the non-burning end of the second string back so that it is ignited by the burning end and what is left of the second string forms a circle. Exactly 45 seconds will elapse between the time when the strings are initially lit and the time when the second string is completely burned.

#### Set 2:

Check the Boxes

You are one of four prisoners held by a deranged but brilliant
statistics professor. To survive execution, each of you must pass a
test: each distinctly-named prisoner has a box with his name on it, and
each box contains a piece of paper with one of the four names written on
it. One by one, each of you must find his own paper by looking in at
most two boxes. You are not allowed to converse in between rounds. If
everybody passes, you are all set free; otherwise... What strategy
should the four of you agree to use in order to maximize your chance of
freedom?

Answer: Each prisoner first looks in the box with his own name on it. If his name is not in the box, then the second box he looks in
is the box with the name he found in the first box. This strategy succeeds with a probability of 5/12.

(This probability can be achieved even if the professor is aware of the strategy, as the prisoners can agree on a random permutation
of their names.)

Half and Half

Suppose you are given a rectangle, which a smaller rectangle completely
contained inside of it. The smaller rectangle need not have any sides
parallel to any of the sides of the larger. Devise a simple procedure
for cutting the area between the two rectangles perfectly in half. Your
procedure should not call for the calculation of any area.

Answer: Any line through the center of a rectangle will divide the rectangle in half, so it is sufficient to take the line that passes through the centers of the rectangles.

Getting Warmer?

The following statement is true: At any point in time, there exist two
points on the surface of the moon that are opposite (that is, the line
directly connecting them passes through the center of the moon) that
have the exact same temperature. Why is this true?

Answer: Here, we assume that the moon is a perfect sphere, and that temperature is a continuous function.)

Define the function f such that given any point on the moon, the value of f is the
temperature at that point minus the temperature at the opposite point. It suffices to show that
there exists a point such that f is zero.

Take any great circle (for example, the equator) around the moon. If f is always zero on this circle, the whole circle has the same temperature.
Otherwise, there is some point where this function has a positive value.
At the opposite point, the function has a negative value. By walking around the circle,
there must be a point where this function is zero, by the Intermediate Value Theorem.

Make it a Big One

Given ten seconds to write down a large number (using standard math
notation and/or English words), what would be your approach to maximize
the number written down? Your answer should be precise enough for any
reasonable modern mathematician to exactly compute, by consulting only
your card, and, if necessary, the published literature.

for a discussion by Scott Aaronson of MIT.

Winning Numbers

The presidential elections are to be held in Anchuria. Of 20,000,000
voters only 1 percent (i.e. the regular army) support the current
president Wobushko. He wants to be re-elected in a democratic way, which
means the following. All voters are split into n1 groups, all of equal
size. Then each group can be split into n2 smaller sub-groups of equal
size, where n2 is the same for all groups. Then each subgroup is split
into n3 equal sub-sub-groups, and so on. Each (sub)i-group chooses by
majority rule one representative to represent it at level i-1, and so
on. (If there is a tie, the opposition wins.) Can Wobushko organize the
groups and distribute his supporters so that he wins the elections?

Answer: Yes. 20,000,000 factors as 4^4*5^7. Starting with the group of all voters, the election will be structured by splitting
each group of voters into 5 groups seven times, then each group into 4 groups three times.

Wobushko needs 3 representatives at the first level to win the election. To ensure this, Wobushko needs 3*3=9 representives at the second level, 9*3=27 representative at the third level, etc.
Wobushko can win with 3^11 = 177,147 < 200,000 supporters.

This puzzle was taken from http://www.cs.cmu.edu/puzzle/index.html

Position that Pays

Two players alternatively erase some 9 numbers from the sequence 1,2,...,101 until only two remain. The player that starts wins x-54 dollars from the player that plays second. Here x is the difference between the remaining two numbers. Would you rather be the first or the second player?

Answer: The first player has a strategy that guarantees that she will win at least 1 dollar.
On the first turn, the first player erases 47 through 55.
The remaining 92 numbers can be put into 46 pairs: {1,56},{2,57},...,{46,101}. Each pair contains two numbers that differ by 55.
The first player responds to the second player by ensuring that only pairs of this form remain after each turn of the first player.
(If the second player erases both numbers in such a pair in a single turn, the first player erases an arbitrary pair.)
This strategy for the first player guarantees that the remaining two numbers differ by 55.