Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Dec 25, 2010

Water Jug Problem

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!

Dec 19, 2010

Equal zeroes and ones

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!

Dec 8, 2010

Locks and Switches

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

Dec 6, 2010

Order of cards

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!

Stick Broken Into Three Pieces

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:
  1. Two break points are selected randomly (and distributed uniformly) on the stick.
  2. The stick is first broken into two pieces. The longest (or rather, not the shortest) is then broken into two.
  3. The stick is first broken into two pieces. A piece randomly selected with probability 1/2 is then broken into two.
  4. 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!

    Dec 4, 2010

    The Social Network (2010) - FaceMash Algorithm

    (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 went to a page and 2 random images of girls were picked and presented to them. The students then had to click on the hottest girl presented to them and then another set of two girls would be presented asking the students to repeat the same actions they had done. The difference with hotornot was that the girls presented were all Harvard students. In other words, the students were rating girls of Harvard based on their looks (You can imagine why Mark got into trouble).

    The algorithm used - The Elo Rating system - insured a fair rating and ranking of the girls. A hot girl A winning over hot girl B girl would gain more points than winning (or being picked) against ugly girl C. Same goes for the following: ugly girl C wins over ugly girl D. ugly girl C gains some points in her general ranking. If ugly girl C wins over hot girl A then ugly girl C gains more points because the ranking of hot girl A is much higher than ugly girl D. The previous scenario is roughly what the algorithm implemented by Mark was doing. It was somewhat insuring a level of fairness despite the misogynistic nature of the product.

    In today’s society, the Elo Rating system is used by many rating and ranking system to predict the outcome of matches but also insure a level of fairness between teams of different levels playing against each others.  FIFA uses it to rank football teams.

    You can read more about the system on wikipedia page(http://en.wikipedia.org/wiki/Elo_rating_system).

    Probability of Grade A or B

    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 that they all will pass is more than a positive constant independent of n.

    Solution: 
    The solution discussed in a problem before at http://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html

    Nov 28, 2010

    Sorted arrays

    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!

    Coin Tossing - Lucky Dealer

    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!

    Nov 12, 2010

    Optimal Trading Execution

    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!

    Oct 30, 2010

    Number of Colour Changes

    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!

    Random Walk around Square

    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!

    Oct 23, 2010

    Two creepers climbing a tree

    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!

    Oct 20, 2010

    Number of Rounds of Derangements

    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!

    Oct 18, 2010

    Baseball Party

    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!

    Oct 17, 2010

    Equilateral Triangle Division

    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.

    Oct 14, 2010

    Painting Coloured Balls

    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?

    Oct 10, 2010

    Senators and Graph Theory

    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.

    Coin Balancing

    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.

    Oct 5, 2010

    Randomized Ice Cream

    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!

    Sep 23, 2010

    Prime Number Strategy Game

    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!

    Sep 9, 2010

    Number Games

    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)

    Sep 8, 2010

    Equal numbers in a circle

    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/

    Aug 27, 2010

    Conway's Soldiers (CheckerBoard Unreachable Line)

    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!!

    Aug 21, 2010

    Magic Money Machine

    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 link
    Solution posted by Siddhant Agarwal (EE Senior Undergraduate, IIT Bombay) who gave credits to Naval Chopra (CSE Senior Undergraduate, IIT Bombay) in comments!

    Aug 20, 2010

    Number of Sons

    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)

    Aug 18, 2010

    Puzzle on Sorting

    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)

    Jul 28, 2010

    Hats and Rooms

    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 strategy would you suggest for the wizards?

    Update (Dec 04, 2010)
    Solution: One solution posted by Siddhant Agarwal (EE 4th year, IITB) in comments! Another solution posted independently by Hasan Kumar Reddy (mintuhouse) (CSE 2nd year, IITB) and Saurabh Joshi (PhD Student, CSE, IITK). Thanks.

    Jul 25, 2010

    Coin conundrum

    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!

    Differing views

    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)

    Jun 26, 2010

    Coin Sequence Game

    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!

    Jun 20, 2010

    Cube in a sphere

    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!

    Jun 17, 2010

    Russian Coins

    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!

    Jun 16, 2010

    Tip the Balance

    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!

    Jun 7, 2010

    Mathematics of Housie/Tambola

    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 game would be over in approximately 15 calls. If there is one person, we expect the game to go on very close to 90 calls. What is the number of people playing the game so that the expected number of calls would be say 70.

    Of course, I played the game in a homely environment where the "dealer" did not keep any money. So, all the money collected was given back as prizes. Since every person has equal expectation to win, I should expect to get back my investment.

    The questions posed are:
    1) What is the expected number of numbers I expect to be crossed if 100 tickets have been sold?
    2)  What is the number of people playing the game, i.e. the number of tickets sold so that the expected number of calls would be 70?

    Cheers to my first original question :P

    Solution: Analysis done by me and posted in comments!

    Jun 3, 2010

    City Planning

    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

    May 30, 2010

    Veit Elser’s Formidable 14

    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!

    May 7, 2010

    Another Hat Problem

    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 back here but did not get any solution. Then I did not have a solution of my own and the solution on the source was too "non-intuitive". Try it again. Its very interesting and trying to solve it gives u a kick :P

    Apr 25, 2010

    Oleg Kryzhanovsky’s Problem - Coin Sequence

    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 from 1 to n. The coins are labeled from 1 to n. The sequence a(n) is the minimum number of weighings we need on a balance scale to confirm that the labels are correct. The original Oleg Kryzhanovsky’s problem asks to prove that a(6)=2. It is easy to see that a(1)=0, a(2)=1, a(3)=2. Its fun proving that a(4) = a(5) =2.
    *

    Apr 14, 2010

    Weighing Piles of Coins

    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!!

    Apr 2, 2010

    Sleeping Beauty Paradox

    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 proposition that our coin landed heads?"

    This problem is considered paradoxical because the answer is often given as either 1/3 or 1/2.

    Think!! :)

    Detailed analysis in the wikipedia article : http://en.wikipedia.org/wiki/Sleeping_Beauty_problem

    Mar 25, 2010

    Street Watch

    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!!

    Mar 14, 2010

    Unexpectedly Great Expections

    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 HnT will earn you 2n dollars. More explicitly, a T on the first toss gives you 1 dollar, a Head followed by a Tail gives you 2, HHT gives you 4, HHHT gives you 8. As soon as the T turns up, we settle accounts, and leave, never to see each other again. However, there is a constant pre-agreed charge P you must pay to play this game against me (say 10000 $). Upto what price P are you willing to play this game?

    Analysis: The probability of the T is 1/2, of HT is 1/4, of HHT is 1/8 and so on (1/2 * 1/2 * 1/2… as they are independent events).
    Hence your expected value of earnings for this game,

    E(earnings)
    = P(T).Earnings(T) + P(HT).Earnings(HT) + P(HHT).Earnings(HHT)….
    = (1/2 * 1) + (1/4 * 2) + (1/8*4) + (1/16*8) + …. = 1/2 + 1/2 + 1/2 + 1/2 …. = (infinite).

    However the 2000th term of this series of halves is highly improbable (1/2^1000). If you believe expected values, you should be willing to pay any finite amount of money to play this game.

    But if you think over it, the probability that you will get at least 1000$ is 0.0005 which is too small. So, you should not be willing to pay infinite amount of money. Your intuition will not allow you to play with infinite money. Can you explain the paradox?

    Solution: The wikipedia article on St. Petersburg paradox

    Mar 11, 2010

    100 Locomotives Problem

    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.

    Mar 9, 2010

    Sink the Submarine

    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!!

    Mar 4, 2010

    Traffic Jam

    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!

    Real Expensive Pills


    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 or in the future)?

    Update (04/03/2010): Solution posted by Nikhil Pandey (CSE, IITB Alumnus and working at ASUS Taiwan) in comments!!

    Mar 2, 2010

    Perfect Powers

    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 mn, 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)) time.

    Interesting discussion and all solutions in comments!!

    Feb 19, 2010

    Sweet Heart Mix Tape

    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 organizing 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 Thirupugalsamy (Research Assistant, Stony Brook University) and "Anonymous" in comments!!

    Feb 15, 2010

    Coin Weighing Problem

    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, CSE, IITB). Another solution posted by Suman in comments!! Thanx

    Feb 14, 2010

    Drunk Guests

    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 by me in comments!!

    Feb 11, 2010

    Pebble Piles

    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!!

    Feb 10, 2010

    Asking a girl out

    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 every week right now and once every month earlier, on an average I go out once every 15 days. So, I like approximately 60 girls every month. That means I have liked approximately 3,600 girls in 5 yrs.)

    Going ahead with this number, slow as I am in developing human relationships, I need at least 3 dates to "test" whether I like this girl or not. So, If I am to date all 3600 girls, I need 11000 dates. Even if I am "seeing" multiple girls together, I need 30 years to date all of them. So, clearly problem reduces to selecting a smaller subset of girls.

    Which girl should I ask?


    Lets remind you of the scene from the movie: The Beautiful Mind. Suppose all the guys are equally smart and intelligent. Suppose you are there in a bar with a few friends and there is a group of beautiful girls all of whom are brunettes, except one blonde. Most people would like to approach blonde first, however this is not a good strategy as Nash points out:

    If we all go for the blonde, we block each other and not a single one of us is going to get her. So then we go for her friends, but they will all give us the cold shoulder because nobody likes to be second choice. But what if no one goes to the blonde? We don’t get in each other’s way and we don’ t insult the other girls. That’s the only way we win“.

    This means that the prettiest girl in the group would always be there to be asked. No one would ask her out as everyone would be too afraid. Consider a guy who decides to talk to the blonde.

    There are three possibilities:
    1) He talks to the blonde and gets accepted. (Gets x points)
    2) He talks to the blonde and gets rejected. He cannot go to the brunette now. (Gets 0 points)
    3) He does not talk to the blonde and goes to the brunette directly. (Gets y points)

    Note that x>y>0

    Assume there are N guys and N girls (I am not talking about an IIT situation)
    Each guy (since none of them is gay) has 2 possible actions (talk to blonde or talk to brunette). So, the sample space has size 2^n.

    However, a particular guy gets x points if the guy approaches blonde while all others do not. Let us assume that the probability that a guy approaches blonde girl is p. So, for me to approach blonde, the award associated with it is x(1-p)^(n-1). While in the other case, the reward I get is y. So, the pareto optimal equilibrium point is the point when x(1-p)^(n-1) = y

    So, p = 1 - (y/x)^(1/N-1)

    Implications:
    1) At N approaches infinity, p tends to zero. That is people are more afraid to ask the most beautiful girl out.
    2) If you are a beautiful girl and you know that N is large, don't be choosie. Just go out with one of those N guys (I am one :P)
    3) If you are a guy and y value for you is very small, you don't have a lot to lose. Go for the prettiest girl.
    4) Whatever it is, I know the math behind this article is flawed. Read it and forget about it. You are a fool if you argue with me and a gentleman/gentlewoman if you leave nice comments!! :)

    Update(11/02/10): Had a lot of small mistakes earlier. Improved it. :)

    Feb 9, 2010

    Checkers Problem

    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!

    Feb 7, 2010

    Invert the Cups

    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!!

    Fair Hat Game

    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 has said that the test is a fair test of intelligence and bravery.

    Source: http://www.folj.com/

    Update(08/02/10):
    Solution: Posted by Ankush (Sophomore, CSE, IITB) in comments!!

    Jan 29, 2010

    Red vs Black cards - Expected payoff

    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 humble enough to accept defeat :P

    Jan 28, 2010

    Three NOT Gates from Two NOT Gates


    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!


    Jan 25, 2010

    Hungry Lion

    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!!

    Jan 22, 2010

    IBM Ponder This January 2010 Puzzle


    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 :)

    Math Olympiad Problems

    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.

    Jan 20, 2010

    Brave Warrior

    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!!

    Bottom Dollar

    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 Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!!
    Clarification: The two shady people do not form a group. They play to their best personal advantage.

    Give and Take

    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!!

    Horse Race

    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.

    Hats in a circle

    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. :)

    Jan 17, 2010

    Homo paradox

    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 correlation between homosexuality and the fertility of mothers. This suggests that there is a gay gene which at the same time is responsible for female fertility.
    But the model is completely random — there can’t be any correlation.
    Where is the mistake?

    Update(24/01/10): Very simple problem. Don't know why it took me time to solve this. Thanx to Maoo for the solution. Posted by me in comments!!

    Jan 15, 2010

    Duplicate Integer

    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!!

    Jan 13, 2010

    Cap Puzzle (Infinite version)

    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)

    Indian Sudoku Championship 2010



    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
    The Indian Sudoku Championship will consist of two online rounds on 3rd and 9th January 2010 to select the top 30 participants for the finals. There will also be an elimination round to select the top 30 from the on the spot participants on 23rd January 2010. The finals for these 60 participants will be held on 24th January 2010. Detailed instructions are available here

    Championship page
    For further details regarding the Indian Sudoku Championship please visit our championship page

    Registration
    All participants will have to register at the TechFest website to get their participant ID here.

    Download Instruction Booklet

    Download Puzzle Booklet 1 (Day 1)
    Password is wa5endul
    Download Puzzle Booklet 2 (Day 1)
    Password is sh9pylyj
    Download Puzzle Booklet 3 (Day 1)
    Password is bu4tabeb

    Download Puzzle Booklet 1 (Day 2)
    Password is dskn7vytps
    Download Puzzle Booklet 2 (Day 2)
    Password is njtnr2qdbh
    Download Puzzle Booklet 3 (Day 2)
    Password is bdjms8bh3k

    The list of puzzles that appeared for the championship are:

    Round 1
    1. Classic Sudoku

    Round 2
    1. Odd-Even Sudoku
    2. Diagonal Sudoku
    3. Frame Sudoku
    4. Sudoku XV
    5. Irregular Sudoku
    6. Consecutive Sudoku

    Round 3
    1. Outside Sudoku
    2. Quadruple Sudoku
    3. Magic Square Sudoku
    4. No Knight Sudoku
    5. Group Sum Sudoku
    6. Toroidal Sudoku

    Results

    1. Jan Mrozowski (Poland) - 1970
    2. Jakub Ondrousek (Czech Republic) - 1910
    3. Rohan Rao (India) - 1875
    4. Jan Novotny (Czech Republic) - 1840
    5. Nikola Zivanovic (Serbia) - 1730
    6. Rishi Puri (India) - 1725
    7. Ritesh Gupta (India) - 1655
    8. Chen Cen - 1585
    9. Jakub Hrazdira (Czech Republic) - 1550
    10. Rakhel Parida (India) - 1435
    10. Puneet Goenka (India) - 1435

    Indian results

    1. Rohan Rao - 1875
    2. Rishi Puri - 1725
    3. Ritesh Gupta - 1655
    4. Rakhel Parida - 1435
    4. Puneet Goenka - 1435
    6. Gaurav Korde - 1360
    7. Priyanka Gupta - 1355
    8. Pooja Gaddyan - 1345
    9. Neha Sharma - 1295
    9. Pratik Poddar - 1295
    9. Gnyanendra Kumar - 1295

    Complete Results

    Jan 12, 2010

    Card Shuffle

    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!!

    Two envelopes Problem

    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:
    1. Denote by A the amount in the selected envelope.
    2. The probability that A is the smaller amount is 1/2, and that it's the larger also 1/2
    3. The other envelope may contain either 2A or A/2
    4. If A is the smaller amount, the other envelope contains 2A
    5. If A is the larger amount, the other envelope contains A/2
    6. Thus, the other envelope contains 2A with probability 1/2 and A/2 with probability 1/2
    7. So the expected value of the money in the other envelope is: \frac{1}{2} 2A + \frac{1}{2} \frac{A}{2} = \frac{5}{4}A
    8. This is greater than A, so swapping is favored
    9. After the switch, reason in exactly the same manner as above, but denote the second envelope's contents as B
    10. It follows that the most rational thing to do is to swap back again
    11. This line of reasoning dictates that envelopes be swapped indefinitely
    12. As it seems more rational to open just any envelope than to swap indefinitely, the player is left with a paradox.
    The puzzle: 

    The puzzle is to find the flaw, the erroneous step, in the switching argument above. This includes determining exactly why and under what conditions that step is not correct, in order to be sure not to make this mistake in a more complicated situation where the misstep may not be so obvious. In short, the problem is to solve the paradox.


    Disclaimer: The problem sometimes is included under "unsolved" problems. A thought and study should be great anyways. :)

    References: Wikipedia link

    Dont roll more

    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 !!

    Jan 10, 2010

    Correct Letters

    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!!

    Jan 8, 2010

    Coupon Collector Problem

    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!!

    Jan 7, 2010

    Infected Chessboard

    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's Collection"

    Problem: An infection spreads among the squares of an nXn checkerboard in the following manner. If a square has two or more infected neighbours, it becomes infected itself. (Each square has 4 neighbours only!). Prove that you cannot infect the whole board if you begin with fewer than n infected squares.

    A different version mailed to me by Nikhil Garg (Sophomore, IIT Delhi) a few days back.

    P.S. : 4th year 2nd sem rocks! Infi time for infi puzzles :P

    Update (10/01/10): Solution: Posted by Nikhil Garg (Sophomore, IIT Delhi) in comments!!

    Chessboard Circle

    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?

    Capturing a pirate ship

    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 solution in comments!!

    Jan 4, 2010

    Threaded Pins

    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?

    Jan 1, 2010

    Finding a hermit

    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!