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.

Source: Asked to me by Ram Kumar, a frequent visitor to this blog. Problem: There's a duck swimming in a circular lake with a wolf at the edge. wolf won't enter water. Duck in water is slower than Wolf on land. Duck on land is faster than the Wolf on land. Given the lake diameter 'd' and wolf speed 'w', what is the minimum speed of the duck in water so that he can escape? what should be his escape strategy? Hint: 1) Its less than w/4. 2) There is pi involved. :) Solution: Answer given by Vivek Jha (EE, IITB) in the comments. Proof of the solution given by me in the comments of one of the earlier posts: http://pratikpoddarcse.blogspot.com/2009/11/polyas-urn-problem.html?showComment=1258400372028#c8784580092886919079

Source: http://www.crackpuzzles.com/ You have hired a worker to clean your garage. The wage is a gold bar (which has 7 parts like a chocolate bar) for a weeks work. However, you don’t want to give the complete bar in the start. You want to pay the person 1 part for each day of his work. So at the end of first day he should have 1 part, at the end of second day 1 part more (a total of 2 parts), third day 1 part more (3 parts total)…at the end of the week all 7 parts. What is the minimum number of pieces that you should break the gold bar in to pay the worker? Update: As pointed by Ramdas, this question is not very well framed. There are a few assumptions that you need to make. :)

Suppose you have a hotel which has one floor with infinite number of rooms in a row and all of them are occupied. A new customer wants to check in, how will you accommodate her? What if infinite number of people want to check in, how will you accommodate them then? Hint: Define infinity. :) Update (18/12/09): Solution in comments by Nikhil Pandey (CSE, IITB alumnus)

Source: Anshum Agarwal (Jaadu) mailed me this problem 2-3 months back. I could solve it. :) Interesting problem. Problem: Assume 100 ants are moving in 1 dimensional plane. All move with the same speed. Some are moving towards the positive x axis and some towards negative. If a collision occurs between two ants both ants changes the direction. If you are given direction of motion of each ant, how will you calculate the number of collisions that will occur? Update (11/12/09): Solution: (Provided by Asad in Comments)

I find number sequences interesting. More because of their abstractness, their ability to surprise you, the infinite possibilities you need to explore, etc, etc. Basically the aha! factor. I found one today and was completely baffled. I would not say this is the best "puzzle" and so I am posting solution with the problem but still interesting as it is weird :) Problem: What comes next? 1, 11, 21, 1211, 111221…. Solution: Highlight the part between the * symbols for the answer. * It’s known as Morris Number Sequence. What happens basically is you count the number of times a number appears in the sequence and write in next. So first number is 1 read as one 1 leading to the next number 11, which in turn is two 1. Therefore the next number in sequence is 21. 21 is read as one 2 one 1 leading to the next number in sequence 1211 which is now read as one 1 one 2 two 1 i.e. 111221. Next number becomes 312211 followed by 13112221, 1113213211 & it continues. :) *

Problem: 7 thieves wanted to lock the treasure looted from a ship. They wanted to put locks to the treasure where each lock had multiple keys. Find the minimum number of locks N and minimum no. of keys K with every thief subject to the following conditions:- All the locks should open each time a majority of thieves(4 or more) try to open the locks. At least one lock remains unopened if less than 4 thieves try opening them. All locks should have same no. of keys. All thieves must have same no. of keys with them. Source: Shamir's paper on Secret Sharing Scheme states this problem and gives the answer with the explanation that its written in standard Combinatorics books Update (11/12/09) Solution: Provided by Jaadu in comments!!

Source: Placement Paper of one of the CS companies Problem: A coin is tossed 10 times and the output written as a string. What is the expected number of HH? Note that in HHH, number of HH = 2 Example: In 3 tosses HHH (2 HH) HHT (1 HH) HTH (0 HH) HTT (0 HH) THH (1 HH) THT (0 HH) TTH (0 HH) TTT (0 HH) Expected number of HH in 3 tosses = 2/8 + 1/8 + 1/8 = 0.5 Update (11/12/09): Solution:   Posted by Asad in Comments!!

This was the killer one. Interesting problem asked to me in one of the interviews. You are given a black-box which returns a random number between 0 and 1. Give an algorithm to generate a point in the circle of radius 1. (I was able to solve this but I must admit, its a difficult problem) Update (December 10 2009) : To make things concrete: The black-box here returns a random number "uniformly" between 0 and 1. The question is to find a point "uniformly" in a unit circle. This would mean that the probability that a random point in the circle lies in a smaller concentric circle of radius r (r<1) is r^2. Solution by Jaadu in comments!!

Three question related to stick breaking. A stick is of length 1. 1) The stick drops and breaks at a random point distributed uniformly across the length. What is the expected length of the smaller part? (Source: DB interview) 2) In the above experiment, what is the expected length of the larger part? (Source: Made it up) 3) In the third experiment, the stick is dropped and breaks at two points. What is the probability that the three pieces could form a triangle? (Source: V.K.Bansal notes, MathOverflow.net) Update (18/12/09): Solution: Partial solution by Aaditya Ramdas (CSE IITB 2005-2009) and Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) and complete solution by me in comments.

This was asked to me on Dec 1 in campus interviews of one of the companies. We have a cube. An ant is on one of the corners. It moves randomly with equal probability in all the three directions. What is the expected number of steps to reach the opposite corner. Note that the probability of the ant reaching the opposite corner in 2 steps is 0, in 3 steps is 6/27, in 4 steps is 0 and so on.. (I was able to solve it :D) Update (11/12/09): Solution posted by Anshum (Jaadu, CSE, IITB) in comments!!

Some real stud people told me that my blog helped them a lot in their interviews at IITB Campus placements. I am really happy about that. I must admit that my blog helped me too :P. In Morgan Stanley QM interview, about half the questions that were asked to me were from my blog. (Although I never pretended that I am thinking and then solving. I always told them that I have seen this problem before. But still, it gives you an extra delta point). In Deutsche Bank GMC interview, more than half of the questions were from the blog. I would really recommend all puzzle enthusiasts and also people who would be preparing for placements 2010-2011 to solve the book (Mathematical Puzzles: A Connoisseur's Collection) by Peter Winkler. Thanx for all your reviews on the blog. I am especially happy as I got responses from many friends after they were placed that my blog helped them. :) Thanx junta! Best of Luck!