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!

-
I have a feeling that this thread is going to waste so much of my time –  Casebash Jul 23 '10 at 12:45
I wrote a book (in Italian) with 99 such puzzles :-) –  mau Jul 23 '10 at 12:54
See also mathoverflow.net/posts/29519 - I'll copy the puzzles I posted there to give this thread a start. –  BlueRaja - Danny Pflughoeft Jul 23 '10 at 15:38
@BlueRaja- please read the question. –  Tom Boardman Jul 23 '10 at 17:20
Rot13 translator: rot13.com/index.php –  Pierre-Yves Gaillard Aug 12 '10 at 17:53

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?

-
+1. A very interesting puzzle. –  Nate Eldredge Oct 5 '10 at 18:02

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.)

-
In puzzle 2, the prisoners can significantly improve their expected survival if they're able to hear each other's 'guesses'. –  Egbert May 27 '12 at 13:44
Sbe gur guveq bar, gur cevfbaref pna rnpu nffhzr gung gur gbgny nzbat nyy bs gurz zbq frira vf fbzr svkrq ahzore, naq thrff nppbeqvatyl. Nf ybat nf rnpu cevfbare vf nffvtarq n qvssrerag svkrq ahzore zbq frira, rknpgyl bar cevfbare vf thnenagrrq gb thrff pbeerpgyl. Vf gurer n orggre fgengrtl? –  Dustan Levenstein May 29 '12 at 21:04
Bs pbhefr, orggre vf fhowrpgvir. V zrnag bar va juvpu fbzrgvzrf zber guna bar crefba thrffrf pbeerpgyl. –  Dustan Levenstein May 29 '12 at 21:36
I think this should work: Gur ynfg cevfbare va yvar (gur svefg gb thrff) fnlf "oynpx" vs gurer ner na bqq ahzore bs oynpx ungf, naq "juvgr" vs gurer ner na rira ahzore bs oynpx ungf. (Ur pna'g or urycrq naljnl.) Gur arkg cevfbare gb thrff frrf ubj znal oynpx ungf gurer ner, abg pbhagvat uvf. Vs gur cnevgl zngpurf, uvf ung zhfg or juvgr; vs vg qbrfa'g zngpu, uvf ung zhfg or oynpx. Gura gur arkg cevfbare qbrf gur fnzr, xabjvat gung gur cerivbhf cevfbare'f thrff jnf pbeerpg. Nq vasvavghz. [translate] –  WChargin Feb 27 '14 at 5:18
I told the first puzzle to a friend, and he came up with this solution: Gur svefg thrffre fnlf gur pbybe bs gur ung va sebag bs uvz. Rirel fhofrdhrag cevfbare ybbxf ng gur ung qverpgyl va sebag bs uvz. Vs gur ung vf juvgr, ur jnvgf svir frpbaqf orsber fnlvat uvf bja ung pbybe; vs vg vf oynpx, ur fnlf vg vzzrqvngryl. I think it's a very clever solution, but is it allowed under the scope of the problem? It introduces another "dimension" of sorts. –  WChargin Feb 28 '14 at 17:29

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?

-
V pnyphyngrq gur ahzore bs cbffvovyvgvrf sbe obgu, naq vg ybbxf gb zr yvxr gurl'er gur fnzr. V'z fher gurer'f n terng rkcynangvba ohg V'z abg frrvat vg evtug abj. –  Ben Alpert Jul 25 '10 at 3:32
Lbh'er evtug, naq gurer'f n terng rkcynangvba. Jurer fubhyq V jevgr vg hc? Nf nabgure pbzzrag? –  Edan Maor Jul 25 '10 at 6:25
Yes, please –  BlueRaja - Danny Pflughoeft Sep 8 '10 at 7:26
I'm not sure I understand the statement. Are we counting all the cards dealt as "turned over", or just the final card (the one that we explicitly note)? And do we stop with the first ace we hit? Or can we stop on any ace of our choosing? –  Aaron May 10 '11 at 1:20
@Aaron: the dealing stops with the first ace, whichever it may be. Only the card after this first ace is 'turned over' and its value noted. –  ThudanBlunder May 10 '11 at 17:00

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$.

-
Hint: Yvarne Vaqrcrqrapr –  Aryabhata Aug 12 '10 at 20:08

From Mathematical Puzzles by Peter Winkler:

Divide an hexagon in equilateral triangles, like in the figure. Now fill all the hexagon with the three kinds of diamonds made from two triangles, also shown in the figure. Prove that the number of each kind of diamond is the same.

-
One answer (from Proof Without Words book): gurmeetsingh.files.wordpress.com/2008/10/calissons.png –  Ben Alpert Jul 23 '10 at 13:58
Peter Winkler's two books of mathematical puzzles are a rich source of problems satisfying all requirements of this thread. I recommend them highly, they are not your usual rehash of well-known chestnuts. –  user115 Jul 23 '10 at 23:11
@Ben - This solution is just awesome! –  Pandora Jan 8 '11 at 13:51

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?

-
Are the probabilities between each successive generation of random numbers constant? –  Justin L. Jul 23 '10 at 18:53
@Justin: Yes~~~ –  BlueRaja - Danny Pflughoeft Jul 23 '10 at 19:34
Probably not the fastest way: Trarengr cnvef bs qvtvgf. Vagrecerg n bar sbyybjrq ol mreb nf n bar. Vagrecerg n mreb sbyybjrq ol n bar nf n mreb. Vs gur gjb ahzoref jrer gur fnzr, qvfpneq gurz naq trarengr gjb zber ahzoref. –  Larry Wang Jul 24 '10 at 18:21
Kaestur Hakarl: That's the fastest way that I know of. –  Ben Alpert Jul 25 '10 at 3:18
I think this problem is a bit too well-known. en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin –  Fixee May 9 '11 at 22:43

unknown source:

Could the plane be colored with two different colors (say, red and blue) so that there is no equilateral triangle whose vertices are all of the same color?

-
I think this is a fairly common kind of olympiad question. Nice though –  Casebash Jul 23 '10 at 13:17
If the size is fixed, it's easy to create a tiling that prevents finding a monochromatic triangle, but if I remember correctly, the answer is unknown in the general case. –  Ben Alpert Jul 23 '10 at 14:00
I don't understand the question: what's colored? Real-points? Integer-points? Grid-sections? –  BlueRaja - Danny Pflughoeft Sep 8 '10 at 7:29
all points in the plane, so real points. –  mau Sep 8 '10 at 8:21

Assuming you have unlimited time and cash, is there a strategy that's guaranteed to win at roulette?

-
My friend gave me a great alternative to the standard znegvatnyr-l fbyhgvba yesterday - ohl gur pnfvab! –  Larry Wang Jul 25 '10 at 19:20
If you have unlimited time and cash, then just keep playing until you're ahead. It'll happen eventually. I must be misunderstanding. –  MatrixFrog Sep 8 '10 at 4:44
@MatrixFrog: Why do you think it will happen eventually? You cannot use the same reasoning as the 1-dimensional walk, since the odds of winning are not 50/50 –  BlueRaja - Danny Pflughoeft Sep 8 '10 at 7:23
@MatrixFrog: Actually, since the expected value from a given spin is actually negative (because of the 0 and 00), if you be the same amount of money each time, it would not be guaranteed that you would get ahead ever. –  yrudoy Oct 7 '10 at 1:13
@Ross Millikan: I'm not sure you understand the strategy. This is assuming you lose most of the time. When you finally do win, you will be at +1. Then you repeat, and when you finally win for the second time, you are at +2. This is NOT relying on properties of random walks. This is relying on unbounded, geometrically increasing bet sizes to compensate for losses. The gambler's ruin is that this strategy (or any other) will eventually crash if you have a finite bank roll. –  Aaron Aug 6 '11 at 6:29

You're once again at a fork in the road, and again, one path leads to safety, the other to doom.

There are three natives at the fork. One is from a village of truth-tellers, one from a village of liars, one from a village of random answerers. Of course you don't know which is which.

Moreover, the natives answer "pish" and "posh" for yes and no, but you don't know which means "yes" and which means "no."

You're allowed to ask only two yes-or-no questions, each question being directed at one native.

-
Nfx ivyyntre 1: "Vs V unq pbzr nybat naq nfxrq lbh 'vf ivyyntre 2 n enaqbz-nafjrere,' jbhyq lbh unir nyfjrerq 'cvfu'? Vs nafjre 'cvfu', nfx ivyyntre 3, vs 'cbfu,' nfx ivyyntre 2: "Vs V unq pbzr nybat naq nfxrq lbh 'vf cngu 1 jnf fnir', jbhyq lbh unir nafjrerq 'cvfu'? Vs nafjre 'cvfu', cngu 1 vf fnsr, bgurejvmr cngu 2 vf fnsr. –  yrudoy Oct 13 '10 at 16:29

Quite simply, a monkey's mother is twice as old as the monkey will be when the monkey's father is twice as old as the monkey will be when the monkey's mother is less by the difference in ages between the monkey's mother and the monkey's father than three times as old as the monkey will be when the monkey's father is one year less than twelve times as old as the monkey is when the monkey's mother is eight times the age of the monkey, notwithstanding the fact that when the monkey is as old as the monkey's mother will be when the difference in ages between the monkey and the monkey's father is less than the age of the monkey's mother by twice the difference in ages between the monkey's mother and the monkey's father, the monkey's mother will be five times as old as the monkey will be when the monkey's father is one year more than ten times as old as the monkey is when the monkey is less by four years than one seventh of the combined ages of the monkey's mother and the monkey's father.

If in a number of years equal to the number of times a monkey's mother is as old as the monkey, the monkey's father will be as many times as old as the monkey as the monkey is now, and assuming no a priori knowledge of the monkeys' longevity, find their respective ages. :-D

-
This is why mathematical notation is so useful –  BlueRaja - Danny Pflughoeft Sep 8 '10 at 7:31
I have managed to solve this problem. Turns out there is a solution only if the father is older than the mother. I can email it to anybody who is interested. –  ThudanBlunder Oct 29 '10 at 14:31
I get monkey=3, mother=24 and father=25. Did you come to the same result? –  wnvl Apr 9 '12 at 14:29

From New Scientist some years ago: 20 teams play a round robin tournament, each gets 1 point for a win, 0 for a loss, and there are no ties. Each team's score is a square number. How many upsets occurred? An upset is defined as team A defeating team B where B scored more total points than A.

-
Assuming there is a unique answer makes this problem so much easier… –  ShreevatsaR May 9 '11 at 22:36

If you have 32 2x1 dominoes then you can cover an 8x8 board easily enough; if you throw away a domino and cut a 1x1 square from each end of a diagonal of the board, can you cover the remaining shape with the remaining dominoes?

I heard this decades ago at university.

-
From dmuir: Ab, orpnhfr vs vg jrer n purffobneq, rnpu qbzvab pbiref n oynpx fdhner naq n juvgr fdhner, juvyr lbh unir phg bss gjb fdhnerf bs gur fnzr pbybhe. –  Sparr Oct 7 '10 at 0:11
@Sparr please try to obfuscate answers a little more even in rot13. "Ab" at the beginning of an answer is pretty obvious. –  WChargin Feb 28 '14 at 23:43
@WChargin are you suggesting that you can visually/quickly read rot13? if not, then I don't understand your objection. if so, that's awesome, but I think you're enough of an outlier that I am not compelled to change to accommodate your abilities. –  Sparr Mar 1 '14 at 2:55
@Sparr well I know that the middle of the alphabet is "m", so "a" maps to "n", and then logically "b" must map to "o"... that much is pretty much immediate but no I certainly can't "read" it normally. –  WChargin Mar 1 '14 at 4:58

You are on the surface of a cube, starting at the midpoint of one of the edges. Which point(s) on the cube is furthest away from you if you are constrained to travel on the surface of the cube?

-
Gur nafjre vf gur cnve bs cbvagf bar guveq naq gjb guveqf bs gur jnl nybat gur bccbfvgr rqtr. –  Henry May 10 '11 at 1:30

Prove that any 2-coloring of a $K_6$ has two monochromatic $K_3$'s.

-

Relatively simple, but still fun...

Unknown source, other than my friend telling me yesterday

There is a room with 50 doors in it, each door leading to a cell that is completely sound-proof and light-proof, and each cell can hold a maximum of 1 person. There are 50 prisoners. There also exists a light in the middle of the main room, so that when a prisoner is pulled out of their cell, they could see the light. There is also a light switch inside the main room which controls the light. The 50 prisoners are the only people allowed to touch the light switch that controls the light (even the prison guard cannot touch it)

Before any prisoner is placed in the cells, the prison guard tells them that he will pull out, at random, any one of them at any time, and then put them back in their cell after they get a chance to turn the light on or off or do nothing at all to it. (Only one prisoner can be out of their cell at any given time) He also guarantees them that he will pull at least one prisoner out at least once a day.

The goal is, when any one prisoner knows when all 50 prisoners have been pulled out of their cells at least one time, and he tells the prison guard this fact correctly, all prisoners will be let free.

The prisoners are allowed one short meeting before they all get placed in their cells.

They also have a (reasonably) infinite amount of time to let the prison guard know when all prisoners have been let out of their cells at least one time. (say 5 years or something to that effect)

There is only one guess allowed ever, so it better be the right answer, or else they will all be fed to the cannibals.

What method did they come up with to know exactly when all 50 prisoners have been out of their cells at least one time?

-
Hint: Guvax ovanel... –  Sev Sep 8 '10 at 18:49
This looks similar to math.stackexchange.com/questions/116340/…. –  Dustan Levenstein May 30 '12 at 17:02

A personal favorite (albeit not ideally-worded): Jamie has a windowbox where he plants a row of iris flowers. He plants in just two colors - blue and yellow - but never plants two yellow irises next to each other (the result is just too garish). Assuming that he wants to keep the same number of flowers in his box every day, how many flowers will he need if he wants a different arrangement of blue and yellow every day for a year?

-

A regular tetrahedron and a regular square pyramid both have unit length. If a triangular face of the tetrahedron is glued to a triangular face of the square pyramid, the resulting shape has how many edges?

-
The answer is not 8 + 6 - 3 = 11 –  ThudanBlunder May 15 '11 at 10:18

Is it possible to divide a circle into a finite number of congruent parts some of which don't touch the center?

-

Frk n th rd 1

Y'r n pth n n slnd, cme t frk n th rd. Bth pths ld t vllgs f ntvs; th ntr vllg thr lwys tlls th trth r lwys ls (bth villgs cld b trth-tllng r lyng vllgs, r n f ch). Thr r tw ntvs t th frk - thy cld bth b frm th sm vllg, r frm dffrnt vllgs (s bth cld b trth-tllrs, both lrs, r ne f ch).

n pth lds t sfty, th thr t dm. Y'r llwd t sk nly n qstn t ch ntv t fgr t whch pth s whch.

Wht d y sk?

-
See the question and this wikipedia link on disemvowelling for an explanation: en.wikipedia.org/wiki/Disemvowelling –  Tom Boardman Jul 23 '10 at 17:30
Seriously though, feel free to rollback. I just wanted to keep my promise. –  Tom Boardman Jul 23 '10 at 17:31
@Tom: I'm going to leave this for the lol's –  BlueRaja - Danny Pflughoeft Jul 23 '10 at 17:42
This is funny :-) –  Aryabhata Aug 12 '10 at 20:07

There is a square table with a pocket at each corner; in each pocket is a drinking glass, which you cannot see. Each glass might be right-side up ("up") or upside-down ("down").

You and an adversary will play the following game. You select exactly two of the pockets, withdraw the two glasses, thus learning their orientations. You then replace the glasses in their pockets, altering their orientations in any way you desire.

If at this point, all four glasses are oriented the same way, you win.

Otherwise, you look away, and the adversary rotates the table. All the pockets are indistinguishable, so you cannot tell what multiple of $\frac\pi2$ the table has been rotated.

Provide a strategy that is guaranteed to win in bounded time.

-

Not a mathematical puzzle in the classical sense, but it is an interesting variation on the men with hats problem. It has a much "quicker" solution which to some degree is a bit surprising. If you are willing to indulge me, I will also add a rich background story.

After Hilbert passed away in 1943 his grand hotel stood empty for some years until it was bought by a mad version of Stalin and was turned into a crazy prison for the infinitely many enemies of the state.

Several days later the prison is full, and Stalin being less-mathematically inclined than Hilbert decides that instead of moving all the prisoners he will execute them. Since mathematicians can be useful to the Soviet Union he decides to play a game.

He announces that in the morning of the next day every prison will be given a hat either black or white (but not both), and the prisoners will be standing in line by their room number, each seeing all those whose room number is larger. Without talking to each other they will have to guess whether or not they wear a white hat or a black hat. If someone guesses the correct color they go free, otherwise they have a meeting with the executioner.

The prisoners all meet at the dining room later that day and devise a strategy in which no infinite number of prisoners will die. What is it?