Probability Puzzles
Classic probability and logic puzzles with answers.
Notation: is the probability of event , the probability of given , and the expected (average) value of . is the -th harmonic number.
Conditional probability and Bayes
1. Monty Hall: There are 3 doors, with a car behind one at random and goats behind the others. You pick a door; the host, who knows where the car is, always opens another door with a goat behind it and offers you a switch. Should you switch?
Solution
Yes: switching wins with probability 2/3. Your first pick is right 1/3 of the time, and switching wins exactly when it was wrong. The host's knowledge is what carries the information.
2. Monty Hall, ignorant host: Same setup, but the host doesn't know where the car is: he opens one of the other two doors at random, and it happens to show a goat. Should you switch?
Solution
1/2, so switching no longer helps. Conditioning on "a goat was revealed" now removes the cases where the host would have revealed the car, which rebalances the odds.
3. Monty Hall, 100 doors: You pick 1 of 100 doors; the host, who knows where the car is, opens 98 of the others, all with goats. Should you switch?
Solution
Switch and win with probability 99/100. Scaling up makes the mechanism obvious and is the clearest way to explain the 3-door version.
4. Boy or girl: A family has 2 children, each independently a boy or a girl with equal chance. You learn that at least one is a boy. What is
Solution
1/3. The equally likely cases are BB, BG and GB. GG is ruled out, and BG and GB are different outcomes.
5. Boy or girl, ordered: Same family, but you learn that the older child is a boy. What is
Solution
1/2. This conditions on a specific child rather than on "at least one", and that difference is the whole lesson of the pair.
6. Tuesday boy: A family has 2 children, each independently a boy or girl and born on any day of the week with equal chance. You learn that at least one is a boy born on a Tuesday. What is
Solution
13/27. Of the equally likely (sex, weekday) pairs, 27 contain a Tuesday boy, and 13 of those are two boys (). The more specific the condition, the closer the answer moves toward 1/2.
7. Two coins: One coin is fair and one has two heads. You pick one at random, flip it, and get heads. What is
Solution
2/3. By Bayes' rule, . After heads in a row it is , so after 3 heads.
8. Three cards: The cards are red–red, red–white and white–white. You draw a card at random and look at a random side of it, which is red. What is
Solution
2/3. Count red faces, not cards: there are 3 red faces and 2 of them are on the red–red card.
9. Medical test: A disease has prevalence 1/1000. A test catches 99% of cases (sensitivity) and correctly clears 99% of healthy people (specificity). You test positive. What is
Solution
. Bayes gives . About 10 false positives per 1000 people swamp the 1 true positive.
10. Rolling until a six, given all rolls were even: Roll a fair die until the first 6. Given that every roll, including the last, was even, what is the expected number of rolls?
Solution
3/2. , which sums to . So given all-even is geometric with success probability , and its mean is . Restricting the die to and answering 3 is wrong, because long sequences are much less likely to stay all even.
Expected value
11. Waiting for a pattern: How many fair-coin flips does it take on average to see HH? And HT?
Solution
and . Similarly , and . Patterns that overlap with themselves take longer, because a failure after a partial match sends you further back. A run of heads takes flips on average.
12. Pattern race: Flip a fair coin until TH or HH appears. What is
Solution
3/4. HH wins only if the first two flips are HH. Otherwise a T comes before any HH, and the next H completes TH. By contrast, HT against HH is exactly 1/2, even though HT has the shorter expected wait. Expected waiting times don't decide who wins a race.
13. Coupon collector: How many rolls of a fair die does it take on average to see all 6 faces?
Solution
. Once you have faces, the expected wait for a new one is . In general it takes draws to collect types.
14. Two sixes in a row: Rolling a fair die, what is the expected number of rolls until two consecutive sixes?
Solution
42, which is . It also follows from first-step analysis on a two-state chain.
15. Uniforms until the sum exceeds 1: Draw independent Uniform numbers until the running sum exceeds 1. What is the expected number of draws?
Solution
. , so .
16. First ace: What is the expected position of the first ace in a shuffled 52-card deck?
Solution
. The 4 aces split the other 48 cards into 5 gaps of equal expected size . Add 1 for the ace itself.
17. Maximum of two dice: What is the expected maximum of two fair dice?
Solution
. .
18. Die with one optional re-roll: Roll a fair die. After seeing it, you may keep it or re-roll once and keep the second result. What is the best expected value?
Solution
. Re-roll whenever the first roll is below the average of 3.5, so on 1 to 3: . With two re-rolls allowed the answer is : keep 5 or 6 on the first roll, then 4 to 6 on the second.
19. Hat check: people get their hats back in random order. How many get their own hat, on average?
Solution
1, for every . By linearity of expectation it is . The chance that nobody gets their own hat tends to .
20. Longest piece: Break a stick of length 1 at 2 uniform random points. What is the expected length of the longest piece?
Solution
, which is .
21. Distinct faces: Roll a fair die 6 times. What is the expected number of distinct faces?
Solution
. Sum an indicator for each face appearing at least once.
22. Race to the first six: Two players take turns rolling a fair die, and the first to roll a 6 wins. What is
Solution
6/11, which is .
Rates
23. Cars on a road: Cars pass a point on a road at random, at a steady average rate. The probability of seeing at least one car in an hour is 0.99. What is the probability of seeing at least one car in half an hour?
Solution
0.9. Assume cars arrive independently at a steady rate, so the two half-hours behave identically and independently. Then , so and the answer is . Equivalently, a Poisson process with rate per hour gives .
24. Two crews: One crew can finish a job in 6 days and another in 8 days, each working at a constant rate. How long do they take working together?
Solution
days. Add rates, not times: together they do of the job per day, so the job takes days.
25. Fly between two trains: Two trains 100 km apart head towards each other at 100 km/h each. A fly starts at one train and flies back and forth between them at 144 km/h, turning instantly, until they meet. How far does the fly travel?
Solution
72 km. There is no need to sum the infinite series of legs: the trains close at 200 km/h and meet after half an hour, and the fly is flying the whole time, so it covers km.
Combinatorics
26. Birthday problem: Ignoring leap years and assuming all 365 birthdays are equally likely, how many people are needed for to exceed 1/2?
Solution
23 (; with 22 it is ). It reaches at 50 people. The number is small because what matters is pairs: 23 people form pairs.
27. Ballot problem: Person A gets votes and person B gets , with greater than . The votes are counted in random order. What is the probability A stays strictly ahead throughout?
Solution
. For example, 5 to 3 gives 1/4. It is proved with the reflection principle.
28. 100 light bulbs: 100 bulbs start off. On pass , for , every -th bulb is toggled. How many end up on?
Solution
10. Bulb is toggled once per divisor of , so it ends on exactly when has an odd number of divisors, which happens only for perfect squares.
29. Josephus problem: people, numbered 1 to , stand in a circle. Going round from person 1, every second person is eliminated (2, 4, …) until one is left. Who survives?
Solution
Position , where with and less than . For that is position 73; for it is 19.
30. Poisoned wine: One of 1000 bottles is poisoned, and even a sip makes a tester ill, but only after a day. Each tester can sip from any number of bottles. How many testers are needed to find the bottle in one day?
Solution
10, since . Number the bottles in binary; tester drinks from every bottle whose -th bit is 1. The pattern of who falls ill spells out the bottle number.
31. 12 balls, 3 weighings: One of 12 otherwise identical balls has a different weight, heavier or lighter. Using a two-pan balance 3 times, find it and say whether it is heavier or lighter.
Solution
Possible. Weigh 4 against 4 and branch, moving balls between pans so each weighing yields one of three outcomes. There are cases and outcomes. The most 3 weighings can handle is balls.
32. Charged batteries: You have 8 batteries, 4 of them charged, and a toy that works only with 2 charged batteries in it. A test means putting two batteries in the toy and seeing whether it works. What is the fewest number of tests that guarantees finding a working pair?
Solution
6. Split the batteries into groups of three, three and two: batteries 1–3, 4–6 and 7–8. Test all three pairs within the first group, then all three within the second. A group of three holding two charged batteries would have produced a working pair, so if all six tests fail, each group of three holds at most one charged battery, which leaves 7 and 8 both charged. A 7th test would only confirm what the 6th failure already proved.
33. Socks: A drawer holds plenty of socks in colours. Drawing in the dark, how many must you take to guarantee a matching pair?
Solution
, by the pigeonhole principle.
Geometry and probability
34. Broken stick triangle: Break a stick at 2 uniform random points. What is
Solution
1/4. Every piece must be shorter than 1/2. In the unit square of break points, that region is one of four congruent triangles.
35. Bertrand's paradox: What is the probability that a random chord of a circle is longer than the side of the inscribed equilateral triangle?
Solution
It depends on how the chord is chosen. Uniform random endpoints give 1/3. A random radius with a uniform point on it gives 1/2. A midpoint uniform in the disk gives 1/4. The honest answer is to name the ambiguity and give all three.
36. Triangle containing the centre: Pick 3 uniform random points on a circle. What is
Solution
1/4. It fails exactly when all 3 points lie in some semicircle, which has probability for .
37. Clock hands: How many times do the hour and minute hands overlap in 12 hours?
Solution
11 times, every minutes. The minute hand gains 11 laps on the hour hand in 12 hours, not 12.
Logic and strategy
38. 100 prisoners and 100 boxes: Slips numbered 1 to 100 are placed at random in 100 numbered boxes, one per box. One at a time, each of 100 prisoners enters the room, opens up to 50 boxes looking for their own number, and leaves everything as they found it. The prisoners may agree a plan beforehand but cannot communicate once it starts, and all are freed only if every prisoner finds their number. What is the best strategy?
Solution
Follow the cycle: open the box with your own number, then the box named by the slip inside, and so on. Success . Everyone succeeds exactly when the random permutation has no cycle longer than 50. Guessing independently gives ; correlating the failures is everything.
39. Hats in a line: 100 people stand in a line, each wearing a black or white hat and seeing only the hats in front of them. Starting from the back, each person says one colour aloud, and everyone hears every answer. Anyone who names their own hat's colour survives. They may agree a plan beforehand but cannot otherwise communicate. How many can be guaranteed to survive?
Solution
99. The person at the back announces the parity of the black hats they see. Everyone else tracks that parity against the guesses already heard and deduces their own colour.
40. Ants on a stick: Ants are placed anywhere on a 1-metre stick, each facing left or right, and walk at the same constant speed. When two ants meet they both reverse, and an ant falls off when it reaches an end. When is the stick certain to be empty?
Solution
After the time it takes to walk 1 metre, whatever the number of ants. Two identical ants bouncing off each other look exactly like two ants passing through each other, so each trajectory is just a straight line.
41. Egg drop: An egg breaks if dropped from some unknown floor or higher and survives below it, and an unbroken egg can be dropped again. With 2 eggs and 100 floors, what is the fewest drops that always finds the highest safe floor?
Solution
14, the smallest with . Drop from floors 14, 27, 39 and so on, with steps shrinking by one so the worst case stays fixed. With 3 eggs it is 9, since .
42. Burning ropes: Two ropes each take exactly 60 minutes to burn, but at uneven rates along their length. With a lighter, how do you measure 45 minutes?
Solution
Light rope A at both ends and rope B at one end. When A is gone (30 minutes), light B's other end; it finishes 15 minutes later. Uneven burning doesn't matter, only the total time.
43. Water jugs: With a 3-litre jug, a 5-litre jug and a tap, how do you measure exactly 4 litres?
Solution
Fill the 5-litre jug and pour it into the 3 (leaving 2); empty the 3 and pour the 2 litres into it; fill the 5 again and top up the 3, which takes 1 litre and leaves 4 in the 5-litre jug. In general, two jugs of sizes and can measure exactly the multiples of up to the larger size; here , so every whole number of litres from 1 to 5 is reachable.
44. 25 horses: 25 horses each always run at the same speed. A race takes at most 5 horses and shows only their finishing order, with no times. How many races does it take to find the 3 fastest?
Solution
7. Race 5 groups of 5, then race the 5 group winners, which finds the fastest overall. Only 5 horses can still be 2nd or 3rd (2 from the winner's group, 2 from the runner-up's, 1 from the third-place group), so one more race settles it.
45. Bridge and torch: 4 people take 1, 2, 5 and 10 minutes to cross a bridge. At most 2 may cross at once, at the slower one's pace, and they share one torch, which must be carried on every crossing. What is the shortest total time?
Solution
17 minutes: 1 and 2 cross (2), 1 returns (1), 5 and 10 cross (10), 2 returns (2), 1 and 2 cross (2). The key is sending the two slowest together; letting the fastest escort everyone takes 19.
46. Three switches: Three switches outside a closed room control one ordinary (incandescent) bulb inside. You may flip the switches as you like, then enter the room once. How do you tell which switch controls the bulb?
Solution
Turn switch 1 on for a few minutes, turn it off, turn switch 2 on, then enter. Lit means switch 2, off but warm means switch 1, off and cold means switch 3. Heat supplies the extra bit of information.
47. Polynomial from queries: A polynomial has non-negative integer coefficients, and you don't know its degree. You may evaluate it at any integers you choose. How few evaluations recover every coefficient?
Solution
Two. First query , the sum of the coefficients, so every coefficient is at most . Then query : since every coefficient is smaller than , the coefficients are exactly the digits of written in base . If coefficients may be negative, no fixed number of queries works without a bound on their size, since is 0 at both and for every ; given a bound , one query at decoded as balanced base- digits suffices. If the degree is known instead, evaluations and interpolation also work.
48. Prisoners and a light switch: 100 prisoners are taken one at a time into a room with a light, which starts off, in an arbitrary order in which everyone visits infinitely often. On each visit a prisoner may toggle the light or leave it. They may agree a plan beforehand but cannot otherwise communicate. How can someone eventually announce, with certainty, that everyone has visited?
Solution
Choose one counter. Every other prisoner turns the light on exactly once, the first time they find it off. The counter turns it off each time and counts, and announces at 99.
Game theory
49. Pirates and gold: 5 ranked pirates split 100 coins. The most senior proposes a split, and it passes with at least half the votes (the proposer votes too); otherwise the proposer is thrown overboard. Every pirate is rational, wants as much gold as possible, and, if it makes no difference to their gold, votes to throw the proposer overboard. What does the top pirate propose?
Solution
98 for themselves and 0, 1, 0, 1 for the others. Work backwards: with 3 pirates the split is 99, 0, 1; with 4 it is 99, 0, 1, 0. The cheapest votes belong to pirates who would get nothing if the proposer were thrown overboard, and 1 coin each buys them. Fix the voting rule first, since requiring a strict majority changes the answer.
50. Russian roulette: A 6-chamber revolver holds 2 bullets in adjacent chambers and is spun once; after each pull of the trigger the cylinder moves to the next chamber. Your opponent fires at himself and survives. Before your turn, should you spin again?
Solution
Don't spin: 1/4 against 1/3. The chamber just fired was one of the 4 empty ones, and only 1 of those 4 is followed by a bullet. Spinning gives .
51. Guess two-thirds of the average: Everyone picks a number from 0 to 100, and the winner is whoever is closest to two-thirds of the average. If everyone reasons perfectly, what should you pick?
Solution
The only Nash equilibrium is 0, by repeatedly ruling out numbers above , then , and so on. Against real people the winning guess is usually around 20 to 35, because most people only reason one or two levels deep.
52. Nim: Two players take turns removing any number of objects from one pile. With piles of 3, 4 and 5, does the first player win if whoever takes the last object wins?
Solution
Yes. The XOR of the pile sizes is , which is not 0. A position loses for the player to move exactly when this XOR is 0, and from any other position there is a move that makes it 0.
53. Gambler's ruin: A fair coin game starts at 10 and ends at 0 or 100. What is What if each step wins with probability , starting at 10 with target 20?
Solution
for the fair game, and about for the biased one, from with . A walker 1 step from a cliff who steps away with probability 2/3 eventually falls with probability .
54. Secretary problem: 100 applicants arrive in random order. After seeing each one, you must accept or reject them immediately, knowing only how they rank against those seen so far. How do you maximize
Solution
Reject the first 37, then accept the first applicant better than all of them. This succeeds with probability . In general, skip about and succeed with probability about .
55. Two envelopes: One envelope holds twice as much as the other. You open one and see . The argument "the other holds or with equal chance, so it is worth on average" says you should always swap. What is wrong with it?
Solution
It assumes for every , which no proper prior distribution allows. Under any real prior, seeing tells you something about which envelope you hold, and the expected gain from swapping is 0.