Probability Puzzles

Classic probability and logic puzzles with answers.

Probability Puzzles

Notation: P(A)P(A) is the probability of event AA, P(A∣B)P(A \mid B) the probability of AA given BB, and E[X]\mathbb{E}[X] the expected (average) value of XX. Hn=1+12+⋯+1nH_n = 1 + \tfrac12 + \dots + \tfrac1n is the nn-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 P(both boys)?P(\text{both boys})\text{?}

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 P(both boys)?P(\text{both boys})\text{?}

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 P(both boys)?P(\text{both boys})\text{?}

Solution

13/27. Of the 14214^2 equally likely (sex, weekday) pairs, 27 contain a Tuesday boy, and 13 of those are two boys (7+7−17 + 7 - 1). 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 P(two-headed)?P(\text{two-headed})\text{?}

Solution

2/3. By Bayes' rule, 1/21/2+(1/2)(1/2)=23\frac{1/2}{1/2 + (1/2)(1/2)} = \frac23. After kk heads in a row it is 1/(1+2−k)1/(1 + 2^{-k}), so 8/98/9 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 P(the other side is red)?P(\text{the other side is red})\text{?}

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 P(disease)?P(\text{disease})\text{?}

Solution

11/122≈9%11/122 \approx 9\%. Bayes gives 0.001×0.990.001×0.99+0.999×0.01\frac{0.001 \times 0.99}{0.001 \times 0.99 + 0.999 \times 0.01}. 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. P(N=n,all even)=(1/3)n−1(1/6)P(N = n, \text{all even}) = (1/3)^{n-1}(1/6), which sums to 1/41/4. So NN given all-even is geometric with success probability 2/32/3, and its mean is 3/23/2. Restricting the die to {2,4,6}\{2, 4, 6\} 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

E[HH]=6\mathbb{E}[\text{HH}] = 6 and E[HT]=4\mathbb{E}[\text{HT}] = 4. Similarly E[HHH]=14\mathbb{E}[\text{HHH}] = 14, E[HTH]=10\mathbb{E}[\text{HTH}] = 10 and E[HTT]=8\mathbb{E}[\text{HTT}] = 8. Patterns that overlap with themselves take longer, because a failure after a partial match sends you further back. A run of nn heads takes 2n+1−22^{n+1} - 2 flips on average.

12. Pattern race: Flip a fair coin until TH or HH appears. What is P(TH first)?P(\text{TH first})\text{?}

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

6H6=14.76H_6 = 14.7. Once you have kk faces, the expected wait for a new one is 6/(6−k)6/(6 - k). In general it takes nHn≈nln⁡nnH_n \approx n\ln n draws to collect nn 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 62+66^2 + 6. It also follows from first-step analysis on a two-state chain.

15. Uniforms until the sum exceeds 1: Draw independent Uniform(0,1)(0, 1) numbers until the running sum exceeds 1. What is the expected number of draws?

Solution

e≈2.718e \approx 2.718. P(sum of n draws≤1)=1/n!P(\text{sum of } n \text{ draws} \le 1) = 1/n!, so E[N]=∑n≥0P(N>n)=∑n≥01/n!=e\mathbb{E}[N] = \sum_{n \ge 0}P(N > n) = \sum_{n \ge 0} 1/n! = e.

16. First ace: What is the expected position of the first ace in a shuffled 52-card deck?

Solution

53/5=10.653/5 = 10.6. The 4 aces split the other 48 cards into 5 gaps of equal expected size 48/548/5. Add 1 for the ace itself.

17. Maximum of two dice: What is the expected maximum of two fair dice?

Solution

161/36≈4.47161/36 \approx 4.47. P(max⁡=m)=(2m−1)/36P(\max = m) = (2m - 1)/36.

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

17/4=4.2517/4 = 4.25. Re-roll whenever the first roll is below the average of 3.5, so on 1 to 3: 12(3.5)+16(4+5+6)\tfrac12(3.5) + \tfrac16(4 + 5 + 6). With two re-rolls allowed the answer is 14/3≈4.6714/3 \approx 4.67: keep 5 or 6 on the first roll, then 4 to 6 on the second.

19. Hat check: nn people get their hats back in random order. How many get their own hat, on average?

Solution

1, for every nn. By linearity of expectation it is n×1nn \times \tfrac1n. The chance that nobody gets their own hat tends to 1/e≈0.3681/e \approx 0.368.

20. Longest piece: Break a stick of length 1 at 2 uniform random points. What is the expected length of the longest piece?

Solution

11/18≈0.61111/18 \approx 0.611, which is 13(1+12+13)\tfrac13\big(1 + \tfrac12 + \tfrac13\big).

21. Distinct faces: Roll a fair die 6 times. What is the expected number of distinct faces?

Solution

6(1−(5/6)6)≈3.996\big(1 - (5/6)^6\big) \approx 3.99. 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 P(first player wins)?P(\text{first player wins})\text{?}

Solution

6/11, which is 1/61−(5/6)2\frac{1/6}{1 - (5/6)^2}.

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 P(none in an hour)=P(none in half an hour)2=0.01P(\text{none in an hour}) = P(\text{none in half an hour})^2 = 0.01, so P(none in half an hour)=0.1P(\text{none in half an hour}) = 0.1 and the answer is 1−0.1=0.91 - 0.1 = 0.9. Equivalently, a Poisson process with rate λ=ln⁡100\lambda = \ln 100 per hour gives 1−e−λ/2=0.91 - e^{-\lambda/2} = 0.9.

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

24/7≈3.4324/7 \approx 3.43 days. Add rates, not times: together they do 16+18=724\tfrac16 + \tfrac18 = \tfrac{7}{24} of the job per day, so the job takes 247\tfrac{24}{7} 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 144×0.5=72144 \times 0.5 = 72 km.

Combinatorics

26. Birthday problem: Ignoring leap years and assuming all 365 birthdays are equally likely, how many people are needed for P(some shared birthday)P(\text{some shared birthday}) to exceed 1/2?

Solution

23 (P=0.507P = 0.507; with 22 it is 0.4760.476). It reaches 0.9700.970 at 50 people. The number is small because what matters is pairs: 23 people form (232)=253\binom{23}{2} = 253 pairs.

27. Ballot problem: Person A gets pp votes and person B gets qq, with pp greater than qq. The votes are counted in random order. What is the probability A stays strictly ahead throughout?

Solution

(p−q)/(p+q)(p - q)/(p + q). 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 kk, for k=1,…,100k = 1, \dots, 100, every kk-th bulb is toggled. How many end up on?

Solution

10. Bulb nn is toggled once per divisor of nn, so it ends on exactly when nn has an odd number of divisors, which happens only for perfect squares.

29. Josephus problem: nn people, numbered 1 to nn, stand in a circle. Going round from person 1, every second person is eliminated (2, 4, …) until one is left. Who survives?

Solution

Position 2L+12L + 1, where n=2m+Ln = 2^m + L with 0≤L0 \le L and LL less than 2m2^m. For n=100n = 100 that is position 73; for n=41n = 41 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 210=1024≥10002^{10} = 1024 \ge 1000. Number the bottles in binary; tester ii drinks from every bottle whose ii-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 12×2=2412 \times 2 = 24 cases and 33=273^3 = 27 outcomes. The most 3 weighings can handle is (33−3)/2=12(3^3 - 3)/2 = 12 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 kk colours. Drawing in the dark, how many must you take to guarantee a matching pair?

Solution

k+1k + 1, by the pigeonhole principle.

Geometry and probability

34. Broken stick triangle: Break a stick at 2 uniform random points. What is P(the 3 pieces form a triangle)?P(\text{the 3 pieces form a triangle})\text{?}

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 P(the triangle contains the centre)?P(\text{the triangle contains the centre})\text{?}

Solution

1/4. It fails exactly when all 3 points lie in some semicircle, which has probability n/2n−1=3/4n/2^{n-1} = 3/4 for n=3n = 3.

37. Clock hands: How many times do the hour and minute hands overlap in 12 hours?

Solution

11 times, every 720/11≈65.45720/11 \approx 65.45 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 =1−(H100−H50)≈31%= 1 - (H_{100} - H_{50}) \approx 31\%. Everyone succeeds exactly when the random permutation has no cycle longer than 50. Guessing independently gives 2−1002^{-100}; 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 nn with n(n+1)/2≥100n(n + 1)/2 \ge 100. 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 (91)+(92)+(93)=129≥100\binom91 + \binom92 + \binom93 = 129 \ge 100.

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 aa and bb can measure exactly the multiples of gcd⁡(a,b)\gcd(a, b) up to the larger size; here gcd⁡(3,5)=1\gcd(3, 5) = 1, 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 f(n)=a0+a1n+⋯+adndf(n) = a_0 + a_1 n + \dots + a_d n^d 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 f(1)=Sf(1) = S, the sum of the coefficients, so every coefficient is at most SS. Then query f(S+1)f(S + 1): since every coefficient is smaller than S+1S + 1, the coefficients are exactly the digits of f(S+1)f(S + 1) written in base S+1S + 1. If coefficients may be negative, no fixed number of queries works without a bound on their size, since a(n−n3)a(n - n^3) is 0 at both n=1n = 1 and n=−1n = -1 for every aa; given a bound BB, one query at M>2BM > 2B decoded as balanced base-MM digits suffices. If the degree dd is known instead, d+1d + 1 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 2/62/6.

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 66.766.7, then 44.444.4, 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 3⊕4⊕5=23 \oplus 4 \oplus 5 = 2, 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 P(reach 100)?P(\text{reach } 100)\text{?} What if each step wins with probability p=0.49p = 0.49, starting at 10 with target 20?

Solution

10/100=1/1010/100 = 1/10 for the fair game, and about 0.4010.401 for the biased one, from 1−rk1−rN\frac{1 - r^k}{1 - r^N} with r=q/pr = q/p. A walker 1 step from a cliff who steps away with probability 2/3 eventually falls with probability (1/3)/(2/3)=1/2(1/3)/(2/3) = 1/2.

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 P(choosing the best)?P(\text{choosing the best})\text{?}

Solution

Reject the first 37, then accept the first applicant better than all of them. This succeeds with probability ≈0.371\approx 0.371. In general, skip about n/en/e and succeed with probability about 1/e1/e.

55. Two envelopes: One envelope holds twice as much as the other. You open one and see XX. The argument "the other holds 2X2X or X/2X/2 with equal chance, so it is worth 1.25X1.25X on average" says you should always swap. What is wrong with it?

Solution

It assumes P(yours is the smaller∣X)=1/2P(\text{yours is the smaller} \mid X) = 1/2 for every XX, which no proper prior distribution allows. Under any real prior, seeing XX tells you something about which envelope you hold, and the expected gain from swapping is 0.