CSE Blog - quant, math, computer science puzzles

Jaadu asked me this question in a Convex Optimization Class this semester. I was able to solve it. He said it was in one of Diwan Sir tutorials. :) Interesting puzzle!! You are given N coins (assume N to be of the form 2^k). Some are light and other are heavy.You are given one weighing machine. What is the number of weighing required to find the number of coins that are heavy? A hint: Try to divide the coins in two equal parts such that each have both have same number of heavy coins. Previously asked coin puzzles: Coins Puzzle Consecutive Heads Five Thieves and Bounty Update (11/12/09): Solution in comments!! Update (11/12/11): Weighing machine here is a weighing balance. Its a function isXgtY {Input X: Set of Weights, Input Y: Set of Weights, Output Bool 1 if X>Y and 0 if X<=Y}

Once again.. Another coin puzzle after this and this (I wonder whether puzzles have anything else other than hats, kings and coins :D) I heard this from Rushabh Sheth (Mech Sophie) who got it from Vivek Jha (Elec Thirdie). There are 100 coins on the table out of which 50 are tail-face up and 50 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two equal halves such that both have equal number of coins with tails face up. (This obviously implies that the two have equal number of coins with heads face up) Second part: There are 100 coins on the table out of which 10 are tail-face up and 90 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two halves (not necessarily equal) such that both have equal number of coins with tails face up. Update (02/01/10): Sorry for inducing confusion in the system. :

IBM Launches one puzzle every month in its "Ponder This" section. I just came to know about it day before yesterday and sent my solution for the active challenge. Check my name at http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/October2009.html The Puzzle is not mathematical though :P Complete the following sequence: 1, 13, 2, 1, 5, 3, 2, 1, 4, 4, 7, 3, 1, 5, 3, 5, ?, ? Hint: The solution is related to a quote about mathematicians. You can do it only if you know it. Thinking does not really help!! :) PandeyJi (Nikhil Pandey) said that he was able to solve it. :) Solution: IBM guys will post it on their link in 2 days anyways! :)

This puzzle was asked to me last year by Manish Agarwal. He said that the answer was 20km. A 120 wire cable has been laid firmly underground between two telephone exchanges located 10km apart. Unfortunately after the cable was laid it was discovered to be the wrong type, the problem is the individual wires are not labeled. There is no visual way of knowing which wire is which and thus connections at either end is not immediately possible. You are a trainee technician and your boss has asked you to identify and label the wires at both ends without ripping it all up. You have no transport and only a battery and light bulb to test continuity. You do have tape and pen for labeling the wires. What is the shortest distance in kilometers you will need to walk to correctly identify and label each wire? Update (11/12/09) : Solution posted in comments!

Jaadu asked me this puzzle during our work visit to IBM Pune Problem: You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1024 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned. The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison. You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned. You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed. What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours? Solution: Highlight the part between the * symbols for the answer. * 10 prisoners must sample the wine.

This puzzle again is from Haidong's website. Problem: There are n people, each with a unique number from 1 to n. There are n identical lockers, each of which contains a paper with a unique number from 1 to n on it. However, you have no idea which locker contains what number. The purpose is for everyone to find the locker with his own number. Each one can open at most n/2 lockers and, once he looks at the number, he has to close the locker. If another person wants to see the same locker, he has to open it again himself. They can't exchange information with each other. Prove that there exists a certain constant that no matter how big n is, those people can always devise a strategy so all of them can find their own numbers with probability larger than that constant. Note: this is surprising because if everyone picks n/2 lockers independent of other people, the probability that all of them find their own numbers is 1/(2^n), which goes to 0 as n goes to infinity. I don't

Another hat puzzle (One of the previous hat puzzles was this ) Source: Stanford student Haidong Wang A teacher puts on 10 hats of either red or blue on 10 students. Each one can see the hats on all other 9 students, but not his own. The teacher tells them that at least one of the hat is blue. The teacher asks each one to write down the color of his hat if he's sure about it, or he can write down "don't know" if he can't deduce its color. Everyone reveals their answer at the same time and all of them write "don't know". The second day, they gather again and the teacher puts on the same hats. Each one has to think about the color of his hat again. This time, still no one can figure out his hat color (i.e. everyone writes down "don't know"). This game repeats in the same way on third day, fourth day, ..., until the ninth day. Still no one figures out. However, on the tenth day, everyone writes down the correct color of his hat. So expl

Problem: If the probability of observing a car on a highway in 20 minutes time is 609/625 then what is the probability of observing a car in 5 minutes time on the same highway (considering all the factors involved to be uniform)? Solution: Highlight the part between the * symbols for the answer. * Probability of seeing a car in 20 minutes = 609/625 => Probability of not seeing a car in 20 minutes = 1 - 609/625 = 16/625 => (Probability of not seeing a car in 5 minutes)^4 = 16/625 => Probability of not seeing a car in 5 minutes = (16/625)^(1/4) => Probability of not seeing a car in 5 minutes = 2/5 Hence, the Probability of seeing a car in 5 minutes = 1 - 2/5 = 3/5 *

Consider a loop of string of unit length. Suppose we cut the string independently and at random in n places. This will divide the loop into n pieces. 1. What is the expected (average) size of the smallest piece? 2. What is the expected (average) size of the largest piece? If you can't find an exact answer the asymptotic behaviour (to leading order) as n goes to infinity will suffice. Update (11/12/09): Solution in comments!!

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)

Roll a die, and you get paid what the dice shows. if you want, but you don't have to, you can roll the die again and get paid what the second roll shows instead of the first. What is the expected value? Update (11/12/09): Solution by Pintu Kumar (CSE, IITB) in comments!! Update (21/01/10): Solution posted by Pintu was wrong. Correct solution posted in comments by me!!

Posted by Mensen at mathoverflow.net Very interesting problem (Very difficult actually) Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. What is the probability 'p' that the minimum distance between any pair of these points is larger than some value 'k' or an expression for the mean minimum distance (MMD) for a pair of points in the set - referring to the smallest distance between any two points that can be found, not the mean minimum/shortest distance between all possible pairs of points. Good problem :D ... I am happy!!! Update (11/12/09): Solution in comments!!

From Saurabh Joshi Problem : 9 balls, 8 identical and 1 is lighter. You need to find out in 4 weights, which one is lighter. Sounds simple? Well, hold on. You are given 3 balance weight machines, out of which one is defective. You do not know which one is defective. Also, defective machine can give any outcome ( >, =, < ) irrespective of what you put on the machine. Now, can you find out which ball is lighter weighing only 4 times in total? Update: Easier problem: A defective machine always outputs the same result. Its pointer always moves in the same direction. Tougher problem: The defective machine gives a random result <, >, = all the time Update (11/12/09): Solution in comments!!

Source: P. Winkler In a circle are light bulbs numbered 0 through n-1 all initially on. At time t, you examine the bulb number t mod n, and if its on, you change the state of bulb t+1 mod n. If bulb t is off, you do nothing. Prove that if you continue around and around the ring in this manner, eventually all the bulbs will again be on. Update (Nov 5 2009) : Thanx vivek, the small problem updated. Bulbs numbered 0 to n-1 instead to 1 to n. Thanx. Solution in comments!!

Jaadu mailed me this problem today. I was able to solve it and I am happy. This is an "intelligent" problem. Solution so elegant that you will fall in love with it. :) 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, what is the number of collision that will occur? Give an algorithm. :) Update (11/12/09): Solution by A Rustle (Prathmesh, CSE, IITB) in comments !!

When six dice are rolled, the number of different numbers which can appear range from 1 to 6. Suppose that once every minute, the croupier rolls six dice and you bet $1, at even odds, that the number of different numbers which appear will be exactly 4. If you start with $10, roughly how long will it be, on average before you are wiped out? :) Update (11/12/09): Solution in comments!!

Source: P. Winkler In a room stand n armed and angry people. At each chime of a clock, everyone simultaneously spins around and shoots a random other person. The persons shot fall dead and the survivors spin and shoot again at the next chime. Eventually, either everyone is dead or there is a single survivor. As n grows, what is the limiting probabality that there will be a survivor. :) Treat at H8 canteen for the person solving it first :)

Bol Baby Bol Source: P. Winkler You have an opportunity to make one bid on an object, whose value to its owner is, as far as you know, uniformly random between $0 and $100. What you do know is that you are so much better at operating the widget than he is, that its value to you is 80% greater than its value to him. If you offer more than the widget is worth to the owner, he will sell it. But you get only one shot. How much should you bid? Update (11/12/09) Solution: (First solved by Jaadu) Highlight the part between the * symbols for the answer. * He should not bid (or bid 0$) !! Explanation in comments!! :) *

Problem posed to me by Ankit Goyal (Civil, H2) There are 25 horses. You want to find the best 3. Of course having a race and finding the top 3 is easy, but the constraint is that only 5 horses are allowed to race at once. Find the top 3 horses having minimum number of races. Solution: Post your answer here. The first to reply with a correct answer (except Ankit) gets an H8 canteen treat!!! Update (11/12/09): Solution by angush (Ankur Mishra, H7, IITB) in comments!!

Problem : (Posed by Saurabh Joshi, IIT Kanpur in his blog) Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle? Solution : Highlight the part between the * symbols for the answer. * If a semi-circle covering all n points, indeed exists, then, a semi-circle covering all n points and starting from one of the points in a clock-wise direction also exists. So, given a semi-circle which starts at one of the point in clock-wise direction. The probability that the rest of the n-1 points will be in that semi-circle is 1/(2^(n-1)). So for n such semi-circle, the probability will be n/(2^(n-1)) * :)

Puzzle: After the revolution, each of the 66 citizens of a certain country, including the king, has a salary of $1. The king can no longer vote, but he does retain the power to suggest changes - namely, redistribution of salaries. Each person's salary must be a whole number of dollars, and the salaries must sum to $66. Each suggestion is voted on, and carried if there are more votes for than against. Each voter can be counted on to vote "yes" if his salary is to be increased, "no" if decreased, and otherwise not to bother voting. The king is both, selfish and clever. What is the maximum salary he can obtain for himself, and how long does it take him to get it? (from P.Winkler, loosely inspired by real historical events in Sweden) Update (11/12/09) Solution : Highlight the part between the * symbols for the answer. * 63$ (Thanx to Deeepanshu (Civil, H2) for explanation in comments!! [What a fool I had been :(], Solution provided in Winkler) To start wit