126
$\begingroup$

You're hanging out with a bunch of other mathematicians - you go out to dinner, you're on the train, you're at a department tea, et cetera. Someone says something like "A group of 100 people at a party are each receive hats with different prime numbers and ..." For the next few minutes everyone has fun solving the problem together.

I love puzzles like that. But there's a problem -- I running into the same puzzles over and over. But there must be lots of great problems I've never run into. So I'd like to hear problems that other people have enjoyed, and hopefully everyone will learn some new ones.

So: What are your favorite dinner conversation math puzzles?

I don't want to provide hard guidelines. But I'm generally interested in problems that are mathematical and not just logic puzzles. They shouldn't require written calculations or a convoluted answer. And they should be fun - with some sort of cute step, aha moment, or other satisfying twist. I'd prefer to keep things pretty elementary, but a cool problem requiring a little background is a-okay.

One problem per answer.

If you post the answer, please obfuscate it with something like rot13. Don't spoil the fun for everyone else.

$\endgroup$
8
  • 3
    $\begingroup$ Since I see this has accumulated a couple of votes to close, I've started a meta thread: tea.mathoverflow.net/discussion/471/math-puzzles-for-dinner $\endgroup$ Jun 24, 2010 at 16:00
  • 2
    $\begingroup$ It's easy to forget the question, read one of the problems below, then write down an answer... $\endgroup$ Jun 25, 2010 at 0:28
  • 15
    $\begingroup$ Out of curiosity, is there a way of posting hidden text in answers that can be revealed by clicking on "Hidden Text?" (kind of like on Art of Problem Solving forums). $\endgroup$
    – Alex R.
    Jun 26, 2010 at 1:53
  • 2
    $\begingroup$ I find it a bit odd that there is a bounty on a CW. Can we discuss this on meta? $\endgroup$ Jul 25, 2010 at 14:46
  • 10
    $\begingroup$ Am I the only person who goes to social events with mathematicians and drinks, banters and has pointless debates about politics or films? $\endgroup$
    – Yemon Choi
    Feb 2, 2011 at 3:02

67 Answers 67

54
$\begingroup$

I really like the following puzzle, called the blue-eyed islanders problem, taken from Professor Tao's blog :

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

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?"

For those of you interested, there is a huge discussion of the problem at http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/

Malik

$\endgroup$
6
  • 3
    $\begingroup$ I have heard the following, politically less correct, version of this: A cruel custom on an island demands that every husband kills his wive at midnight if informed that she has cheated on him. All inhabitants of the island are married and all cheat. A newly arrived priest has heard of this scandalous lifestyle and, during his sermon, announces to the whole tribe that at least one (and thus at least two) inhabitant has been unfaithful. $\endgroup$ Jun 24, 2010 at 14:13
  • 6
    $\begingroup$ The wikipedia link in the blog post is quite a revelation. $\endgroup$ Jun 24, 2010 at 19:28
  • 1
    $\begingroup$ I remember the blue-eyed islanders puzzle fondly from my teenage years, so about 20 years ago now. I am pretty sure it is not due to Prof. Tao. In fact I wonder is its provenance can be tracked down. (A version appears early on in Spivak's Calculus, for instance...) $\endgroup$ Jun 26, 2010 at 17:29
  • 1
    $\begingroup$ What's the point here? Obviously, no effect: the islanders already know that there are many people with blue eyes on the island. Even if they do not know statistics, they know that such people exist there. $\endgroup$
    – Anixx
    Jan 28, 2011 at 14:11
  • 2
    $\begingroup$ @Anixx: Well that is the interesting thing, and why this problem is popular. At first glance "no effect" seems to be right, but after some thought, we can deduce that all the blue eyed people kill themselves after a some number of days. $\endgroup$ Mar 6, 2011 at 23:55
46
$\begingroup$

You and infinitely many other people are wearing hats. Each hat is either red or blue. Every person can see every other person's hat color, but cannot see his/her own hat color; aside from that, you cannot share any information (but you are allowed to agree on a strategy before any of the hats appear on your heads). Everybody simultaneously guesses the color of his/her hat. You win if all but finitely many of you are right. Find a strategy so that you always win.

$\endgroup$
10
  • 1
    $\begingroup$ As I recall, the number of hat colors can be arbitrary...? I guess it's better to state this version because if it sounds too impossible people will get suspicious and might catch on faster. $\endgroup$ Jun 24, 2010 at 5:12
  • 6
    $\begingroup$ @Qiaochu: yes, that's true. A variant where it's important to have two colors: you win if everybody is right or everybody is wrong. $\endgroup$ Jun 24, 2010 at 5:15
  • 4
    $\begingroup$ The solution to this problem can be turned into a strategy to predict the future (!?). It was nicely explained in a nice article on the American Mathematical Monthly, of which I forgot the title. Sadly the strategy is not effective... $\endgroup$ Jun 24, 2010 at 13:29
  • 6
    $\begingroup$ @Andrea: The name of the article is A Peculiar Connection Between the Axiom of Choice and Predicting the Future by Hardin and Taylor. You can access the article by clicking on the link from Francois G. Dorais' answer to this question $\endgroup$
    – Tony Huynh
    Jun 24, 2010 at 15:07
  • 5
    $\begingroup$ This is one of my favorites. I've always liked the mental image of the players sitting around beforehand and nterrvat ba n pubvpr shapgvba. $\endgroup$ Jun 24, 2010 at 19:13
43
$\begingroup$

You are blindfolded, then given a deck of cards in which 23 of the cards have been flipped up, then inserted into the deck randomly (you know this). Without taking the blindfold off, rearrange the deck into two stacks such that both stacks have the same number of up-flipped cards. (You are allowed to flip as many cards as you please.)

$\endgroup$
12
  • 2
    $\begingroup$ I really like this one. I heard it a few years ago, and remembered my solution because it was neat. However, I had forgotten the question (and have been intermittently searching the internet for it) until now. Thanks! (It is a bad thing to have an answer without a question floating around in your head!) $\endgroup$
    – ADL
    Jun 24, 2010 at 14:40
  • 3
    $\begingroup$ @Roland: Each stack contains the same number of up-flipped cards, not necessarily 11.5 (in fact, definitely not, as ripping cards is destructive). – Kiochi 0 secs ago $\endgroup$
    – Kiochi
    Jun 24, 2010 at 16:53
  • 2
    $\begingroup$ @Kiochi: you really should mention this in the answer. I've edited it for you, hope that's okay! $\endgroup$
    – Vectornaut
    Jun 24, 2010 at 18:15
  • 5
    $\begingroup$ This thread is killing me. Won't anyone post the answers? $\endgroup$
    – Olivier
    Jun 25, 2010 at 8:20
  • 6
    $\begingroup$ Yes, you're right -- I just hadn't figured out how to adapt the solution for 26 to other numbers: Qvivqr gur qrpx vagb bar cvyr bs fvmr gjragl-guerr naq bar cvyr bs fvmr gjragl-avar. Abj ghea gur svefg cvyr hcfvqr-qbja. (Naq bs pbhefr 23 vf neovgenel urer.) $\endgroup$
    – JBL
    Jun 28, 2010 at 1:27
41
$\begingroup$

1000 prisoners are in jail. There's a room with 1000 lockers, one for each prisoner. A jailer writes the name of each prisoner on a piece of paper and puts one in each locker (randomly, and not necessary in the locker corresponding to the name written on the paper!).

The game is the following. The prisoners are called one by one in the room with the lockers. Each of them can open 500 lockers. If a prisoner finds the locker which contains is name, the game continues meaning that he leaves the room (and leaves it is the exact same state as when it entered it, meaning that he cannot leave any hint), and the following prisoner is called. If anyone of the prisoners fails to recover his name, they all lose and get killed.

Of course they can agree before the beginning of the game on a common strategy, but after that, they cannot communicate anymore, and they cannot leave any hint to the following prisoners.

A trivial strategy where each prisoner opens 500 random lockers would lead to a winning probability of 1/2^1000. But there exists a strategy that offers a winning probability of roughly 30%.

$\endgroup$
5
  • 8
    $\begingroup$ This is also a very beautiful puzzle. As to the context, I'prefer to tell it in a less violent fashion: let's say that the director of a private prison offers a free Thanksgiving dinner to his clients if they succeed to win the game. On the mathematical side, there is a less known but very nice additional part: prove that the solution is indeed optimal: no other strategy gives better chances of winning. $\endgroup$ Jun 24, 2010 at 17:59
  • 1
    $\begingroup$ This is a very nice puzzle. Of course, computing that winning probability requires some calculation, but finding the strategy is beautiful math. $\endgroup$
    – Tara Holm
    Jun 25, 2010 at 15:09
  • 1
    $\begingroup$ I love this puzzle too. I first read it on madore.org/~david/weblog/2006-11.html#d.2006-11-20.1390 which also lists a few more well-known puzzles. $\endgroup$ Jun 25, 2010 at 22:09
  • 3
    $\begingroup$ @Pietro: but that's half the fun, free dinner doesn't motivate a good strategy like the guillotine does. $\endgroup$ Dec 7, 2010 at 23:59
  • 1
    $\begingroup$ This may be pedantic, and is definitely very late, but it is important that the lockers are labeled. If the prisoners are unable to tell different lockers apart then the (very pretty) solution doesn't work. $\endgroup$ Jul 27, 2011 at 2:51
40
$\begingroup$

There are $n$ balls rolling along a line in one direction and $k$ balls rolling along the same line in the opposite direction. The speeds of the balls in the first group and in the second group are equal. Initially the two groups of balls are separated from one another and at some point the balls start colliding. The collisions are assumed to be elastic. How many collisions will there be?

$\endgroup$
5
  • 1
    $\begingroup$ This is a fun puzzle! V guvax vg vf gur cebqhpg bs gur ahzore bs onyyf zbivat gb gur yrsg gvzrf gur ahzore bs onyyf zbivat gb gur evtug. (V zbqry guvf hfvat fcva punvaf...) $\endgroup$ Jul 25, 2010 at 2:34
  • 9
    $\begingroup$ Jose -- glad you liked it. Your answer is correct. Actually, fvapr gur pbyyvfvbaf ner rynfgvp, bar pna guvax bs gur onyyf nf vs gurl cnffrq evtug guebhtu rnpu bgure vafgrnq bs pbyyvqvat. $\endgroup$
    – algori
    Jul 25, 2010 at 3:12
  • 1
    $\begingroup$ I've always liked this puzzle, because most people eventually solve it, but without noticing the elegant solution. $\endgroup$ Jul 26, 2010 at 22:50
  • $\begingroup$ I think you have to add something about the initial conditions. I can easily envisage an instance where there is exactly one collision. $\endgroup$ Jan 27, 2011 at 13:08
  • $\begingroup$ Christian -- or none at all! You are right, thanks, will correct this. $\endgroup$
    – algori
    Jan 27, 2011 at 20:59
37
$\begingroup$

(I learned this puzzle from Ravi Vakil.) Suppose you have an infinite grid of squares, and in each square there is an arrow, pointing in one of the 8 cardinal directions, with the condition that any two orthogonally adjacent arrows can differ by at most 45 degrees.

Can there be a closed cycle? (i.e. start at some arrow, move to the square that arrow points to, follow where the arrow there points and so on, and come back to the square you started at).

$\endgroup$
3
  • 1
    $\begingroup$ So are you asking if there can ever exist a configuration of arrows producing a closed cycle? $\endgroup$ Oct 5, 2017 at 9:35
  • $\begingroup$ Wouldn't a plain octagon work...? $\endgroup$
    – BlueRaja
    Sep 29, 2019 at 13:38
  • $\begingroup$ @BlueRaja Can you fill in the middle of the octagon? $\endgroup$ Aug 30, 2021 at 16:30
29
$\begingroup$

Adam Hesterberg told me this one ages ago. It apparently used to circulate around MOP.

Three spiders and a fly are placed on the edges of a regular tetrahedron, and travel only on those edges. The fly travels at the rate of $1$ edge/s, whereas the spiders travel at the rate of $1 + \epsilon$ edge/s for some $\epsilon > 0$. The spiders want to agree beforehand on a deterministic strategy for capturing the fly, whose location they do not know (but they do know each others' locations). The fly is invisible and omniscient; in particular, it is aware of the locations of the spiders and of their strategy at all times. (It also cannot fly.)

Can the spiders guarantee that they will catch the fly in finite time, regardless of the initial positions of the spiders and the fly? Does the answer depend on the value of $\epsilon$?

$\endgroup$
7
  • 37
    $\begingroup$ I like how the fly is anything but a fly.. :) $\endgroup$ Jun 24, 2010 at 5:46
  • $\begingroup$ I initially read that with the bugs being placed on the vertices, making it a bit stupid... $\endgroup$ Jun 24, 2010 at 6:53
  • 3
    $\begingroup$ Va pnfr nalbar vf phevbhf, gur nafjre vf lrf, ohg V unir sbetbggra gur fgengrtl. Gur fcvqref pna pngpu gur syl va fbzrguvat yvxr gjb bire rcfvyba cyhf guerr frpbaqf. $\endgroup$ Jun 26, 2010 at 2:36
  • 1
    $\begingroup$ @Jonah: Gur syl vf bzavfpvrag, fb cerfhznoyl vg xabjf enaqbz pubvprf nurnq bs gvzr. Engure, fnl gur iregvprf ner pbybherq. Sebz fgneg cbfvgvbaf, gjb fcvqref zbir gb erq, bar gb juvgr. Gura: bar ubyqf ng erq, bar zbirf erq gb terra, bar zbirf juvgr gb terra; terra ubyq, terra gb oyhr, erq gb oyhr; oyhr ubyq, oyhr gb juvgr, terra gb juvgr; juvgr ubyq, juvgr gb erq, oyhr gb erq. Ercrng. Gur syl vf sbeprq vagb gur erq-terra-oyhr-juvgr plpyr naq riraghnyyl pnhtug. (I really like this one - there's even a deleted comment with a wrong answer I totally convinced myself was right and posted.) $\endgroup$ Jun 26, 2010 at 22:59
  • 3
    $\begingroup$ Is it impossible if the spiders are the same speed or slower? $\endgroup$ Jul 8, 2010 at 5:39
25
$\begingroup$

Simplify (x-a)(x-b)...(x-z).

$\endgroup$
13
  • 18
    $\begingroup$ I always hated that one... $\endgroup$ Jun 24, 2010 at 6:43
  • 12
    $\begingroup$ But it's already so simple! $\endgroup$ Jun 24, 2010 at 6:46
  • 7
    $\begingroup$ @Pietro If something weird happens..., you haven't got it yet! $\endgroup$
    – Unknown
    Jun 25, 2010 at 9:39
  • 13
    $\begingroup$ This is cheap. I think it's one of the puzzles I've been least happy to have solved. $\endgroup$ Jun 26, 2010 at 2:05
  • 38
    $\begingroup$ I had to look this up on Google and now I hate myself ... $\endgroup$
    – gowers
    Jan 27, 2011 at 22:19
25
$\begingroup$

Here is another of my favorites: Player 1 thinks of a polynomial P with coefficients that are natural numbers. Player 2 has to guess this polynomial by asking only evaluations at natural numbers (so one can not ask for $P(\pi)$). How many questions does the second player need to ask to determine P?

$\endgroup$
3
  • 5
    $\begingroup$ Qbrf Cynlre 2 xabj n obhaq P sbe gur pbrssvpvragf? (Gura n fvatyr k1>P jvyy erirny nyy bs gurz ol jevgvat C(k1) va onfr k1.) $\endgroup$ Jun 29, 2010 at 8:27
  • $\begingroup$ Ab ur qbrfa'g xabj nalguvat nobhg gur qrterr be gur pbrssvpvragf. $\endgroup$ Jun 29, 2010 at 8:53
  • 18
    $\begingroup$ nu... abj vg qnjarq ba zr. C(1) jvyy rfgnoyvfu n obhaq ba gur pbrssvpvragf, gb or hfrq jvgu cerivbhf nggrzcgrq nafjre. $\endgroup$ Jun 29, 2010 at 11:15
24
$\begingroup$

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 a unbiased random generator of binary numbers?

$\endgroup$
9
  • 2
    $\begingroup$ I really like this one! $\endgroup$ Jun 25, 2010 at 20:18
  • 1
    $\begingroup$ Nate: Nal fbyhgvba pbhyq gnxr n juvyr. Vs gur obk vf irel ovnfrq, rnpu syvc whfg vfa'g cebqhpvat gung zhpu ragebcl. V nz abj phevbhf, ubjrire, vs gurer vf n fbzrjung zber rssvpvrag fbyhgvba. $\endgroup$ Jun 25, 2010 at 22:32
  • 1
    $\begingroup$ @Richard @Nate: Guvf cebprff vf nyfb pnyyrq haovnfvat be juvgravat (uggc://ra.jvxvcrqvn.bet/jvxv/Uneqjner_enaqbz_ahzore_trarengbe#Fbsgjner_juvgravat). Guvf cntr (uggc://jjj.pvcuretbgu.bet/pelcgb/haovnfvat/) pynvzf gb unir n fgengrtl juvpu vf arne vqrny, gubhtu V unira'g unq gvzr gb ernq vg lrg. $\endgroup$
    – BlueRaja
    Jun 25, 2010 at 22:40
  • 2
    $\begingroup$ znxr rnpu cnve bs ovgf bs gur byq trarengbe n ovg bs gur arj bar ol gbffvat bhg mreb-mreb naq bar-bar cnvef; bar pna nyfb erplpyr gur gbffrq bhg cnvef ol cnvevat gurz nf jryy (naq gbffvat mreb-mreb-mreb-mreb naq bar-bar-bar-bar); erplpyr naq ercrng... Vf guvf nf rssvpvrag nf vg pna trg? $\endgroup$ Jun 26, 2010 at 20:18
  • 2
    $\begingroup$ @RichardDore and others: the efficiency question leads to some interesting mathematics. See this paper by Yuval and my (slightly less, but still related) paper $\endgroup$
    – Dan Romik
    Sep 13, 2015 at 6:57
24
$\begingroup$

A princess inhabits a flight of 17 rooms in a row. Each room has a door to the outside, and there is a door between adjacent rooms. The princess spends each day in a room that is adjacent to the room she was in the day before. One day a prince arrives from far away to woo for the princess. The guardian explains the habits of the princess and also the rules to him: Each day he may knock at an outside door of his choice. If the princess is behind it she will open and in the end marry him. If not, nothing happens, and he gets another chance the next day. Unfortunately his return ticket expires after 30 days. Does he have enough time to conquer the princess? (Adapted from "simpler-solutions.net")

$\endgroup$
6
  • $\begingroup$ Nice problem! The solution I found in the end is so simple that if I hadn't proved it, I wouldn't believe that it could work. :) $\endgroup$ Jun 29, 2010 at 19:36
  • $\begingroup$ I'm confused! It seems like an obvious solution is "ba qnl a, xabpx ba qbbe a." But if this works, why are there only 17 rooms? $\endgroup$
    – Vectornaut
    Oct 13, 2010 at 18:13
  • 1
    $\begingroup$ @Vectornaut The princess can move: she could spend day n in the room number (n+1). $\endgroup$ Oct 26, 2010 at 15:42
  • $\begingroup$ Ba qnl a, xabpx ba qbbe a vs a vf yrff guna 17, be 33-a bgurejvfr. Rffragvnyyl gur nethzrag vf n qvfpergr irefvba bs fubjvat gung nal pbagvahbhf shapgvba sebz [0,1] gb [0,1] unf n svkrq cbvag. Bayl gung urer, gurl pna pebff rnpu bgure, ohg gur cevaprff'f cnevgl (bqq/rira) vf svkrq, juvyr jr fhccyl n "yvar" sbe obgu pnfrf. Jvyy guvf jbex? $\endgroup$
    – BharatRam
    May 25, 2011 at 17:16
  • 2
    $\begingroup$ This problem is addressed in general in Finding a princess in a palace: A pursuit-evasion problem (Britnell, John R. and Mark Wildon, 2012) and mentions this MO post specifically. Britnell and Wildon solve the problem for arbitrary graphs: they provide a strategy which is guaranteed to find the princess in bounded time if such a strategy exists, they characterize the graphs for which such a strategy does exist, and they show that their strategy provides the smallest bound among all such strategies. $\endgroup$ Oct 9, 2019 at 19:12
20
$\begingroup$

It is very important that you tell these two puzzles in the correct order, i.e., first the first puzzle and then the second one. The first puzzle is very easy but messes with people's minds in just the right way. In my experience some mathematicians are driven crazy by the second puzzle.

Puzzle 1: Grandma made a cake whose base was a square of size 30 by 30 cm and the height was 10 cm. She wanted to divide the cake fairly among her 9 grandchildren. How should she cut the cake?

Puzzle 2: Grandma made a cake whose base was a square of size 30 by 30 cm and the height was 10 cm. She put chocolate icing on top of the cake and on the sides, but not on the bottom. She wanted to divide the cake fairly among her 9 grandchildren so that each child would get an equal amount of the cake and the icing. How should she cut the cake?

$\endgroup$
9
  • 3
    $\begingroup$ uneq sbe gur zngurzngvpvnaf, ohg ernyyl rnfl sbe gur tenaqzn... $\endgroup$ Jul 7, 2010 at 21:57
  • 1
    $\begingroup$ On a related note, here's a similar puzzle: Grandma wants to cut the first cake into 8 equal slices, but only making three cuts. How can she do it? $\endgroup$
    – BlueRaja
    Jul 8, 2010 at 21:03
  • 2
    $\begingroup$ @ BlueRaja: gurer ner ab gevpxf, vg ernyyl vf n fvzcyr naq ryrzragnel 2Q trbzrgel ceboyrz. Nyfb abgr gung vg znggref gung gur pnxr vf fdhner naq abg erpgnathyne. $\endgroup$ Jul 9, 2010 at 10:29
  • 2
    $\begingroup$ Hint: gur fvzcyr fbyhgvba (jryy, ng yrnfg gur bar V'z guvaxvat bs) trarenyvfrf vzzrqvngryl gb nal ahzore bs tenaqpuvyqera (jvgubhg punatvat gur pnxr). $\endgroup$ Jul 12, 2010 at 17:58
  • 5
    $\begingroup$ Solution, since nobody posted it: Gb qvivqr gur pnxr vagb a cnegf, znex a cbvagf ba gur pvephzsrerapr bs gur fdhner fhpu gung gurl qvivqr gur pvephzsrerapr vagb rdhnyyl ybat cnegf. Gura phg sebz gur pragre bs gur fdhner gb gur znexrq cbvagf. $\endgroup$ Jul 27, 2010 at 23:27
18
$\begingroup$

You have a glass of red wine and a glass of white wine (of equal volume). You take a teaspoon of the red wine and put it in the glass of white wine and stir. You then take a teaspoon of the white wine (which now has a teaspoon of the red wine in it) and put it in the glass of red wine and stir.

Which glass has a higher ratio of (original wine)/(introduced wine)?

$\endgroup$
6
  • 11
    $\begingroup$ This is a classic so chances are everyone will know this at a dinner. $\endgroup$
    – algori
    Jun 24, 2010 at 4:59
  • 8
    $\begingroup$ You don't even have to stir perfectly $\endgroup$
    – Ben
    Oct 27, 2010 at 17:09
  • $\begingroup$ @Ben: Why don't you have to stir? First I was surprised. But the simplest solution is this: Take a very big teaspoon holding all red whine. $\endgroup$
    – user34804
    Jun 29, 2013 at 11:47
  • $\begingroup$ @Hilbert: Well, the solution works even without perfect stirring. $\endgroup$
    – Ben
    Jun 29, 2013 at 17:21
  • 1
    $\begingroup$ @Ben: O, what a fool I was! Consider simply every glass containing 100 marbles, red and white, at the beginning, and 100 marbles of both colours, at the end. Really no stirring necessary! $\endgroup$
    – user34804
    Jun 30, 2013 at 11:42
18
$\begingroup$

What is the resistance between 2 adjacent vertices of an infinite checkerboard if every edge is a 1 ohm resistor?

$\endgroup$
2
  • 14
    $\begingroup$ xkcd.com/356 $\endgroup$
    – PersonX
    Jul 1, 2010 at 15:14
  • 6
    $\begingroup$ Great puzzle, but having seen the solution I'm not sure I'd have managed this over dinner... using a ynggvpr terra'f shapgvba hardly puts this at the level of sudoku does it? $\endgroup$ Jul 13, 2010 at 11:29
16
$\begingroup$

A certain rectangle can be covered by 25 coins of diameter 2. Can it always be covered with 100 coins of diameter 1?

$\endgroup$
1
16
$\begingroup$

When you watch yourself in a mirror, left and right are exchanged. But why aren't top and bottom?

$\endgroup$
3
  • 1
    $\begingroup$ Please define "left". (Eg.: the side with a wedding band...?) $\endgroup$ Jan 27, 2011 at 4:05
  • 5
    $\begingroup$ I am used to even more misdirection: Describe it as a philosophy problem. In college, we would ask philosophy majors this puzzle at dinner, and let them go on at length before revealing that there is a simple answer, which shouldn't be the case for a philosophy problem. $\endgroup$ Jan 28, 2011 at 10:02
  • 4
    $\begingroup$ Gur zveebe qbrf abg rkpunatr yrsg naq evtug, abe qbrf vg rkpunatr gbc naq obggbz; vg rkpunatrf sebag naq onpx. Zbfg crbcyr, jura gheavat nebhaq gb ybbx va n zveebe, jvyy ghea nobhg n iregvpny nkvf engure guna n ubevmbagny bar. Guvf gheavat unf gur rssrpg bs rkpunatvat sebag naq onpx (chggvat gurz onpx gur jnl gurl jrer) nf jryy nf yrsg naq evtug. $\endgroup$ Mar 31, 2012 at 14:36
15
$\begingroup$
  1. Alice shuffles an ordinary deck of cards and turns the cards face up one at a time while Bob watches. At any point in this process before the last card is turned up, Bob can guess that the next card is red. Does Bob have a strategy that gives him a probability of success greater that .5?

  2. Let $x_1, x_2, \dots, x_n$ be $n$ points (in that order) on the circumference of a circle. Dana starts at the point $x_1$ and walks to one of the two neighboring points with probability $1/2$ for each. Dana continues to walk in this way, always moving from the present point to one of the two neighboring points with probability $1/2$ for each. Find the probability $p_i$ that the point $x_i$ is the last of the $n$ points to be visited for the first time. In other words, find the probability that when $x_i$ is visited for the first time, all the other points will have already been visited. For instance, $p_1=0$ (when $n>1$), since $x_1$ is the first of the $n$ points to be visited.

  3. Let $\pi$ be a random permutation of $1,2,\dots,n$ (from the uniform distribution). What is the probability that 1 and 2 are in the same cycle of $\pi$?

  4. Choose $n$ points at random (uniformly and independently) on the circumference of a circle. Find the probability $p_n$ that all the points lie on a semicircle. (For instance, $p_1 = p_2 = 1$.) More generally, fix $\theta<2\pi$ and find the probability that the $n$ points lie on an arc subtending an angle $\theta$ .

$\endgroup$
1
  • 2
    $\begingroup$ The answer to 3 surprised me, as did the brevity of the proof I found: Ercerfrag n crezhgngvba bs {1,...,a} ol, re, n crezhgngvba bs {1,...,a} nf sbyybjf: Jevgr qbja gur ryrzragf bs vgf plpyrf, rnpu plpyr ortvaavat jvgu vgf fznyyrfg ryrzrag, plpyrf va qrfpraqvat beqre bs gung fznyyrfg ryrzrag. Rirel crezhgngvba C bs {1,...,a} vf gur abgngvba sbe n havdhr crezhgngvba D bs {1,...,a}. Gur plpyr va D gung pbagnvaf 1 ortvaf jurerire 1 nccrnef va C naq pbagvahrf gb gur raq bs C; gurersber gung plpyr pbagnvaf 2 vss 1 cerprqrf 2 va C, naq jr'er qbar. $\endgroup$ Sep 30, 2015 at 13:01
14
$\begingroup$

This is a hat problem I heard only two days ago: you have a hundred people and each one has a (natural) number between 1 and 100 written on his hat. (Numbers may repeat.) As ususal, everybody can see only the numbers on other people's hats. Give these guys a strategy for guessing so that at least one will surely make the right guess. (They do not hear each other guesses.)

$\endgroup$
2
  • $\begingroup$ Nice problem. Here is a slightly different problem that can be solved in a similar way. Give these guys a strategy for guessing so that everybody guesses correctly with probability 1/100. $\endgroup$
    – Tony Huynh
    Jul 9, 2010 at 10:59
  • 2
    $\begingroup$ Very nice! Jbex zbq 100. Crefba a thrffrf (a zvahf (fhz bs ahzoref gurl frr)). Gura crefba (fhz bs nyy ahzoref) vf pbeerpg. $\endgroup$ Jul 12, 2010 at 17:35
13
$\begingroup$

Not a very difficult one but I like it since it is even suitable for non-mathematicians:

A small boat carrying a heavy stone is floating in a swimming pool. What happens to the level of water (up, down or remains equal) in the swimming pool if one removes the stone from the boat and throws it in the swimming pool?

The very easy solution suggests the following joke (illustrating the well-known ignorance of mathematicians of reality): Instead of sending scores of ships for saving passengers from the Titanic, one should have sunk all possible rescue-ships in order to lower the sea-level.

$\endgroup$
4
  • 2
    $\begingroup$ I feel I should point out that it's dependent on having a very dense (denser than water) stone rather than just heavy. Other than that, good question. $\endgroup$
    – Mark Bell
    Jun 24, 2010 at 14:03
  • 7
    $\begingroup$ If the stone sinks, it's denser than water. $\endgroup$ Jun 26, 2010 at 22:26
  • 10
    $\begingroup$ If you look on the periodic table, you'll find out that stone atoms are about twice as heavy as water atoms. As all atoms are the same size, and all solids and liquids pack their atoms as dense as possible, stone is necessarily twice as dense as water. $\endgroup$ Jul 7, 2010 at 22:43
  • 11
    $\begingroup$ Theo, your argument doesn't make much sense: "stone atoms"? Rocks contain many different elements, including hydrogen and oxygen (which water molecules contain). Also, solids don't necessarily pack atoms to maximize density (the heaviest solids aren't necessarily made of the heaviest atoms). Regardless, I think it's pretty safe to say stones tend to be heavier than water. Most kayakers don't worry about boulders floating down rivers and rolling over them. $\endgroup$ Aug 7, 2010 at 3:10
12
$\begingroup$

Instead of recommending some puzzles, I'll recommend some books containing many puzzles. Peter Winkler, Mathematical Puzzles; Peter Winkler, Mathematical Mind-Benders; Miodrag Petkovic, Famous Puzzles of Great Mathematicians.

$\endgroup$
12
$\begingroup$

Via the great Martin Gardner: A cylindrical hole is drilled straight through the center of a solid sphere. The length of hole in the sphere (i.e. of the remaining empty cylinder) is 6 units. What is the volume of the remaining solid object (i.e. sphere less hole)? Yes, there is enough information to solve this problem!

$\endgroup$
5
  • $\begingroup$ This is an amusing exercise for calculus courses (solids of revolution), although calculus is not necessary. $\endgroup$ Jun 24, 2010 at 17:42
  • $\begingroup$ @Michael: Indeed! I first saw this as an exercise while I was teaching calculus and was somewhat surprised/annoyed by how long it took me to figure out. $\endgroup$
    – Kiochi
    Jun 24, 2010 at 18:59
  • 2
    $\begingroup$ It's easy to see what the answer has to be once you're told there's an answer, but I don't see how to prove it without setting up an integral. What am I missing? $\endgroup$ Jun 26, 2010 at 14:54
  • 2
    $\begingroup$ Jonah, I don't think you're missing anything. To solve rigorously, I think you need calculus. Gardner's own answer basically said that, assuming you understand that the problem is well-posed, the answer must not depend upon the size of the sphere. So take the sphere with hole of diameter approaching zero (i.e. a sphere of diameter 6 units), which is just the whole sphere (i.e. 36π cubic units). $\endgroup$
    – user5794
    Jun 27, 2010 at 15:40
  • 10
    $\begingroup$ Full-blown calculus isn't necessary. You only need Cavalieri's principle: en.wikipedia.org/wiki/… $\endgroup$
    – aorq
    Jul 1, 2010 at 18:12
10
$\begingroup$

(I learned this problem from Persi Diaconis.) A deck of $n$ different cards is shuffled and laid on the table by your left hand, face down. An identical deck of cards, independently shuffled, is laid at your right hand, also face down. You start turning up cards at the same rate with both hands, first the top card from both decks, then the next-to-top cards from both decks, and so on. What is the probability that you will simultaneously turn up identical cards from the two decks? What happens as $n \to \infty$? And does the answer for small $n$ (say, $n=7$) differ greatly from $n=52$?

$\endgroup$
10
$\begingroup$

Okay, so it's somewhat more numeric than the others, but I quite enjoy the simplicity of:

Simplify:

$$\sqrt{2+\sqrt3}$$

$\endgroup$
11
  • $\begingroup$ Do you mean $\sqrt{3+2\sqrt2}$ ? $\endgroup$
    – lhf
    Jul 6, 2010 at 11:49
  • $\begingroup$ oops! in fact... $\endgroup$ Jul 6, 2010 at 12:07
  • 1
    $\begingroup$ (GURER FUBHYQ OR AB VGRENGRQ FDHNER EBBGF VA LBHE NAFJRE) $\endgroup$ Jul 6, 2010 at 12:30
  • 1
    $\begingroup$ Nalbar jub qvq zngu pbzcrgvgvbaf erpragyl fubhyq erpbtavmr gur unys-natyr sbezhyn, V jbhyq guvax. :) $\endgroup$
    – JBL
    Jul 6, 2010 at 12:44
  • 4
    $\begingroup$ Jung'f guvf gevt vqragvgl ohfvarff? Chg n zvahf orsber gur vaare fdhner ebbg naq lbh trg gur vairefr. Gura fhz be fhogenpg vg jvgu vgf vairefr naq frr jung gurve fdhnerf ner. Gur tnybvf gurbel fbyhgvba :) $\endgroup$
    – Ryan Reich
    Jul 28, 2010 at 4:21
9
$\begingroup$

Countably many little dwarfs are going to their everyday work to the mine. They are marching and singing in a well-ordered line (by natural numbers), so that number 1 watches the backs of all the other ones, and, in general, number n watches the backs of all the others from n+1 on. Suddenly, an evil wizard appears on the top of a small hill, and magically puts a name on the back of each dwarf. Any name may be used, even more than once: existing ones, old-fashioned ones, or just weird sounds sprang out of his sick imagination, included grunts, sneezes and any snort-like name (you may enjoy providing your listerners with examples if they ask for). Then, he claims that, at his signal, everybody has to guess his own name, and say it loudly, all together. Whoever fails, will disappear immediately. Poor dwarfs are not new to these bully spells, and do have a strategy, that allows all but finitely many of them to survive. How do they do? To formalize, we may think the evil wizard has attached a real number to each dwarf's back.

$\endgroup$
2
  • 2
    $\begingroup$ I now see that this is a variant of Anton Geraschenko's problem. $\endgroup$ Jun 24, 2010 at 5:47
  • 2
    $\begingroup$ Here is my solution: the strategy of the dwarfs is simply...n yvarne cebwrpgbe C sebz gur irpgbe fcnpr K bs nyy erny frdhraprf bagb gur fhofcnpr L bs nyy riraghnyyl inavfuvat erny frdhraprf. Gur jvmneq unf pubfra na ryrzrag k bs K; rnpu qjnes xabjf vg hc gb na ryrzrag bs L, fb ur pbzcyrgryl xabjf (V-C)k. Gurl nterr gb orunir nf vs Ck jrer 0, juvpu vf gur yhpxl pubvpr sbe nyy qjnesf ohg gur barf jvgu vaqrk va gur fhccbeg bs Ck. Bs pbhefr, gur rkvfgrapr bs gur cebwrpgbe vf rafherq ol gur nkvbz bs pubvpr. Jurer gurl qvq trg bar, vg erznvaf n zlfgrel. $\endgroup$ Jun 27, 2010 at 14:58
9
$\begingroup$

You have a large pile of ropes and some matches. All you know about the ropes:

  • Each rope has a different length
  • Each rope burns completely (starting from one end) in exactly 64 minutes
  • Each rope has non-uniform density, meaning it is thicker at some points than others. Consequently, burning half a rope cannot be guaranteed to take 32 minutes.

The goal is to identify when exactly 63 minutes have passed.

$\endgroup$
2
  • 1
    $\begingroup$ Hint: lbh arrq gb ohea frira ebcrf $\endgroup$
    – BlueRaja
    Aug 6, 2010 at 17:58
  • $\begingroup$ Solution: Yvtug bar raq bs nyy 7 ebcrf, naq gur bccbfvgr raq bs bar bs gur ebcrf, ba sver fvzhygnarbhfyl. Gur bar jvgu obgu raqf yvg jvyy ohea bhg va rknpgyl 32 zvahgrf. Ng gur rknpg zbzrag vg oheaf bhg, yvtug gur bgure raq bs gur frpbaq bar. Vg jvyy ohea bhg va 16 zvahgrf. Jura vg svavfurf, yvtug gur guveq, juvpu jvyy ynfg 8 zvahgrf. rgp. $\endgroup$
    – BlueRaja
    Jan 27, 2015 at 23:00
8
$\begingroup$

You have 1000 bottles of wine. Exactly one of the bottles contains a deadly poison, but you don't know which one. The killing time of the poison varies from person to person, but death is imminent in at most $t$ hours after ingestion. You are allowed to use 10 notorious criminals as poison fodder (they are on death row). How much time do you need to correctly determine the poisoned bottle?

$\endgroup$
7
  • $\begingroup$ How deadly is the poison? $\endgroup$ Jun 24, 2010 at 17:44
  • $\begingroup$ It's fatal, but you don't know exactly how long it will take for each person. It's safe to assume that it will take roughly t hours for each person, but not exactly t hours. Otherwise you could determine the poison bottle in slightly over t hours if you had a precise enough stop watch. $\endgroup$
    – Tony Huynh
    Jun 24, 2010 at 19:14
  • 15
    $\begingroup$ Since the death penalty is occasionally dealt to innocent people, I would use 10 notorious politicians. $\endgroup$ Jun 27, 2010 at 9:12
  • 6
    $\begingroup$ I think the first step is to dash to the store for 2 dozen bottles of wine. $\endgroup$ Jul 14, 2010 at 15:29
  • 3
    $\begingroup$ There's a question about generalizing to k poisoned bottles at MU: math.stackexchange.com/questions/639/… $\endgroup$ Jul 29, 2010 at 17:50
7
$\begingroup$

There is a square with seven monkeys on the floor and seven bananas on the top. Seven ladders go up the square, from one monkey to the banana over it, and the monkeys can climb them. Moreover there are some ropes which connect the ladders.

A monkey will go up towards the bananas, but whenever it meets a rope it cannot resist the temptation to stray and hang on it. Prove that every monkey will reach a banana, no matter the configuration of ropes.

There are at least two different solutions to this.

$\endgroup$
3
  • $\begingroup$ I guess we can assume that the ends of two ropes do not coincide? $\endgroup$
    – Tom Smith
    Jun 24, 2010 at 19:45
  • $\begingroup$ Yes, that is correct. Otherwise the path of a monkey would not be well defined. Maybe I should add, just to be precise, that there is a finite number of ropes. $\endgroup$ Jun 25, 2010 at 9:44
  • 1
    $\begingroup$ Vaqhpgvba ba gur ahzore bs ebcrf: Jvgu n ebcr wbvavat cbvagf N naq O, lbh erzbir gur ebcr, phg gur ynqqref ng N naq O naq vagrepunatr gur gbcf, erfhygvat va na rdhvinyrag fvghngvba jvgu bar srjre ebcr. $\endgroup$ Dec 29, 2013 at 13:32
7
$\begingroup$

When they came to diner some shook hands. Ask them to prove that that two of them shook hands the same number of times.

$\endgroup$
2
  • 4
    $\begingroup$ provided forgetful ones (as mathematicians tend to be) don't shake hands twice with each other... $\endgroup$ Jun 27, 2010 at 9:07
  • $\begingroup$ Sorry, I forgot to mention that. $\endgroup$
    – rgrig
    Jul 27, 2010 at 14:29
7
$\begingroup$

Oldie but a goodie (Monty-hall problem):

You are on a game show with three doors, behind one of which is a car and behind the other two are goats. You pick door #1. Monty, who knows what’s behind all three doors, reveals that behind door #2 is a goat. Before showing you what you won, Monty asks if you want to switch doors. Should you switch?

$\endgroup$
4
  • $\begingroup$ Jr nyy xabj gur nafjre vf, lrf, lbh fubhyq. Gur rnfvrfg jnl gb rkcynva vg gb aba-zngurzngvpvnaf vf: Jung vs gurer jrer 100 qbbef, jvgu 99 tbngf, naq nsgre cvpxvat bar qbbe, gur ubfg bcrarq hc 98 qbbef bs tbngf - jbhyq lbh fjvgpu gura? $\endgroup$
    – BlueRaja
    Jun 25, 2010 at 0:29
  • 6
    $\begingroup$ You should specify that Monty knows what's behind all three doors and is guaranteed to open a door hiding a goat (though I think this is intuitively understood). $\endgroup$
    – JBL
    Jun 27, 2010 at 1:46
  • $\begingroup$ After arriving at the solution, read this comic: spikedmath.com/020.html $\endgroup$
    – Kiochi
    Jun 29, 2010 at 15:04
  • $\begingroup$ If you need a car you should switch. Otherwise stay with door number 1. $\endgroup$
    – Mykie
    Jul 28, 2010 at 19:44
7
$\begingroup$

There is a plane with 100 seats and we have 100 passengers entering the plane one after the other. The first one cannot find his ticket, so chooses a random (uniformly) seat. All the other passengers do the following when entering the plane (they have their tickets). If the seat written on the ticket is free, one sits on this seat, if not he chooses a other (free) seat at random (uniformly). What is the probability the last passenger entering the plane gets the correct seat?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.