CSE Blog - quant, math, computer science puzzles

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

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 H n T will earn you 2 n  dollars. More explicitly, a T on the first to

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.

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

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!

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

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 m n , 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)) tim