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!
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Oct 30, 2010
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!
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!
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!
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!
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.
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?
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.
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.
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!
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!
Subscribe to:
Posts (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

-
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 art...
-
Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...
-
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
