CSE Blog - quant, math, computer science puzzles

Source: Introduction to Algorithms (by Cormen, Rivest, Leiserson) Problem: Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water and vice versa. How can you find the grouping of the jugs into pairs of red and blue jugs that hold the same amount of water, in the minimum number of comparisons. The only operations allowed is compare between a red and a blue jar (no two reds, no two blues) Update (Dec 30, 2010): Problem statement changed a bit to make it more understandable. Solution: Posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) and Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments! Explained in detail by me in comments!

Source: Asked to me by Dinesh Dharme (CSE IITB Fifth year student) Problem: You have a array of 0's and 1's. e.g. 0001011101001010100101010101100111 Find the maximum contiguous subsequence of the above sequence so the number of 0's and 1's in that subsequence are equal Update (21 Dec 2010): Solution: Posted by Nikhil Garg (Third year student, CSE IIT Delhi) in comments!

There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles Note 1: Can be done in O(N^2) time and O(1) space. Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence) Update (Dec 20, 2010): Complete solution posted jointly by Siddhant Agarwal (EE, Final year student, IITB) and Gaurav Sinha (IITK 1996 CSE Alumnus, IRS Officer). Thanks a lot

Source: Asked to me by Prateek Srivastava (CSE IITB Alumnus & Yahoo! Software Engineer) Problem: I have ten cards, Ace,2,3,4,5,6,7,8,9,10. The value of the Ace is 1. They’re shuffled, then dealt one by one, face up. For the first card, you automatically win $10. For the next 9 cards, if the card face-up is greater than every previous card, you win $10 more. What is the expected winning amount? Clarification: 1) Game does not end when you draw a card that is not a winning card. ie, if I pick a 5 first, then a 6, then a 4, the game is not over. I keep drawing until all of the cards are gone 2) It might be useful to know that the chance of winning $100 is 1/10!, because the cards will have to be drawn in the order: {A, 2, 3, 4 … , 9, 10}. Update (Dec 08, 2010) Solution: Posted by Goutham Valeti (Aero IITB Alumnus, Fair Issac Research Scientist) in comments! A more mathematical solution posted by me in comments!

Source: http://www.cut-the-knot.org/ Problem: Assume a stick is broken at random into three pieces. What is the probability that the pieces can form a triangle? Solve it in following cases: Two break points are selected randomly (and distributed uniformly) on the stick. The stick is first broken into two pieces. The longest (or rather, not the shortest) is then broken into two. The stick is first broken into two pieces. A piece randomly selected with probability 1/2 is then broken into two. The stick is first broken into two pieces. A piece randomly selected with the probability proportional to its length is then broken into two.  Update (Dec 22, 2010) Solution posted by me in comments!

(Disclaimer: This post does not contain any puzzle, but it has sufficient math to keep you interested) I saw Social Network three times in 1 week. Not for entertainment. Not because I had nothing better to do. But because I wanted to understand the math and computer science fundae used in the movie. I would like to discuss one particularly interesting scene from the movie. You may remember Mark inviting his friend Eduardo to give him his chess algorithm at the beginning of the movie (Mark was drinking, blogging and hacking simultaneously and creating Facemash.com). You may also remember the scribbles on the window: and What is this? This is actually the math behind Elo Rating System. Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor. As explained in the movie, Facemash was quite simple. Not unlike hotornot.com, students

Source: Homepage of Tejaswi Navilarekallu, Post Doctoral Fellow, Vrije Universiteit, Amsterdam Problem: A professor decides the following grading scheme in his class. After the final exam is graded, he keeps all the papers upside down on his table in a random order so that no student can recognize his own paper. Each student during his turn can overturn at most n/2 of these papers (where n is the total number of students in the class) and guess whether he received an A or a B on the final (there are only two grades given). Obviously the student doesn't know which paper is his, so it is not guaranteed that he will find his own score by looking at n/2 scores. The papers are then turned back and kept in the original order. The students cannot pass any information to others. All the students pass the course if "everyone" guesses their grade correctly, and they fail otherwise. Come up with a strategy that the students can decide on beforehand, so that the probability

Source: Just made it up! Problem: Easy: Given 2 sorted arrays of size n, give an efficient algorithm to find the kth largest number. Hard: Given m sorted arrays of size n each, give an efficient algorithm to find the kth largest number. Update (04 December 2010) Solution: Posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments! Another solution posted by me in comments!

Source: Credit Suisse Placement Test at IITB Problem: You bet 1$ on a coin toss. A win gives u 1$ gain, a loss gives you a 1$ loss. The guy tossing the coin gets what he wants 80% of the time. You start with X$. Find strategy so that you always win. Update (Dec 04, 2010) Assumption: Note that the dealer is just an employee of the casino. You can take him in your group and make an offer he cannot refuse. Solution: Posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!

You are trying to buy a stock at the best price. You need to buy it in the next 100 minutes. Every minute you will receive a random price (uniform distribution) that is a number between 1 and 100 dollars and decide whether to buy it or not. 1. Assuming you buy the stock in one trade, give a condition for buying the stock. 2. On average how many minutes will pass before that condition holds (expression or approximation is fine)? 3. If you could split up the trade, i.e, buy different amounts at different minutes, what would you do differently? Update(Nov 17, 2010): Solution posted by Sumit Somani (Senior Undergraduate, CSE, IITB) in comments! Same solution posted by me with spreadsheet in comments!

Source : A Quant Company Placement Test 2010 at IITB Problem : You are given an urn with 100 balls (50 black and 50 white). You pick balls from urn one by one without replacements until all the balls are out. A black followed by a white or a white followed by a black is "a colour change". Calculate the expected number of colour changes if the balls are being picked randomly from the urn. Update (Oct 30, 2010): Solution posted by Ankush Agarwal (Junior Undergraduate, CSE, IITB) in comments! Update (Nov 05, 2010): A different solution posted by Piyush Sao (5th year Dual Degree Elec Student, IIT Madras) in comments!

Source: Placement Test of a Quant Company at IITB in 2010 Problem: Consider a random walk around the edges of a square. From any vertex, the probability of moving to any adjacent vertex is 0.5. Suppose the walk stops as soon as after all traversing through all the vertices, you return to your starting vertex. What is the expected path length? Update (Nov 10, 2010): Solution: 1) First solution posted by Naval Chopra (Final year student, CSE, IIT Bombay) in comments! 2) A more elegant solution posted by Ankush Agarwal (Third Year undergraduate student, CSE, IIT Bombay) in comments! He has also posted a mathematica code for verifying his solution :) 3) A similar solution posted by Yash in comments (with a minor typo though) Thanks a lot for the active participation!

Source : Asked to me by Nigel Coldwell (now posted on his blog) Problem : Two creepers, one jasmine and other rose, are both climbing up and round a cylindrical tree trunk. jasmine twists clockwise and rose anticlockwise, both start at the same point on the ground. before they reach the first branch of the tree the jasmine had made 5 complete twists and the rose 3 twists. not counting the bottom and the top, how many times do they cross? Related video : Solution : My solution posted on Nigel's Blog here . Slightly different solution posted by Gaurav Sinha (1996 CSE IITK passout, now at Indian Revenue Service) in comments! A more general argument by Aaditya Ramdas (CMU Grad Student - CSE IITB 2009 Alumnus - Ex Tower Research Analyst) in comments!

Source : Asked to me by Sudeep Kamath (Third year PhD Student, UC at Berkeley, EE IITB Alumnus) Problem : There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men, whoever gets their own hat, takes it and leaves and a random permutation of the remaining hats is picked and so on. What is the expected number of rounds it takes for everyone to leave? Hint : Answer is n Update (21 Oct 2010): Solution posted by Siddhant Agarwal (Senior Undergraduate, EE, IITB), and a more detailed explanation posted by me in comments!

Source : MIT OCW Course 6.041 / 6.431 Probabilistic Systems Analysis and Applied Probability Problem : Your n guests (n>0) are all baseball fans and they wear baseball caps. There is a total of s teams (s>0) in the league. Everyone of your guests is equally likely to be a fan of any one of these teams. Compute the expected number of people who will pick a cap from their own team. Clarification : The number of caps is also n. You have brought the caps so that if the people behaved in an intelligent manner, each person would have got the cap of his team. The guests already had their team caps and after their arrival they had put their caps in a basket. After the party is over, the guests pick cap randomly from basket. Update (22 Oct 2010) Solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!

Source : William Wu Puzzle Page Problem : Draw an equilateral triangle (all sides same length). Divide it into four identical shapes. remove the bottom left hand shape. now divide the resulting shape into four identical shapes. Update (18 Oct 2010): Solution : Identical solutions posted independently by Siddhant Agarwal (Senior Undergraduate, EE, IITB) and Shaunak Chapparia (Senior Undergraduate, CSE, IITB) in comments.

Source : Asked to me by Sudeep Kamath (Third year PhD Student, UC at Berkeley, EE IITB Alumnus) Problem : A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the first. Then, you put both balls back into the box. What is the expected number of times this needs to be done so that all balls in the box have the same colour?

Source : Asked to me by Sai Teja Pratap (Sophomore Undergraduate, CSE, IITB) Problem : There are 51 senators in a senate. The senate needs to be divided into n committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does 'not' necessarily hate senator A.) Find the smallest n such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee.

Source : Asked to me by Vivek Jha (Senior Undergraduate, EE, IITB) Problem : Among 10 given coins, some may be real and some may be fake. All real coins weigh the same. All fake coins weigh the same, but have a different weight than real coins. Can you prove or disprove that all ten coins weigh the same in three weighings on a balance scale? BTW, List of previously asked Coin related puzzles on the blog: Russian Coins Coin Weighing Problem Another Coin Problem Coins Puzzle Consecutive Heads Five Thieves and Bounty Update (Oct 12, 2010) Solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments! Reposted by me removing typo.

Source: Wu William's Puzzle Page Problem: A vendor is handing out free ice cream cones in alphabetical order of flavor, each cone being a different flavor. Kids are lined up at the ice cream truck, and you're first in line! The vendor will hand you ice cream cones one at a time, and you must decide whether to keep the cone or pass it on to the next kid in line. The first cone is guaranteed to be chocolate. You like all flavors equally, so you want to randomly select a cone with each flavor having an equal chance of being chosen. Unfortunately, you don't know the total number of flavors, but being the little hipster that you are, you are carrying a pocket calculator which can generate random numbers from 1 to X, where X is a value you punch in. How can you decide which flavor to keep? Solution: Update (Oct 10, 2010): Solution posted by Hanumanth Rao (explained in more detail by me) in comments!

Disclaimer: Difficult Problem Source: Amol Sahasrabudhe (Associate, Morgan Stanley) - Got his permission to put it on blog \m/ \m/ Problem: Lets consider a two player game in which a number is given. The first person gets a chance to choose a number of the form (prime-1) and subtract it from the given number. Then the second person gets a chance to do the same and so on. The person who makes the number zero wins. So, if the chosen number is of the form (prime-1), the first person would win in the first chance. There are infinite numbers for which first person has a winning strategy. Prove that second person also has a winning strategy for infinite numbers. :) Bonus: Given a chance to choose whether you want to be first person or second person, what would you choose? Update (25-09-10) Solution: Posted by Siddhant Agarwal (4th year, EE, IITB) in comments!

Source: Puzzle Toad, CMU Problem: Its raining outside and Alfonso and Bernadette are bored. Alfonso suggests the following games: (a) Two players alternatively erase some 9 numbers from the sequence 1,2,...,101 until only two remain. The player that starts wins x−54 dollars from the player that plays second. Here x is the difference between the remaining two numbers. Would you rather be the first or the second player? (b) Two players alternatively erase one number from the sequence 1,2,...,27 until only two numbers remain. The first player wins if the sum of these numbers is divisible by 5; otherwise the second player wins. Who has a winning strategy? Update (Oct 10, 2010): Solution posted by Siddhant Agarwal (Senior Undegraduate, EE, IITB) in comments!! Also at Puzzle Toad page ( http://www.cs.cmu.edu/puzzle/solution31.pdf )

Source: Stanford Math Circle Sunday May 30, 2010 Problem: A circle is divided into 6 sectors. The numbers 1, 0, 1, 0, 0, 0 are written into the sectors in the counter clock-wise direction. You may increase any two neighboring numbers by 1. Is it possible to make all of the numbers equal? Disclaimer: Think simple. Very simple problem. Solved it in less than 30 seconds. :) Solution: Posted by Aman in comments!! He claims he took less than 10 seconds \m/ \m/. This is one thing where it feels good to win, but feels awesome to be defeated \m/ \m/

Source: Asked to me by Amol Sahasrabudhe (Morgan Stanley Quant Associate) Problem: An infinite checkerboard is divided by a horizontal line that extends indefinitely. Above the line are empty cells and below the line are an arbitrary number of game pieces, or "soldiers". A move consists of one soldier jumping over an adjacent soldier into an empty cell, vertically or horizontally (but not diagonally), and removing the soldier which was jumped over. The goal of the puzzle is to place a soldier as far above the horizontal line as possible. Prove that there is no finite series of moves that will allow a soldier to advance more than four rows above the horizontal line. I could get the correct direction in 5 min. Spent enough time on the problem but could not solve it. :( Give it a go! \m/ Update: Sep 07, 2010 Solution: Posted by Siddhant Agarwal (Senior Undergraduate, Elec IITB) in comments!!

Source: CMU Puzzle Toad Problem: The wizards at Wall Street are up to it again. The Silverbags investment bank has invented the following machine. The machine consists of 6 boxes numbered 1 to 6. When you first get the machine, it contains 6 tokens, one in each box. You have two buttons A, B on the machine and you can press them as many times as you like and in any order. Button A Choose a number i from 1 to 5 and then take one token from box i and magically two tokens will be added to box i + 1 . Button B Choose a number i from 1 to 4 and then take one token from box i and then the contents of boxes i + 1 and i + 2 will be interchanged. The machine sells for one trillion dollars. The contract says that you can take the machine back to the bank at any time and then the bank will give you one dollar for each token in the machine. Is the machine worth buying? Update (Nov 10, 2010): This problem is an IMO 2010 Problem. Solution available at artofproblemsolving lin

Problem: A man has two children. He says one of them is a son. What is the probability that the other one is also a son? (Hint: Answer is not 0.5 :P) I have read this problem many times in many different forms. But still looks fresh :P Solution: Read the wikipedia article of a famous and related problem ( Link )

Source: Saurabh Joshi's Blog Problem: (copy-pasting from the source) Suppose we have 13 cards arranged in descending order: K Q J 10 9 8 7 6 5 4 3 2 1 At any move, you can take a substring of cards and move it elsewhere. For example, 10 9 8 could be move to the right by 2 steps to get K Q J 7 6 10 9 8 5 4 3 2 1. The goal is to sort the string in increasing order minimize the number of such moves. It must be absolutely obvious that you can do it with 12 moves but the very fact that I’m asking you this question means that you can do better. How many moves do you need? Now the obvious extension to this problem is to generalize this technique for any n. Awesome Problem!! Update (Sep 07, 2010): Solution: At Saurabh Joshi's blog ( Link )

Source: Tanya Khovanova’s Math Blog Problem: The Sultan decided to test the wisdom of his wizards. He collected them together and gave them a task. Tomorrow at noon he will put hats of different colors on each of the wizard’s heads. The wizards have a list of the available colors. There are enough hats of each color for every wizard. The wizards also have a list of rooms. There are enough rooms to assign a different room for every color. Tomorrow as the Sultan puts hats on the wizards, they will be able to see the colors of the hats of the other wizards, but not the color of their own. Without communicating with each other, each wizard has to choose a room. The challenge comes when two wizards have the same hat color, for they must choose the same room. On the other hand, if they have different hat colors, they must choose different rooms. Wizards have one day to decide on their strategy. If they do not all complete their task, then all of their heads will be chopped off. What str

Source: Australian Mathematical Society Gazette Puzzle Corner Problem: There are coins of various sizes on a table, with some touching others. As often as you wish, you may choose a coin, then turn it over, along with every other coin that it touches. If all coins start out showing heads, is it always possible to change them to all tails using these moves? Update (Nov 15, 2010): Solution: Solution from the gazette author posted by me in comments! Interesting linear algebra solution posted by Siddhant Agarwal (EE, Senior Undergraduate, IITB) in comments!

Source: Australian Mathematical Society Gazette Puzzle Corner Problem: An optimist and a pessimist are examining a sequence of numbers. The optimist remarks, ‘Oh jolly! The sum of any eight consecutive terms is positive!’ But the pessimist interjects, ‘Not so fast, the sum of any five consecutive terms is negative.’ Can they both be right? How long can this sequence of numbers be? Incentive: Treat at H8 Canteen/Sodexho Cafeteria for the first person to solve it :P Update (27/07/10): Solution: Posted in comments by Varun Jog (Berkeley Grad Student, EE IITB Alumnus) and Siddhant Agarwal (EE Senior Undergraduate, IITB)

Source: Plus Magazine Issue 55 Problem: Let's witness a game. The game involves flipping a coin, which you assume has equal probability of coming up heads or tails. The game is played by two players, A and B, who each select a sequence of three flips. For example, assume that Player A selected "heads-heads-heads" (HHH) and Player B has selected "tails-heads-heads" (THH). Then the coin is flipped repeatedly, resulting in a sequence like the following: HTHTHHHHTHHHTTTTHTHH... The player whose sequence showed up first (HHH for Player A or THH for Player B) is declared the winner. A chooses first and you have to help B. Show that given what A has chosen, B can always choose a sequence such that B is in a better position than A. For example: If A chooses HHH, B chooses THH to make sure that now it has 7/8 probability to win. Update (27/07/10): Solution: Posted in comments by me!

Source: CMU Spring 2010 Course on Great Theoretical Ideas in Computer Science Problem: 10% of the surface of a sphere is colored green, and the rest is colored blue. Show that no matter how the colors are arranged, it is possible to inscribe a cube in the sphere so that all of its vertices are blue. Hint: Use probabilistic analysis. Consider a random cube and calculate the expected number of vertices that are blue. (Update 23/06/10): Solution: Posted by connect2ppl - Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!

Source: 2010 Euler math Olympiad in Russia to Eighth graders. The author of the problem is Alexander Shapovalov Problem: Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. How would we find at least one genuine coin using two weighings on a balance scale? By the way, ten eighth grade students in Russia solved this problem during the competition. :P Best of Luck! I am sure solving this problem will make you happy :) Update(26-06-10) Solution: Posted by Nikhil in comments!

Source: Gazette of the Australian Mathematical Society Problem: A balance scale sits on the teacher’s table, currently tipped to the right. There is a set of weights on the scales, and on each weight is the name of at least one student. The teacher chooses a set of students to enter the classroom. One by one, each chosen student will move each weight carrying his or her name to the opposite side. Prove that the teacher can always choose a set of students to tip the scales to the left. Update (June 17, 2010) Solution: Posted by me in comments!

My first original question :P Source of inspiration: Discussion with one of the seniors (CSE, IITB Alumnus 05-09 & Quant Analyst) during Pre-Placement Talk of a firm during Campus Placements - " I have seen your blog. Its very good. But its not original. Try and make your own questions. " Problem: Ever played housie/tambola? I played housie once every month for 6 good years of my life. Won some prizes. Each coupon (a ticket with 15 numbers) cost Rs. 10 then. Full Housie was nearly 150 Rs, exact number depending upon the number of tickets sold. I played one such game once again after a lapse of 6 years I think. At the end of the game I saw that 76 numbers out of 90 had been cut on the board. I couldn't help but to think what is the expected number of numbers I expect to be crossed if N (say 100) tickets have been sold. Also, I wanted to find out what is a good number of people who should be there to play housie. Of course if there are zillions of people, the gam

Source: http://puzzles.nigelcoldwell.co.uk/twentysix.htm Problem: A man has built three houses. Nearby there are gas water and electric plants. The man wishes to connect all three houses to each of the gas, water and electricity supplies. Unfortunately the pipes and cables must not cross each other. How would you connect connect each of the 3 houses to each of the gas, water and electricityic supplies? Disclaimer: Trick Question! Solution: http://puzzles.nigelcoldwell.co.uk/twentysix.htm

Source: CMU Spring 2010 Course on Great Theoretical Ideas in Computer Science Lecture01. Course pointed to me by Aaditya Ramdas (To be CMU Grad Student & CSE-IITB Alumnus) Problem: Fit disks of the following diameters into a circular cavity of size 12.000: 2.150 2.250 2.308 2.348 2.586 2.684 2.684 2.964 2.986 3.194 3.320 3.414 3.670 3.736 Write a program or give a general algorithm to solve a general case. Disclaimer: Did not spend a lot of time on the problem but I have not been able to solve it. Clearly sum of the squares of the smaller radii is less than the square of the larger radii suggesting that it might be possible to fit disks. I am not able to make any more comments!

Source:  Very interesting puzzle from http://forums.xkcd.com/ Problem: There are 7 people standing in a circle, and each has either a red or a blue hat. The colors of the hats are chosen uniformly at random (although the problem is much the same if they're chosen adversarially). The people can't see their own hats, but can see each others'. Everyone is given a strip of paper and a pen, and simultaneously writes "red", "blue", or "abstain". Nobody can see what the other people are writing, or convey information in any other way. They win if somebody guesses his own hat color, and nobody guesses wrong. Find a strategy (which they agree on ahead of time) that maximizes probability of winning. Obviously, it is impossible to make a strategy that wins every time, because somebody must guess and that person has no information. To make it easier, try it first with three people. Disclaimer: I posted this problem (in different words) 4 months

Source: http://blog.tanyakhovanova.com/ Problem: You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice? Disclaimer: It is a difficult problem Hint: (Highlight from * to * to see the hint) * Some people post wrong solutions and believe they have solved it. For example, they would start by putting the coins labeled 1 and 2 on the left cup of the scale and 3 on the right cup. If these coins balanced, the person assumes that the coins on the left weighed 1 and 2 grams and that the coin on the right weighed 3 grams. But they’d get the same result if they had 1 and 4 on the left, for example, and 5 on the right. I propose the following sequence a(n) . Suppose we have a set of n coins of different weights weighing exactly an integer number of grams

Source: Asked to me by Ankush Agarwal (Sophomore, CSE, IITB) Problem: There are two kinds of coins, genuine and counterfeit.  A genuine coin weighs X grams and a counterfeit coin weighs X+delta grams, where X is a positive integer and delta is a non-zero real number strictly between -5 and +5.  You are presented with 13 piles of 4 coins each.  All of the coins are genuine, except for one pile, in which all 4 coins are counterfeit.  You are given a precise scale (say, a digital scale capable of displaying any real number).  You are to determine three things: X, delta, and which pile contains the counterfeit coins.  But you're only allowed to use the scale twice! Prize: Treat at H8 canteen to the first person who solves it!!

The paradox imagines that Sleeping Beauty volunteers to undergo the following experiment. On Sunday she is given a drug that sends her to sleep. A fair coin is then tossed just once in the course of the experiment to determine which experimental procedure is undertaken. If the coin comes up heads, Beauty is awakened and interviewed on Monday, and then the experiment ends. If the coin comes up tails, she is awakened and interviewed on Monday, given a second dose of the sleeping drug, and awakened and interviewed again on Tuesday. The experiment then ends on Tuesday, without flipping the coin again. The sleeping drug induces a mild amnesia, so that she cannot remember any previous awakenings during the course of the experiment (if any). During the experiment, she has no access to anything that would give a clue as to the day of the week. However, she knows all the details of the experiment. Each interview consists of one question, "What is your credence now for the pr

Source: http://www.math.utah.edu/~cherk/puzzles.html Problem: Salt Lake City looks like a rectangle crossed with M streets going from North to South and with N streets going from East to West. The city is frequently visited by tourists who suppose to run around in the buses. The Utah governor wants to vigil all moves of the buses. He plans to put policemen at some intersections to watch all the buses moving on the streets visible from that intersections. What is the minimum number of policemen needed for the bus watch? Update (26/03/10) Solution: Posted by Ashu and Aman in comments!!

Unexpectedly Great Expectations Post here shows an awesome paradox. The paradox is called St. Petersburg paradox. I have spent hours explaining this paradox to many smart friends of mine. This is probably the best paradox I have ever seen. Just reposting the game from that article: WARNING: THESE ARE THEORETICAL GAMES. Try not to bias yourself by how much YOU value 1000$ compared to how a millionaire values 1000$ (the utility function of money is a constant for all people). Also, we assume God has infinite amount of money with him, and does not lie when he says he will pay you, so please don’t give arguments like “put the money on the table and I will play” (replace 1$ by 0.001$ or any such figure if you want to satisfy yourself practically). God offer you the option of playing a game,  exactly once , against me. This is how the game works. God will toss a fair coin until a T turns up. The sequence of coins H n T will earn you 2 n  dollars. More explicitly, a T on the first to

100th Puzzle \m/ \m/ Source: " Fifty Challenging Problems in Probability" by Mosteller F. Problem:   A railroad numbers its locomotives in order 1,2,3.. N. One day you see a locomotive and see that its number is 100. Guess how many locomotives the company has. You have looked at 5 locomotives and the largest number you have seen is 100. Again guess how many locomotives does the company have? Update(26/03/10): This is not an exact question. I need to see various approaches to solve this problem. I see this as a real problem: I saw some locomotives and then someone asks me - Guess the number of locomotives. Since I have not provided enough data, all "creative" answers are correct.

Source:  http://www.ocf.berkeley.edu/~wwu/riddles Problem: An enemy submarine is somewhere on the number line (consider only integers for this problem). It is moving at some rate (again, integral units per minute). You know neither its position nor its velocity. You can launch a torpedo each minute at any integer on the number line. If the the submarine is there, you hit it and it sinks. You have all the time and torpedoes you want. You must sink this enemy sub - devise a strategy that is guaranteed to eventually hit the enemy sub. Related Link: A similar problem we solved some time back was " Finding a Hermit " Solution: Posted by Aaditya Ramdas (CSE, IITB Alumnus working at Tower Research) in comments!!

You have N cars that are all traveling the same direction on an infinitely long one-lane highway. Unfortunately, they are all going different speeds, and cannot pass each other. Eventually the cars will clump up in one or more traffic jams. In terms of N, what is the expected number of clumps of cars? Update (05/03/2010): Solution: Posted by me in comments!! Thanx to Asad (EE, IITB Alumnus) and Siddhant Agarwal (EE, IITB 3rd year student) for their participation in discussion in comments!! Update (29/01/2011) Very simple and clear solution posted by wonderwice in comments! Thanks a ton!

You have Some Terminal Condition, which necessitates taking two pills a day: one Pill A and one Pill B. If you neglect to take either pill, you die; if you take more than one A or more than one B, you die. If you don't take them at exactly the same time, you die. This morning you are going through your usual routine. You pick up your bottle of A Pills and gently tap one into your palm. Then you pick up your bottle of B Pills and tap it, but two pills accidentally fall into your hand. You now hold three pills (one pill of A and two pills of B), you don't know which are which, and they are completely indistinguishable from each other. The A Pills are the same color as the B Pills, they are the same shape, same size - they are identical in every respect.  Your doctor is charging you $10,000,000 a pill! So you dare not throw any away. Thus, the puzzle: what can you do to ensure that you take only one A Pill and only one B Pill today, without wasting any pills (either today

Source: Appeared in 1977 High School Programming Contest. Taken from  http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml Problem: Write a fast program that prints perfect powers (integers of the form m n , with m,n>1) in increasing numerical order. So the first few outputs should be 4, 8, 9, 16, 25, 27, 32, ... Find an algorithm that prints all perfect powers less than equal to N. Update (05/03/2010): Solution: Nikhil Garg (CSE, IITD Sophomore) posted a solution which takes O(N) space and O(log N*sqrt N) time. Printing takes time O(N) though. I posted a solution which takes O((sqrt N)*(log N)) space and O((sqrt N)*(log N)*(log N)) time. Rajendran Thirupugalsamy (Research Assistant, Stony Brook University) posted a solution which takes O(log(N)) space and O(sqrt N * log N * log(log(N))) time. {Analysis done by Ramdas} Aaditya Ramdas (CSE IITB Alumnus and working at Tower Research Capital) posted a solution which takes O(sqrt N) space and O((sqrt N)*(log N)*(log N)) tim

Source: Placement test of one of the Algorithmic Trading Firms coming to the campus. Also in UC Berkeley, Spring 2001 Final Exam for CS170 (Efficient Algorithms and Intractable Problems) Problem: Pratik is org anizing a mix tape for his sweetheart, Pratiksha. The tape will have her top N songs of all time. Pratik was going to determine the order of these songs on his own, but then Pratiksha found out about his little project. Being an obnoxiously demanding woman, she has now given Pratik a price function f which takes a pair of songs [si,sj] as input, and returns a real number that quantifies exactly how good song sj sounds after song si, in her opinion. (Note that f([si,sj]) may not be equal to f([sj,si]).) Write an O(n^2*2^n) algorithm for Pratik that will determine a song order which maximizes the total transition goodness of the mix tape. (If the maximum is not achieved, Pratik will be dumped. :() Solution: Posted by Nikhil Garg (Sophomore, CSE, IITD), Rajendran Thirupugal

Yet another coin problem. Read this today in "Heard from the Street". Found it interesting. Problem: You are given a set of scales and 90 coins. The scales are of the old balance variety, that is a small dish hangs from each end of the rod that is balanced in the middle. You must pay 100$ every time you use the scales. The 90 coins appear to be identical. In fact, 89 of them are identical and one is of a different weight. Your task is to identify the unusual coin and to discard it while minimizing the maximum possible cost of weighing. What is your algorithm to complete this task? Note that the unusual coin may be heavier than the others or it may be lighter. You are asked to both identify it and determine whether it is heavy or light. Previously asked coin puzzles: Another Coin Problem Coins Puzzle Consecutive Heads Five Thieves and Bounty Update (18/02/10): Solution  posted by me in comments!! A non-optimal but simpler solution posted by Bhanu (M.Tech Student

Source: Problem 1.27 from the book "Heard from the Street" Problem: A very large number, N, of people arrive at a convention. There are exactly N single rooms in the hotel where the convention takes place. Each guest is given a numbered key for a specific room. Before they even go upstairs, they are all invited to a large party in the banquet hall. To gain admittance to the hall, they have to give up their keys to a doorman. At the end of the evening, the guests are not sober enough to recall their room numbers, so the doorman simply hands out the keys randomly. Each guest ends up spending the night in a random room. What is the probability that at least one guest ends up in a room he or she was originally assigned? What is the expected number of guests who end up in a room in which they were originally assigned? Update(18/02/10): Solution: Posted by Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments!! Explanation and a different solution

Problem: You are given three piles with 5, 49 and 51 pebbles respectively. Two operations are allowed: (a) merge two piles together or (b) divide a pile with an even number of pebbles into two equal piles. Is there a sequence of operations that would result in 105 piles with one pebble each? Update(12/02/10): Solution: Posted by Shantanu Gangal (CSE IITB Alumnus and BCG Consultant) in comments!!

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P Most of my friends already read an article that I wrote more than an year back - " Speak Up " Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it! Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis. @Consultants, correct me if I am wrong in my estimates. :P Why is there a need to be selective? From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once

Source: Nikhil Garg (Sophomore, IITD) mailed them to me. Problem 1: A checker starts at point (1,1). You can move checker using following moves : 1) if it is at (x,y) take it to (2x ,y ) or (x,2y) 2) if it is at (x,y) & x>y take it to (x-y,y) 3) if it is at (x,y) & x<y take it to (x,y-x) Characterise all lattice points which can be reached. Problem 2: You have a checker at (0,0) , (0,1) , (1,0), (2,0), (0,2), (1,1) each. You can make a move as follows: if(x,y) is filled  & (x+1,y) and (x,y+1) both are empty, remove checker from (x,y) & put one at each of (x+1,y) and (x,y+1) Prove that under this move , you can not remove checker from all the six initial points. Solution: Update (02/03/10): Solution posted by Nikhil Garg in comments!

Source: Techfest 2010 Puzzle Hut Problem: It is desired to invert a set of n upright cups by a series of moves in each of which n-1 cups are turned over. Show that this can always be done if n is even  and never can be done if n is odd. Update(08/02/10): Solution: Posted by Ankush Agarwal (2nd yr, CSE, IITB), Dinesh Dharme (4th yr, CSE, IITB), Nikhil (2nd yr, IITD) and Siddhant Agarwal (3rd year, EE, IITB) in comments!! For just solution, read Ankush's and Sid's comment!! Proof of bound posted by me in comments!!

Problem: A king wants his daughter to marry the smartest of 3 extremely intelligent young princes, and so the king's wise men devised an intelligence test. The princes are gathered into a room and seated, facing one another, and are shown 2 black hats and 3 white hats. They are blindfolded, and 1 hat is placed on each of their heads, with the remaining hats hidden in a different room. The king tells them that the first prince to deduce the color of his hat without removing it or looking at it will marry his daughter. A wrong guess will mean death. The blindfolds are then removed. You are one of the princes. You see 2 white hats on the other prince's heads. After some time you realize that the other prince's are unable to deduce the color of their hat, or are unwilling to guess. What color is your hat? Note: You know that your competitors are very intelligent and want nothing more than to marry the princess. You also know that the king is a man of his word, and he h

This is a variation of the problem discussed some time back:  Don't roll More . Just published the solution to the earlier problem . Thought it would be interesting to solve this problem taken once again from the book "Heard on The Street". Problem:  You have 52 playing cards (26 black and 26 red). You draw cards one by one. A red card pays you a dollar. A black card costs you a dollar. You can stop any point you want. Cards are not returned to the deck after being drawn. What is the optimal stopping rule in terms of maximizing expected payoff? Also, what is the expected payoff following the optimal rule? Hint: Try the problem with 4 cards (2 red, 2 black) :) Update(29/01/10): Question was incomplete. Added more information. Solution: (Update (05/02/10)) Idea posted by Aman in comments!! Solution posted by me in comments!! The problem/solution is very difficult and not so beautiful. Its not very mathematical though. Do this only if you have time and you are humbl

Problem: Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates I have read and solved many problems like these. Can people post some similar interesting problems using gates. I was asked one such question in my Deutsche Bank Interview which I was not able to answer. Update(09/02/10): Solution: Solution posted by Sid in comments!! Update(23/06/14): Solution: Interesting link shared by divby0 in comments!

Source: Puzzle Toad, CMU Problem: A hungry lion runs inside a circus arena which is a circle of radius 10 meters. Running in broken lines (i.e. along a piecewise linear trajectory), the lion covers 30 kilometers. Prove that the sum of all turning angles is at least 2998 radians. Update(05/02/10): Solution: Solution posted by me in comments!!

I solved IBM Ponder This October 2009 Challenge and IBM Ponder This November 2009 Challenge and now solved this very interesting puzzle at IBM Ponder This January 2010 Challenge I am happy!! My name on IBM's research site three times in 4 months. :) Problem: Present a computation whose result is 5, being a composition of commonly used mathematical functions and field operators (anything from simple addition to hyperbolic arc-tangent functions will do), but using only two constants, both of them 2. It is too easy to do it using round, floor, or ceiling functions, so we do not allow them. Source: IBM Ponder This January 2010 Challenge Solution: IBM guys would post it on their site by February 2010 :) Three different solutions given by Piyush (Fourth year, IITM), Aniesh Chawla (Fourth year, IITD) and me (Fourth year, IITB) :). All posted in comments!! Thanx to Anirudh Shekhawat urf Maoo (CSE, IITB & Google) for help in the last step :)

Some basic math olympiad problems: Divisible by 289? For how many integers x, x^2 - 3x - 19 is divisible by 289? Perfect square? For how many positive integral values of n, the expression n(4n + 1) is a perfect square? Update (23/01/10)(05/02/10): Solution: Posted by Aaditya Ramdas (CSE IITB Alumnus & Tower Research), Piyush Sao (Senior Undergrad, EE, IITM) and Nikhil Garg (Sophomore, IITD) in comments!!  Thanx.

Source: Insight (IITB Newsletter) Questech Problem : In a land far away, there is a village threatened by an hundred-headed beast. This beast can only be killed by cutting of all the hundred heads. Legend says that any brave warrior can cut off exactly 10, 20, 30 or 40 heads at one time. However with each of these, 40, 2, 60 and 4 new heads appear respectively. The village has lost several brave warriors against this beast. Can you save the village from this beast ? Update(21/01/10): Solution: Solution provided by Bhanu Prakash (M.Tech Student, CSE, IITB) in comments!!

Source: +Plus Magazine Problem: You're in a glitzy casino in Las Vegas. Having tried your hand at everything from Roulette to Black Jack, you've managed to lose most of your money and have only one dollar left. What's worse, with all the champagne and everything, you've misbehaved and the management has made it very clear that you're not allowed any more games. But you need two dollars to get the bus back to the hotel. Two shady-looking characters at the bar offer you a game: they have a pile of 15 stones. Each of you in turn is to take your choice of 1, 2, 3, 4 or 5 stones from the pile. The person who takes the last stone gets one dollar from the person who drew previously, and the third person neither wins nor loses. You're to draw first. You're sure that both of the other players will play to their best personal advantage and won't make any mistakes. Should you agree to play the game? Update(23/01/10): Solution: Posted by Gir

Source: Gazette of the Australian Mathematical Society Problem: Two people, Give and Take, divide a pile of one hundred coins between themselves as follows. Give chooses a handful of coins from the pile and Take decides who will get them. This is repeated until all coins have been taken or until one of them has taken nine handfuls. In the latter case, the other person is allowed to take all of the remaining coins in the pile. What is the largest number of coins that Give can be sure of getting? Update (05/02/10): Solution: Solution by Aaditya Ramdas  (CSE, IITB alumnus & Tower Research) in comments!! Further explained by me in comments!!

Source: http://www.qbyte.org/puzzles/puzzle14.html Problem: (An interesting counting exercise) In how many ways, counting ties, can eight horses cross the finishing line? (For example, two horses, A and B, can finish in three ways: A wins, B wins, A and B tie.) Update(21/01/10): (simple combinatorics problem) Solution: Solution posted by Nikhil Garg (Sophomore, IIT Delhi) in comments!! Update(06/02/10): Interesting solution posted by Aman too.

Source : Puzzle Toad, CMU Problem: Each hat is black or white. The people are standing in a circle. Now our n hat wearing friends are standing in a circle and so everyone can see everybody else's hat. The hats have been assigned randomly and each allocation of hat colors is equally likely. At a certain moment in time each person must simultaneously shout "my hat is black'' or "my hat is white'' or "I haven't a clue''. The team wins a big prize if at least one person gets the color of his hat right and no one gets it wrong (saying "I haven't a clue'' is not getting it wrong). Of course, if anyone gets it wrong, the whole team is eliminated and this is painful. The prize is big enough to risk the pain and so devise a strategy which gives a good chance of success. Update (29/01/10): Solution:  Posted in comments by me. Update (06/02/10): Previous solution deleted. Solution reposted with more explanation. :)

Suppose N mothers live in a city. Half of them have one child and half of them have two children. That means that an average mother has 1.5 children. Suppose we pick the sexual orientation of every child by rolling dice. Let’s assume that a child has a 10% probability of being homosexual. The number of mothers with one child who is homosexual is 0.05N . The number of mothers with two children both of them homosexual is 0.005N . The number of mothers with two children with only the first child homosexual is 0.045N , which is the same as the number of mothers of two children with only the second child homosexual. The total number of mothers who have two children with at least one of them homosexual is 0.095N . Let’s calculate the average fertility of a mother with at least one homosexual child. It is (1*0.05N + 2*0.095N)/(0.05N + 0.095N) = 0.24/0.145 = 1.66 . The resulting number — 1.66 — is much bigger than 1.5, the average number of children for a mother. This means there is a

Source: Variant of a sub-problem in my seminar presentation on " Security Attacks on RSA " . Very interesting (and difficult) algorithms problem. Problem: An array of length n+1 is populated with integers in the range [1, n]. Find a duplicate integer (just one, not all) in linear time with O(1) space. The array is read-only and may not be modified. Solution: Update(20/01/10): Solution (from Gurmeet Singh Manku's blog) posted in comments!!

Source: Tanya Khovanova’s Math Blog Problem: The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake? Reference: This is a followup to the following problem http://pratikpoddarcse.blogspot.com/2009/08/cap-puzzle.html Update(24/01/10): Solution : Posted by me in comments (taken from a recent blog entry by Saurabh Joshi, IIT Kanpur)

Among Top 10 in India in Indian Sudoku Championship Elimination Round :) Indian Sudoku Championship 2010 Sudoku, dubbed as the hottest puzzle sensation since the Rubiks Cube gained worldwide popularity in early 2005. The first World Sudoku championship (WSC) was held in March 2006 in Lucca, Italy. The 5th WSC will be held in April 2010 in Philadelphia, USA. Logic Masters India in association with TechFest at IIT Bombay, invites you to test your logical skills in the Indian Sudoku Championship and get an opportunity to represent India at the WSC. All resident Indian nationals, irrespective of age, can participate in Indian Sudoku Championship. The sudoku-solving skills of contestants will be tested through the regular Classic sudokus as well as different sudoku variations which appear in the WSCs. Top rankers at the Indian Sudoku Championship will be eligible to represent India at the 5th World Sudoku Championship to be held in Philadelphia in April 2010. Rules and Regulations

Story: I remember that I used to believe that shuffling cards more makes the pack "more" randomized. It turns out that if I was perfect, I would have given serious advantage to my opponents. Lets see how. :) Source: William Wu's Puzzle Page Puzzle : A perfect in-shuffle of a deck of 52 cards is defined as follows. The deck cut in half followed by interleaving of the two piles. So if the cards were labeled 0, 1, 2, …, 51, the new sequence is 0, 26, 1, 27, 2, 28, … With repeated in-shuffles, shall we ever get back the original order? In how many iterations? The shuffling technique described in the puzzle is known as the Faro Shuffle . Update(12/01/10): On a related note, I was searching for optimal shuffling algorithms and found this an interesting read. Update (14/01/10): Solution posted by me in comments!!

Source: Wikipedia (Classical "Exchange Paradox" problem) Problem: The setup: The player is given two indistinguishable envelopes, each of which contains a positive sum of money. One envelope contains twice as much as the other. The player may select one envelope and keep whatever amount it contains, but upon selection, is offered the possibility to take the other envelope instead. The switching argument: Denote by A the amount in the selected envelope. The probability that A is the smaller amount is 1/2, and that it's the larger also 1/2 The other envelope may contain either 2 A or A /2 If A is the smaller amount, the other envelope contains 2 A If A is the larger amount, the other envelope contains A /2 Thus, the other envelope contains 2 A with probability 1/2 and A /2 with probability 1/2 So the expected value of the money in the other envelope is: This is greater than A , so swapping is favored After the switch, reason in exactly the same ma

Source: Taken from the book "Heard on The Street" (Problem 4.2 in Revised 9th Edition) by Timothy Falcon Crack. Saw a very similar problem in the placement test of a hedge fund coming to campus. (Cannot disclose the name. Policy signed :P) Problem: I will roll a single die not more than three times. You can stop me immediately after the first roll, or immediately after the second, or you can wait for the third. I will pay you the same number of dollars as there are dots on the single upturned face on my last roll (roll number three unless you stop me sooner). What is your playing strategy? Update(06/02/10): Solution: Posted by Vivek Kumar Jha (Elec IITB 3rd yr B.Tech) in comments!! Generalized solution by Aman !!

Source: Jaadu a.k.a Anshum Agarwal (Fourth Year, CSE, IITB and to be Tower Research Analyst) gave me this question. Said question from Tutorial of Prof. Sundar's course "Approximation Algorithms" Problem: There are n letters and n envelopes. Your servant puts the letters randomly in the envelopes so that each letter is in one envelope and all envelopes have exactly one letter. (Effectively a random permutation of n numbers chosen uniformly). Calculate the expected number of envelopes with correct letter inside them. Disclaimer: Not easy :P Update (10/01/10): Solution: Posted by Giridhar (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!! Nice solution. Update (21/01/10): With the help of Asad Ali (EE, IITB Alumnus), a different solution  posted by me in comments!!

Source: Peter Winkler book, Placement quant company interview, Wikipedia Problem: 1) How many times do you need to flip a coin before you expect to see both heads and tails? 2) How many times do you need to roll a die before you expect to see all the numbers 1-6? 3) A company — say Coca-Cola, for concreteness — is holding a contest where everyone who collects one each of n different "coupons" wins some prize. You get a coupon with each purchase of a Coke, and each coupon is equally likely. What’s the expected number of Cokes you have to buy in order to collect all the coupons? Update (10/01/10): Solution posted by Giridhar (IITK alumnus, Yahoo! Engineer) in comments!!

Source: Puzzle Toad, CMU Problem: Gridville is a perfect city. It is laid out as an nXn grid and each of n^2 families inhabits its own square. A developer o ers to buy k < n plots at a price of one billion Wazooli's per plot. If a plot is bought, the family will move out and the plot will be used for growing Garbash, the most valuable commodity in GridWorld. If at any time, a family plot has two Garbash plots adjacent to it, the smell of the Garbash will cause them to leave and the developer will buy up the plot for a mere million Wazooli's and start growing Garbash. After, 10 years, the developer agrees to clean up and replace the plots by family homes, unless everybody has left. The developer will not disclose where he plans to put his k initial plots. Should the inhabitants of Gridville take the money, given that they want to gt back to normal in 10 years? Different version of the problem: Source: Peter Winkler book "Mathematical Puzzles: A Connoisseur

Source: " The Second Book of Mathematical Puzzles and Diversions " by Martin Gardner Problem: A chessboard has squares that are two inches on the side. What is the radius of the largest circle that can be drawn on the board in such a way that the circle's circumference is entirely on black squares?

Source: Puzzle collection of K. Rustan M. Leino, Microsoft Research Problem: You're on a government ship, looking for a pirate ship.  You know that the pirate ship travels at a constant speed, and you know what that speed is.  Your ship can travel twice as fast as the pirate ship.  Moreover, you know that the pirate ship travels along a straight line, but you don't know what that line is.  It's very foggy, so foggy that you see nothing.  But then!  All of a sudden, and for just an instant, the fog clears enough to let you determine the exact position of the pirate ship.  Then, the fog closes in again and you remain (forever) in the thick fog.  Although you were able to determine the position of the pirate ship during that fog-free moment, you were not able to determine its direction.  How will you navigate your government ship so that you will capture the pirate ship?:) Update(10/01/10): Solution: Thanx to Suyash Roongta (First Year, IIT Delhi) for posting s

Suggested to me by Giridhar Addepalli (IITK CSE Alumnus, Yahoo! Sr. Software Engineer). Nice puzzle. Original Source is "Thinking Mathematically" ( Amazon Link ). Giridhar posts nice mathematical problems on his blog . Interesting puzzle. It is not an easy problem. But the experience of getting stuck trying to solve the problem is in itself rewarding. Hint: Try and specialize. Organize the results of specialising. Make a conjecture, however wild. Check and prove your conjecture. Followup : Given by Giridhar on his blog. Using this, find an O(1) space algorithm to "rotation of array" problem where you are asked to rotate the array by a given amount k. For example, rotating Array containing 3, 5, 9, 14, 1, 2, 11 by 3 positions will yield 14, 1, 2, 11, 3, 5, 9. O(k) space algorithm is of course trivial. Can you find an O(1) space algorithm?

Problem: There are five holes arranged in a line. A hermit hides in one of them. Each night, the hermit moves to a different hole, either the neighboring hole on the left or the neighboring hole on the right. Once a day, you get to inspect one hole of your choice. How do you make sure you eventually find the hermit? Source: Puzzle collection of K. Rustan M. Leino, Microsoft Research Update (02/01/10): Give a deterministic strategy to find the hermit such that the hermit knows our strategy and would want to escape. Update (03/01/10): Solution: Partial solutions provided in comments by Saurabh Agarwal (CSE, IITB 2006-2010) and Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer). Detailed solution posted by me in comments!! Update (20/12/10): A general solution for n holes posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!