Your favourite maths puzzles

Okay, so this question was bound to come up sooner or later- the hope was to ask it well before someone asked it badly...

We all love a good puzzle

To a certain extent, any piece of mathematics is a puzzle in some sense: whether we are classifying the homological intersection forms of four manifolds or calculating the optimum dimensions of a cylinder, it is an element of investigation and inherently puzzlish intrigue that drives us. Indeed most puzzles (cryptic crosswords aside) are somewhat mathematical (the mathematics of sudoku for example is hidden in latin squares). Mathematicians and puzzles get on, it seems, rather well.

But what is a good puzzle?

Okay, so in order to make this question worthwhile (and not a ten-page wadeathon through 57 varieties of the men with red and blue hats puzzle), we are going to have to impose some limitations. Not every puzzle-based answer that pops into your head will qualify for answerhood- to do so it must

• Not be widely known: If you have a terribly interesting puzzle that motivates something in cryptography; well done you, but chances are we've seen it. If you saw that hilarious scene in the film 21, where kevin spacey explains the monty hall paradox badly and want to share, don't do so here. Anyone found posting the liar/truth teller riddle will be immediately disemvowelled.
• Be mathematical: as much as possible- true: logic is mathematics, but puzzles beginning 'There is a street where everyone has a different coloured house...' are much of a muchness and tedious as hell. Note: there is a happy medium between this and trig substitutions.
• Not be too hard: any level is cool but if the answer requires more than two sublemmas, you are misreading your audience
• Actually have an answer: crank questions will not be appreciated! You can post the answers/hints in Rot-13 underneath as comments as on MO if you fancy.

And should

• Ideally include where you found it: so we can find more cool stuff like it
• Have that indefinable spark that makes a puzzle awesome: a situation that seems familiar, requiring unfamiliar thought...

For ease of voting- one puzzle per post is bestest.

Some examples to set the ball rolling

Simplify $\sqrt{2+\sqrt{3}}$

From: problem solving magazine

Hint:

Try a two term solution

Can one make an equilateral triangle with all vertices at integer coordinates?

From: Durham distance maths challenge 2010

Hint:

This is equivalent to the rational case

nxn Magic squares form a vector space over $\mathbb{R}$ prove this, and by way of a linear transformation, derive the dimension of this vector space.

From: Me, I made this up (you can tell, can't you!)

Hint:

Apply the rank nullity theorem

Happy puzzling!

Solution 1:

The Blue-Eyed Islander problem is one of my favorites. You can read about it here on Terry Tao's website, along with some discussion. I'll copy the problem here as well.

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

[For the purposes of this logic puzzle, "highly logical" means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.]

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

One evening, he addresses the entire tribe to thank them for their hospitality.

However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

What effect, if anything, does this faux pas have on the tribe?

Solution 2:

Here are three of my favorite variations on the hats and prisoners puzzle that I've collected over time:

1. Fifteen prisoners sit in a line, and hats are placed on their heads. Each hat can be one of two colors: white or black. They can see the colors of the people in front of them but not behind them, and they can’t see their own hat colors. Starting from the back of the line (with the person who can see every hat except his own), each prisoner must try to guess the color of his own hat. If he guesses correctly, he escapes. Otherwise, he is fed to cannibals (because that’s the canonical punishment for failing at hat problems). Each prisoner can hear the guess of each person behind him. By listening for painful screaming and the cheering of cannibals, he can also deduce if each of those guesses was accurate. Of course, this takes place in some magical mathematical universe where people don’t cheat. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. (The cannibals should eat no more than one prisoner.)

2. In the year 3141, Earth’s population has exploded. A countably infinite number of prisoners sit in a line (there exists a back of the line, but the other end extends forever). As in the previous problem, white and black hats are placed on their heads. Due to modern technology, each person can see the hat colors of all infinitely many people in front of them. However, they cannot hear what the people behind them say, and they do not know if those people survive. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. Assume that there are enough cannibals to eat everyone who fails. (The cannibals should eat no more than finitely many prisoners. Assume the Axiom of Choice.)

3. There are seven prisoners, and colored hats will be placed on their heads. The hats have seven possible colors (red, orange, yellow, green, blue, indigo, violet), and may be placed in any arrangement: all the same color, all different colors, or some other arrangement. Each person can see everyone else’s hat color but cannot see his own hat color. They may not communicate after getting their hats, and as in the previous problems, they remain in a magical universe where no one cheats. They must guess their hat colors all at the same time. If at least one person guesses correctly, they are all released. If no one guesses correctly, however, the entire group is fed to cannibals. Assuming that they don’t want to be eaten, find the optimal guessing strategy for the prisoners. (By this point, the cannibals have probably eaten far too much. It would be cruel to force them to eat any more, so spare the cannibals and find a way to guarantee that the seven prisoners survive.)

Solution 3:

A probability problem I love.

Take a shuffled deck of cards. Deal off the cards one by one until you reach any Ace. Turn over the next card, and note what it is.

The question: which card has a higher probability of being turned over, the Ace of Spades or the Two of Hearts?

Solution 4:

Most of us know that, being deterministic, computers cannot generate true random numbers.

However, let's say you have a box which generates truly random binary numbers, but is biased: it's more likely to generate either a 1 or a 0, but you don't know the exact probabilities, or even which is more likely (both probabilities are > 0 and sum to 1, obviously)

Can you use this box to create an unbiased random generator of binary numbers?

Solution 5:

The odd town puzzle.

You have a town with $m$ clubs formed by $n$ citizens of the town.

The clubs are so formed that

• Each club has an odd number of members.
• Any two clubs have an even number of common members. (Could be zero too).

Show that $m \le n$.