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

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible?  Solution: Highlight the part between the * symbols for the answer. * This is Simpson's Paradox: each topic on its own shows one trend, but the combined score shows the opposite. Arithmetic is the easier topic - both students score a higher fraction there (Siddhant 5/6 = 83.3%, Vaibhav 20/25 = 80%) than in Geometry (Siddhant 20/28 = 71.4%, Vaibhav 6/9 = 66.7%). But the two tests mixed the topics very differently. Vaibhav's...

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.

Problem: There are two maternity hospitals in a town with 50 and 500 beds. Given full occupancy on a particular day, which of these hospitals is more likely to have equal no of boys and girls given probability of boys = probability of girls ? ‪ What would the answer intuitively be by #‎LawOfLargeNumbers‬? You would see #LawOfLargeNumbers does not seem to work here. How should the statement be positioned for #LawOfLargeNumbers to work? 

Source: Alok Goyal (Stellaris VP) puzzle blog Problem: This is another famous puzzle in the Martin Gardner collection, and variations of this puzzle exist in different “sizes”. This particular one has been picked up from The Colossal Book of Short Puzzles and Problems, Puzzle 9.18. Replicating the puzzle as is. Lenox R. Lohr, president of the Museum of Science and Industry in Chicago, was kind enough to pass along the following deceptively simple version of a type of combinatorial problem that turns up in many fields of applied mathematics. A traveler finds himself in a strange town without funds; he expects a large check to arrive in a few weeks. His most valuable posession is a gold watch chain of 23 links. To pay for a room he arranges with a landlady to give her as collateral one link a day for 23 days. Naturally, the traveler wants to damage his watch chain as little as possible. Instead of giving the landlady a separate link each day he can give her one link the first...

Source:  Alok Goyal's Puzzle Page Problem: In a line up of 10 soldiers, what is the least number of soldiers that can be picked in order of either ascending or descending heights? Assume that no two soldiers have the same height. Soldiers can be picked from anywhere in the line, but their order of standing cannot be changed.