Math puzzles for dinner [closed]

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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?

Answer 6

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

Answer 7

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

Answer 8

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?

Answer 9

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

Answer 10

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?

Answer 11

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

Answer 12

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?

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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.

Answer 20

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.

Answer 21

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!

Answer 22

(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$?

Answer 23

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

Simplify:

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

Answer 24

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.

Answer 25

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.

Answer 26

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?

Answer 27

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.

Answer 28

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

Answer 29

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?

Answer 30

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?