CSE Blog - quant, math, computer science puzzles

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!