CSE Blog - quant, math, computer science puzzles

Source: Peter Winkler, "Seven Puzzles You Think You Must Not Have Heard Correctly" (devised by Peter Bro Miltersen). Problem: The names of 100 prisoners are placed in 100 boxes, one name per box. Each prisoner enters alone and may open at most 50 boxes. Unless EVERY prisoner finds his own name, all are executed. Random guessing works with probability (1/2)^100. Find a strategy with success chance over 30%. Solution: Highlight the part between the * symbols for the answer. * Number the boxes 1-100. Each prisoner opens his own box, then the box of the name inside, following the chain. He succeeds iff his cycle has length at most 50. All survive iff no cycle exceeds 50: P(fail) = 1/51 + ... + 1/100 = 0.688, so P(survive) = 0.312, tending to 1 - ln 2 = 30.7%. *

An old classic that still trips people up in interviews. The obvious answer is not the best one. Problem: Four friends have to cross a rickety rope bridge at night with one torch; the bridge holds at most two people and cannot be crossed without the torch. They take 1, 2, 5 and 10 minutes to cross; a pair moves at the slower person's pace, and the torch must be carried back after each crossing. The obvious plan - let the 1-minute guy ferry everyone across - takes 19 minutes. Do better. Solution: Highlight the part between the * symbols for the answer. * 17 minutes. Send the slow pair together: 1 and 2 cross (2), 1 returns (3), 5 and 10 cross (13), 2 returns (15), 1 and 2 cross (17). The two slow walkers must share a trip, else they alone burn 15 minutes, and a fast walker must wait on the far side to return the torch, so 1 and 2 cross first; the rest is forced. *