CSE Blog - quant, math, computer science puzzles

Source: Quantnet Forums Problem: You pick random numbers between 0 and 1 (uniformly at random) x1, x2, x3.. as long as they keep decreasing x1 > x2 > x3 > ... What is the expected value of the smallest number you pick? Update (26-05-2011): Solution: Posted by Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments! Interesting approach (although wrong) by Gautam Kamath (EE, Senior Undergraduate, IIT Bombay) in comments - Corrected by me!

Problem: Pick a number from 0 to 100. The winner is the person who chooses the number closest to 2/3rds of the group's average response. What is the rational answer? Related thought: Once you get the solution, you would be surprised to see the implications. A Keynesian beauty contest is a concept developed by John Maynard Keynes and introduced in Chapter 12 of his work, "General Theory of Employment Interest and Money" (1936), to explain price fluctuations in equity markets. Read wikipedia article to appreciate it: http://en.wikipedia.org/wiki/Keynesian_beauty_contest Update: (23 March 2011): Solution posted by Gautam Kamath (EE, Senior Undergraduate, IIT Bombay) in comments!

Source: Concrete Mathematics, Donald Knuth Problem: Let's say we have a plane. Draw N straight lines on the plane, any way you wish. Try to divide the plane into as many different regions as possible. How many regions is that? For example, if we draw 1 line on the plane, we can divide it into two regions. If we draw 2 lines, we can divide it into four regions. Followup questions : Source: http://skepticsplay.blogspot.com/ Draw N perfect circles on a plane, of any size, anywhere you want. Into how many regions can you divide the plane? Next, draw N perfect ellipses on another plane. Into how many regions can you divide the plane?

Source: Puzzle Corner, Australian Mathematical Society Problem: The king has 500 barrels of wine, but one of them is poisoned. Anyone drinking the poisoned wine will die within 12 hours. The king has four prisoners whom he is willing to sacrifice in order to find the poisoned barrel. Can this be done within 48 hours? Related Problem: King's Poisonous Wine Puzzle - CSE Blog Update (16/03/2011): Solution posted by Tejas Hiremani (IITB EE Alumnus, Goldman Sachs Quant), Siddhant Agarwal (IITB EE Senior Undergraduate), Mehul Tikekar (IITB EE Alumnus, MIT PhD Candidate) and Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!

Source: Mailed to me by Sudeep Kamath  (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus) Problem: Three people start with integer amounts a,b and c. In each round, each one tosses a fair coin. If not all faces are the same, the person with the different face gets a rupee from each of the other two. If all faces are the same, no money is exchanged. This process is repeated till one of them gets bankrupt. What is the expected number of rounds till the game ends? Related Problems: http://pratikpoddarcse.blogspot.com/2009/10/lets-say-keep-tossing-fair-coin-until.html http://pratikpoddarcse.blogspot.com/2010/11/source-credit-suisse-placement-test-at.html http://pratikpoddarcse.blogspot.com/2011/02/equal-heads-and-tail.html Update (15/03/2011): Hint: Given away by Sudeep. (* Define a martingale of the form Y_n=A_n*B_n*C_n + some other term (where A_n,B_n,C_n are the fortunes of the three players at time n). *) Solution: Posted by chera (Gaurav Sinha, IITK 1...

Source : Interview at one of the quant firms Problem : As posted in problems this and this , this is an extension to the derangement problem. There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men. What is the probability that no person gets the correct hat? Update (March 6, 2011) Solution: Posted by Vipul Verma (Engineer at Portware, IIT KGP and University of South California Alumnus) in comments!

Source: Posted by chera (Gaurav Sinha, IITK 1996 Graduate, Indian Revenue Service) in comments on Consecutive Heads Problem Problem: Suppose you have a fair coin and you toss it until you have got equal number of heads and tails. What is the expected number of tosses? Note that probability that the game stops in odd number of tosses is 0. The probability that the game stops in 2 tosses = 0.5 Solution: Different solutions posted by Kalyan Parhi (EE IITB Alumnus), Abhash, Siva, Gaurav Sinha (CSE IITK 1996 Alumnus, Indian Revenue Service), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer) in comments!