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

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