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. Solution: Highlight the part between the * symbols for the answer. * Answer: 11 dimsums. In general for coprime box sizes p and q, the largest unattainable number is the Frobenius number pq - p - q. For 7 and 3: 11 = 7a + 3b has no non-negative solution (a = 0: 11 not divisible by 3; a = 1: 4 left, not a multiple of 3). But 12 = 4x3, 13 = 7 + 2x3, 14 = 2x7, and from then on every number is 12, 13 or 14 plus a multiple of 3 - so every n >= 12 is buyable and 11 is the answer. General proof sketch: since gcd(p, q) = 1, the numbers 0, q, 2q, ..., (p-1)q hit every residue class mod p. The smallest representable number in class r is t_r = k_r q for the unique k_r in 0..p-1 with k_r q = r (mod p)...

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?  Solution: Highlight the part between the * symbols for the answer. * The SMALLER (50-bed) hospital is more likely to have an exactly equal split. P(exactly 25 boys in 50) = C(50, 25) / 2^50 = 11.2%; P(exactly 250 in 500) = C(500, 250) / 2^500 = 3.6%. The exact-split probability falls like 1/sqrt(pi*n) (Stirling), so it shrinks as the hospital grows. No contradiction with the Law of Large Numbers: the LLN is a statement about PROPORTIONS - P(|boys/n - 1/2| < epsilon) -> 1 for any fixed epsilon - not about hitting exact equality. The f...

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. Solution: Highlight the part between the * symbols for the answer. * Answer: 4. This is the Erdos-Szekeres theorem: any sequence of (a-1)(b-1) + 1 distinct numbers contains an increasing subsequence of length a or a decreasing subsequence of length b. With 10 = 3*3 + 1 soldiers, some monotone subsequence of length 4 always exists. Quick proof: label each soldier with (i, d) = (length of the longest increasing subsequence ending at him, longest decreasing one). If two soldiers got the same label, the taller-later / shorter-later comparison would extend one of the two subsequences - so all labels are distinct. If no monotone subsequence had length 4, all lab...

Source: Sent to me by Prateek Chandra Jha (IIT Bombay) Problem: This problem is inspired by the Cheryl's Birthday Puzzle ( FB Post , Guardian Link ). Paul, Sam and Dean are assigned the task of figuring out two numbers. They get the following information: Both numbers are integers between (including) 1 and 1000 Both numbers may also be identical. Paul is told the product of the two numbers, Sam the sum and Dean the difference. After receiving their number, the following conversation takes place: Paul: I do not know the two numbers. Sam: You did not have to tell me that, I already knew that. Paul: Then I now know the two numbers. Sam: I also know them. Dean: I do not know the two numbers. I can only guess one which may probably be correct but I am not sure. Paul: I know which one you are assuming but it is incorrect. Dean: Ok, I also know the two numbers. What are the two numbers? Disclaimer: Its not a puzzle for 14-15 year olds like Cheryl's Solution: H...

Source: Alok Goyal Puzzle Page ( http://alokgoyal1971.com/ ) . Alok is ex-IIT Delhi, Partner at Helion VC Problem: Part I (Easy): Using a clock, divide a pizza among 12 people Part II (Difficult): Using a clock, divide a pizza among 11 people? Solution: Highlight the part between the * symbols for the answer. * Part I (12 people): cut along the radii pointing at the 12 hour marks - they are evenly spaced at 360/12 = 30 degrees, giving 12 equal slices. Part II (11 people): use the 11 moments in 12 hours when the hour and minute hands exactly overlap (12:00, ~1:05:27, ~2:10:54, ..., ~10:54:33). The minute hand gains 330 degrees per hour on the hour hand, so successive overlaps are 12/11 hours apart, and the overlap direction advances by exactly 360/11 degrees each time. Those 11 radii are therefore equally spaced - cutting along them divides the pizza into 11 equal slices. Bonus extension from the comments: minute and second hands overlap 59 times an hour - the ...

Source: Asked to me by Ankush Jain (CSE IITB 2011, Morgan Stanley Quant Associate). He took it from Algorithms Design book by Tardos and Kleinberg Problem: Easy case: You’re trying to buy equipments whose costs are   appreciating. Item i appreciates at a rate of r_i  > 1 per month, starting from  $100, so if you buy it t months from now you will pay 100*((r_i)^t) .  If you can only buy one item per month, what is the optimal order in which to  buy them? Difficult case: You’re trying to sell equipments whose costs are depreciating . Item  i  depreciates at a rate of  r_i  < 1 per month, starting from  $100, so if you sell it  t  months from now you will get  100*((r_i)^t) .  If you can only sell one item per month, what is the optimal order in which to sell  them? Solution: Highlight the part between the * symbols for the answer. * Buying (appreciating, r_i > 1):...

Source: Sent to me by Sudeep Kamath Problem: Airline check-in baggage has size restriction by ​so-called ​linear dimension: length + breadth + height should not exceed 62 inches. Prove that you can't "cheat" by packing a box with higher linear dimension into a box with ​lower​ linear dimension. Solution: Posted by GoKu in comments!

Source: Mailed to me by Kushagra Singhal, Ex-IIT Kanpur, PhD Student at University of Illinois at Urbana-Champaign Problem: Prove that for any positive K and a natural number n, every (n*K)th number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence. More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K). Solution: Posted by Alex_IITD in comments!

Source: Mailed to me by JDGM ("regular commenter JDGM") Problem: The integers greater than zero are painted such that: • every number is either gold or silver. • both paints are used. • silver number + gold number = silver number • silver number * gold number = gold number Given only this information, for each of the following decide whether it is a gold number, a silver number, or could be either: 1.) gold number * gold number 2.) gold number + gold number 3.) silver number * silver number 4.) silver number + silver number Solution: Highlight the part between the * symbols for the answer. * First, the whole colouring is forced into one shape: pick any G > 1 and let gold = multiples of G, silver = everything else. Proof: 1 is silver (if 1 were gold, then silver x 1 would have to be gold by rule 2 - contradiction). Let G be the smallest gold number, so 1..G-1 are silver. Rule 1 (silver + gold = silver) then makes every non-multiple of G silver (write it as kG + r, 0 < r...

Source: Asked to me by a friend - who was asked this question in an interview at Facebook Problem: Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm? Solution: Highlight the part between the * symbols for the answer. * O(n^2) algorithm: the optimal line passes through at least two of the points (otherwise rotate/translate it until it does without losing collinear points). So for each point p, compute the slope from p to every other point and tally frequencies in a hash map (use exact rational slopes dy/dx reduced by gcd, plus a sentinel for vertical lines - avoid floating point). The most frequent slope from p, plus p itself, gives the best line through p. Take the maximum over all p. Complexity: n points x O(n) slope computations and hash updates = O(n^2) expected time, O(n) space per round. (Deterministic O(n^2 log n) via sorting slopes instead of hashing.) This is worst-...

Source: Sent to me by Pritish Kamath ( http://www.mit.edu/~pritish/ ) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclag...

Source:   Mind Your Decisions Blog Related Problem:   Expected Length of Last Straw - Breaking the back of a Camel - CSE Blog Problem: Your boss tells you to bring him a cup of coffee from the company vending machine. The problem is the machine is broken. When you press the button for a drink, it will randomly fill a percentage of the cup (between 0 and 100 percent). You know you need to bring a full cup back to your boss. What’s the expected number of times you will have to fill the cup? Example:  The machine fills the cup 10 percent, then 30 percent, then 80 percent–>the cup is full plus 20 percent that you throw away or drink yourself. It took 3 fills of the cup. Solution: Highlight the part between the * symbols for the answer. * Answer: e = 2.71828... fills. Let X_i be the fraction dispensed on press i (uniform on [0,1]) and S_k = X_1 + ... + X_k. You press a (k+1)-th time exactly when S_k < 1, so the expected number of presses is 1 + su...

Source: AUSTMS Gazette 35 Related Problem: Pebble Placement Puzzle 1 Problem: Peggy aims to place pebbles on an n × n chessboard in the following way. She must place each pebble at the center of a square and no two pebbles can be in the same square. To keep it interesting, Peggy makes sure that no four pebbles form a non-degenerate parallelogram. What is the maximum number of pebbles Peggy can place on the chessboard? Solution: Highlight the part between the * symbols for the answer. * Answer: 2n - 1. Construction: fill the entire first row and first column - 2n - 1 pebbles. Any further pebble at (r, c) completes a rectangle (a non-degenerate parallelogram) with the pebbles at (r, 1), (1, c) and (1, 1), so nothing more can be added. Upper bound: suppose row i contains N_i pebbles in columns C_i1 < C_i2 < ... . Within row i, consider the N_i - 1 differences C_ij - C_i1 (j >= 2). Across all rows this gives N - n differences, where N is the total number of pebbles, e...

Source: AUSTMS Gazette 35 Problem: There are several pebbles placed on an n × n chessboard, such that each pebble is inside a square and no two pebbles share the same square. Perry decides to play the following game. At each turn, he moves one of the pebbles to an empty neighboring square. After a while, Perry notices that every pebble has passed through every square of the chessboard exactly once and has come back to its original position. Prove that there was a moment when no pebble was on its original position. Solution: Highlight the part between the * symbols for the answer. * Consider the moment just before the FIRST pebble (call it x) completes its tour - i.e. x has visited every square exactly once and is about to step back onto its original square. At that moment, look at any other pebble y. If y were sitting on its own original square, there are two possibilities. Either y left at some point and came back - but then y had already completed a full tour and returned...

Source: Australian Mathematical Society Gazette Puzzle Corner 34 Problem:  Begin with n integers x1, . . . , xn around a circle. At each turn, simultaneously replace all of them by the absolute differences Repeat this process until every number is 0, then stop. Prove that this process always terminates if and only if n is a power of 2. Shameless plug: Follow CSE Blog on CSE Blog - Twitter and CSE Blog on Quora . :-) Solution: Highlight the part between the * symbols for the answer. * These are Ducci sequences; the answer is driven by arithmetic mod 2. Step 1 (mod 2): over GF(2), absolute difference is just addition: x_i -> x_i + x_(i+1). After k steps the entries are given by binomial coefficients of (1+z)^k around the cycle. If n = 2^m, then (1+z)^n = 1 + z^n (mod 2), and around a cycle of length n, z^n = 1 - so after n steps every entry becomes x_i + x_i = 0: all even numbers. If n is not a power of 2, write n = 2^m * k with k odd > 1: the 3-cycle (0,1...

Source: Australian Mathematical Society Gazette Puzzle Corner 35 Problem: There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total of W grams. Suppose W is less than the number of weights on the left multiplied by the number of weights on the right. Is it always true that we can remove some, but not all, of the weights from each side and still keep the two sides balanced? Solution: Highlight the part between the * symbols for the answer. * Yes - in fact something stronger holds: some single weight sits on BOTH pans, so removing that one weight from each side keeps the balance. Proof (Govind's): let the left pan hold m weights a_1 < ... < a_m and the right pan n weights b_1 < ... < b_n, with both sums equal to W < mn. Suppose no weight value appears on both ...