CSE Blog - quant, math, computer science puzzles

Source: Asked to me by Nikhil Garg (Sophomore, IIT Delhi) Problem: We have a deck of n cards with cards labeled from 1 to n. Starting at any configuration , we repeat this : If the top card has number k , we reverse the order of top k cards. Prove eventually that 1 would be the top card. I was able to solve it. Very interesting problem. :D Update (03/01/10): Solution: Posted by me in the comments!! Thanx to Giridhar and KP Ashwin (CSE, IITB) for the help.

Problem: n children are sitting around a circular table. Each child starts out with an integer number of candies. The following step is repeated: Every child who has an odd number of candies is given another piece of candy by the teacher. Each child now has an even number. Now every child passes half of his/her candy to the child on his/her left. Prove that eventually all the children will have the same amount of candy. Source: Puzzle Toad, CMU Update (30/12/09): Solution: PDF Document from CMU Site

Problem: A set of fuel dumps on a circular racetrack have just enough gasoline for one car to make one round trip. Prove that there exists a fuel dump from which one car, starting with an empty gas tank, can complete the round trip. Source: Read it in many puzzle books. This form taken from Manku's blog. Update (30/12/09) Solution: From the site cut-the-knot.org in comments!!

Four ships are sailing on a 2D planet in four different directions. Each ships traverses a straight line at constant speed. No two ships are traveling parallel to each other. Their journeys started at some time in the distant past. Sometimes, a pair of ships collides. A ship continues its journey even after a collision. However, it is strong enough only to survive two collisions; it dies when it collides a third time. The situation is grim. Five of six possible collisions have already taken place (no collision involved more than 2 ships) and two ships are out of commission. What fate awaits the remaining two? Update June 18, 2010 Solution: Let z-axis denote time. let x- and y- axes denote the 2D planet. Then the four trajectories are straight lines. Since no collision involved more than two ships, these four lines must all lie in a plane. So, one might be tempted to believe that the two other ships will also collide. But, they might have collided in negative time. So, it cannot b...

Problem: You are the chief guest at an auction, where some number of horses will be auctioned, one after the other, randomly permuted. You are a connoisseur of horses, and can judge whether one horse is ‘better’ than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better? Source: Fifty Challenging Problems in Probability with Solutions by F Mosteller Disclaimer/Hint: If you are even half like me, you would love attempting this puzzle. Just do it using basic math and you will hit it right. The solution would even imply "Birthday Paradox" beautifully. :) Update: (22/12/09) Solution posted by Giridhar in comments.

Source: Classic combinatorics problem. Read it at a lot of places. Also in wikipedia Wiki Link Problem: Nine schoolgirls are to be arranged in three rows and three columns on four different days so that any pair of schoolgirls is in the same row on exactly one of the four days. Update: (18/12/09) Hint was wrong and hence removed. Solution by Giridhar in comments. Some discussion by me in comments.

Source: Tejas Hiremani (EE, IITB) asked this question. I had read it before in Peter Winkler's puzzle book and Carnegie Mellon's Puzzle Toad site. Nice problem. Problem: Given 3 buckets containing x,y,z litres of water. Assume buckets have "large" size. x, y, z are integers. You can move water from one bucket to another only if the bucket to which water is being transferred doubles the amount of water it has. So, all moves have to of the form: If water is being moved from bucket containing x litres to bucket containing y litres. After the operation, the bucket containing y litres has 2y litres and the first bucket has x-y litres. Show that you can always empty one of the buckets. :) Update (18/12/09): Solution: One solution posted by Aaditya Ramdas (CSE, IITB alumnus - Tower Research Analyst) in comments. A different solution posted by me in comments.