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!

This was the question asked to Anirudh in his google interview. He could not do it (who cares! He got the job :D) I could give a vague but correct answer :) You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place. Of course, O(n) can be done {Compare best-so-far value for each point} But since our set of n points is constant, we would want some pre-processing so that the query time is reduced. :) Interesting problem. Interesting solution.

Four tumblers are placed at the corners of a square table. A blind gnome and an evil goblin take turns to play a game. The blind gnome gets to choose a subset of the four tumblers and flip them simultaneously. Effectively, he may choose “one tumbler”, “two diagonally opposites”, “two adjacent”, “three tumblers” or “four tumblers” lying in front of him. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues: the evil goblin rotates the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy? Source: One of the questions in the placement paper of a quant company at another IIT Update (11/12/09): Solution by Me, Jaadu and Ramdas in comments!!

2^29, expressed in base 10, is a nine-digit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 2^29. This question was posed to me by Dinesh Dharme (CSE, IITB). Simple but interesting puzzle!! Update (11/12/09): Solution in comments!!

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No

Puzzle: An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix? Source: Gurmeet Singh Manku's Blog where he said that he saw it in an old Russian problem book. Solution: Highlight the part between the * symbols for the answer. * There are 36 3×3 blocks and 25 4×4 blocks. Given a sequence of blocks, the same effect is achieved no matter in what order the blocks are chosen. If the same block occurs two times in a sequence, their effect is nullified. Thus, a sequence of blocks is equivalent in effect to some subset of the 36 + 25 = 61 blocks. Starting with all zeros, at most 2^61 distinct configurations out of 2^64 possible configurations of the matrix can be reached. This means that we may not be able to remove all the ones from the original matrix. * Fundoo question!!

I saw this puzzle on the site http://www.crackpuzzles.com/ Suppose two players are playing a game where we call integers. The first person who calls 50 wins. The rules are that the first person calls a number between 1 and 10. After that any new number that is called must exceed the last number by at least one and no more than by 10. For example: If the last number called is 15, then the next number that is called must be between 16-25. I give you the first mover advantage, devise a strategy to win. Update (11/12/09): Solution in comments!!

Source: IITM Friend (who did not want his name to be disclosed). Also read it once in CLR (Introduction to Algorithms) Given an array of n numbers. Finding minimum takes n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 comparisons? Update (11/12/09): Solution by Ameya and Me in comments !!

These problems was posed to me by friends at NBHM Nurture Programme 2007 at IMSc Chennai Problem 1: A shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. How many minimum weights and name the weights you will need to measure all weights from 1 to 1000. Solution 1: Highlight the part between the * symbols for the answer. * The numbers 1,2,4,8,16... This is optimal as each number has exactly one binary representation. So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, 512. :) * ------------------------------------------------------------------------------ Problem 2: Same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and a

Source: P. Winkler I write two different numbers in the range [a,b], one on each hand. You choose one of my hands at random, I show you the number on that hand. You now guess whether the number you've seen is larger than the number you haven't seen. Find a strategy for guessing such that, no matter what two numbers I write, you have GREATER THAN a 50% chance of being correct. Solution: Highlight the part between the * symbols for the answer. * I would choose a number randomly in the range [a,b]. Add 0.5 to it and save the number as k in my memory. If the number I see in one hand is less than k, I would say that the number in the other hand is greater. In the other case, I will say that the number in the other hand is less. One can prove that here, winning probability is greater than 0.5 Let the number that comes out is k' If k' less than k, I am doing well when other number is either greater than k or between k' and k If k' greater than k I

Found it in collection of Jian Li, CS Department, University of Maryland Given 2 cyclic strings, both consisting n distinct letter,namely a permuatation of 1 to n. the problem is to find a rotation of one string that minimize the swap distance.(i.e.the number of swaps of adjacent elements to bring one necklace to the other) Can you give an O(nlogn) algorithm? This is a difficult problem. So, think hard!! Update (11/12/09): Solution in comments !!

Solved a more difficult problem in HC Verma 5-6 years back.. :) Four bugs are on the corners of a 1 meter square. Each bug always faces the next bug (on the next clockwise corner). If they all walk forward at the same speed until they meet, how far does each bug travel? Solution:  Highlight the part between the * symbols for the answer. * Since the bugs always move perpendicular to each other, so when they meet at the center they have traveled a distance equivalent to their initial separation i.e. 1 m. If some of you remember, in the HC Verma problem, the three ants were moving in a equilateral triangle of side-size 1. The three ants were such that 1 is following 2, 2 is following three and three is following 1. By symmetry, they would meet at the centre. The time taken was 2/3v as you had to take components along the line joining the two ants. So, v(1+cos60) was the real relative speed along the line joining two ants. So, time taken was 2/(3v). So, the distance traveled was

Heard this problem many times. This problem is everywhere. You can go to a fast food restaurant to buy chicken nuggets in 6-pack, 9-pack or 20-packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets? Solution: Highlight the part between the * symbols for the answer. * Yes. The number is 44 All numbers can be written in the form 3n-1, 3n or 3n+1. Now taking all nos. of the form 3n, all such numbers (except 3) can be formed by combination of 6 and 9. Now let us take all numbers of the form 3n-1 which are greater than 20, starting with 23, 26, 29.... now again using the same concept like in the last part if we subtract 20(i.e. including a 20 nugget pack) from these numbers, the rest can be formed by combination of 6 and 9 other than 23 which would be the largest such number so far. Similarly we will take all numbers of the form 3n-2 which are greater than 40, starting with 43, 46, 49.... and we will use

I am happy.. I am amongst the first few people to solve IBM Ponder This November Challenge.. This puzzle, unlike the last one, is really challenging and requires mathematical skills. I am posting the puzzle. IBM Guys would post the solution in a month's time. IBM Page What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1) divisor of a number between 2 and 166 (inclusive)? We are asking for the exact answer in two cases: In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions? On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions. * For example, the smallest divisor of 105 is 3, and of 103 is 103. Update (26-05-2011) Solution: First part: Posted by Abhishek Shukla (Indian Institute of Science Education and Research, Kolkata) in comments! Second part: Posted by Siddha

Algorithms: Graph Algorithms Search Algorithms String Algorithms NP Complete Problems Polynomial Time Problems Dynamic Problem Longest Common Substring Longest Increasing Subsequence Longest Common Subsequence Selection Algorithm Some famous paradoxes: Gambler's Fallacy Ellsberg Paradox Two Envelopes Problem Neck Tie Paradox Monty Hall Problem Three Prisoners Problem Bertrand's Box Paradox Boy or Girl Bertrand's Paradox Anti martingale St. Petersburg Paradox Exchange Paradox

Some site said that this is a google interview question: There is an array A[N] of N integers. You have to compose an array B[N] such that B[i] will be equal to the product of all the elements of A[] except A[i]. B[i] = (product from j = 1 to N, j not equal to i) A[i] Example: Input:[4, 3, 2, 1, 2] Output:[12, 16, 24, 48, 24] Solve it without division operator and in O(n). Update (11/12/09) : Solution provided by Subhasis (EE, IITB) in comments!! Update (01/01/10) : Solution for another case provided by Shantanu Gangal, BCG (CSE, IITB alumnus) in comments!!

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

Read about this in Concrete Mathematics - Knuth some time back... Interesting problem There are n persons in a circle, numbered 1 to n. Going around the circle, every second person is removed from the circle, starting with person number 2, 4, and so on. Show that the number of the last person remaining in the circle can be obtained by writing n in binary, then moving the leftmost 1 to the right. So for example, with n = 13 persons (1101 in binary), the last person is number 11 (1011 in binary). Math at : http://en.wikipedia.org/wiki/Josephus_problem Solution: In case of 13, The order in which people die are xxx0 xx01 {Since last bit of 13 was 1, hence xx01, otherwise it would have been xx11} x111 {Since secondlast bit of 13 was 0, hence x111, otherwise it would have been x011} 0011 {Since thirdlast bit ....} So, you would want to be 1011 So, we can see that the solution for a general n is in the bit representation of n, add a bit 1 at the end and remove the first bi

Another puzzle from Krishnamurthy Iyer's website Problem Five thieves have just looted a bounty of 1000 gold coins. The loot has to be divided among them and therein lies the problem. It is then decided that the youngest one will come up with a strategy of division, and the rest will put the strategy to vote. If the strategy is voted with a majority, it will be accepted and will be carried out. Otherwise, the youngest one will be shot and the second youngest will be asked to do the same...and so on. So the problem is, if you are the youngest thief, what will be your strategy, to maximize your share of the bounty? (Assume all thieves have different ages.) Thieves base their decisions on three factors. First of all, each thief wants to survive. Secondly, each thief wants to maximize the amount of gold coins he receives. Thirdly, each thief would prefer to throw another overboard, if all other results would otherwise be equal Update (11/12/09): Solution provided by Jaadu ...

This puzzle is taken from website of Krishnamurthy Iyer (Stanford) Two immensely intelligent players, A & B, engage in a game, the rules of which are as follows. For some natural number N, the board consists of numbers from 1 to N. Each player takes turns to strike off a number from the board, with the added condition that if a number is struck off, then all its divisors should also be struck off. The player to strike off the last number on the board wins. A plays first. Is this game fair? If not, who has a winning strategy for each N and what is it? Else find the best strategy for each player. Update (11/12/09): Solution in comments!!

Puzzle: An evil troll once captured a bunch of gnomes and told them, “Tomorrow, I will make you stand in a file, one behind the other, ordered by height such that the tallest gnome can see everybody in front of him. I will place either a white cap or a black cap on each head. Then, starting from the tallest, each gnome has to declare aloud what he thinks the color of his own cap is. In the end, those who were correct will be spared; others will be eaten, silently.” The gnomes set thinking and came up with a strategy. How many of them survived? Source: Another one from Gurmeet's blog Solution: Highlight the part between the * symbols for the answer. * There is no way for the tallest gnome to figure out the color of his own hat. However, all others can be saved! The tallest gnome says aloud “black” if there are an even number of black hats in front of him, otherwise he says “white”. The second tallest gnome can now deduce his hat color. He says it aloud. One by one, all ot

Problem: A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible. (Once again, posed by Gurmeet Singh Manku on his blog) Solution: Highlight the part between the * symbols for the answer. * [Thanks to Gaurav Bubna for his solution] Pair up all the computers. In every pair, test one comp with other. We have 3 possibilities - correct correct, correct wrong, wrong wrong. correct correct can only come if both comps are either correct or both wrong. From each such pair just keep one comp. Note that: Since for wrong wrong pairs and correct wrong pairs, both working can never be the case, so, in correct correct pairs, number of working > no of damaged. So, the property number of working > no of damaged is preserved in the next iteration. Note that we reduce number of elem

I got this puzzle from Gurmeet Singh Manku's blog. Awesome CS guy he is. Good one! Give it a try. Original Link The solution proposed by Gurmeet was wrong. I have added a comment and I hope it would be corrected in some time. Puzzle: A goblin forewarns N gnomes as follows: “Tomorrow morning, I shall place one hat on each of you. Each hat shall be labeled with some number drawn from the range [0, N-1]. Duplicates are allowed, so two different hats might have the same label. Any gnome shall be able to see numbers on other hats but not his own! When a bell rings, all gnomes shall simultaneously announce one number each. If any gnome succeeds in announcing the number on his own hat, all gnomes shall be set free.” The gnomes have assembled in the evening to discuss their predicament. Can you help them devise a strategy? Solution: (correct version) Highlight the part between the * symbols for the answer. * Let gnomes be numbered 0 thru N-1. The i-th gnome should announce (i –

Simon Phipps, Chief Open Source Officer at Sun, says that "India is where so much innovation is happening". The award (1 million$ grant) is being announced in India because that's where I expect the greatest open source community growth to come from in the near future." Two questions: Can India lead the world in open source technology? Is it good for the country? In my last post ( link ), I talked about how I feel open source is good for the country (perhaps taking a biased view). Let me be more critical now. From an article in Business Standard, "Open source is a profound idea.... The enduring puzzle of India's software companies is their persistent inability to grow from projects to products. Open source is a powerful answer to this problem. Open source reduces the importance of products and raises the importance of services. In the open source world, each programmer builds on the work of others before him. This brings down the cost of development.&q

In a country, where people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. Who will be more in the country(boys or girls)? Intuitively, I and many of my friends thought it to be boys. Which seems fine as the society favours boys. But calculation shows that they would be equal. How? Suppose there are N couples. Note that each couple would have exactly one boy. So, no. of boys born is equal to N. Counting the no. of girls. N/2 parents would have no girl child. N/4 would have exactly 1 girl child, N/8 would have exactly two girl children, N/16 would have exactly 3 girl children and so on.... So, Expected no. of girls from N couples would be S: S = 1*N/4 + 2*N/8 + 3*N/16 + 4*N/32 + .......... 2S = N/2 + 2*N/4 + 3*N/8 + 4*N/16 + 5*N/32 + ............. So, S = N/2 + N/4 + N/8 + N/16 + ..... S = N So, Expected no. of boys = Expected no. of girls. Equal sex ratio. :)

India is a developing country. Most of us are seeing India's future as a developed country. Will IT play a role in this? I strongly feel "yes". I also feel that India's development would depend on the idea that how many Indians are willing to adapt to the Open Source Business Model. I present two ideas on why open source is a boon for India. The first would be on the basis of the facts suggesting that India cannot realise one laptop per child dream if it is using proprietary software. Open source is cheap, better, affordable, reliable. Open-source software meets the basic criteria of useful and affordable that people and businesses in emerging economies such as India need to adopt them. " To koi ye kyun le, wo na le ". As pointed out in the red hat articles with exact numbers, open source would cut down the cost by a lot and help people realise the dream. To add to it, Indian industries are mostly small or medium scale, which adds to the need of using affor