Mar 25, 2010

Street Watch


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,

= 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.

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?

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


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"

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

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

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