CSE Blog - quant, math, computer science puzzles

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!

Source: Quant interview at Religare Technova Problem: Write a C program to compare two integers without using relational operators (== != < <= > >=)  

Source: Problems on Algorithms (Ian Parberry and William Gasarch) Problem:  Let f be a function which takes a number x (number with say n digits, digit i represented by d_i ) as input and outputs sum of the 2001 powers of the digits. So, f(327)=3^2001 + 2^2001 + 7^2001 . Show that for any x , the set { f(x), f(f(x)), f(f(f(x))),.. } is finite. Update (31 January 2011) Solution: Posted by Sudeep Kamath (UC Berkeley PhD Student & EE IITB Alumnus) in comments!

Source:  Mailed to me by Sudeep Kamath  (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus), Taken from Anand Sarwate (Postdoc at UC San Diego, PhD from UC Berkeley) Problem: Given a permutation p of length n , let c(p)  be the number of cycles in p . Suppose p is drawn uniformly from the set of all permutations. Show that Expectation of 2 raised to the power of number of cycles is n+1 , i.e E[ 2^c(p) ]= (n+1) Hint: 1) There is no high funda group theory/number theory involved. I could solve this in 15 minutes \m/ \m/ 2) After you are done, you might want to read this  (*Spoiler Alert*) Solution: Hint posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) in comments! Solution posted by Kalyan in comments! Kalyan's comment explained in detail by me in comments! A simpler solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Alumnus, Indian Revenue Service) in comments!

Source: CMU Puzzle Toad Problem: Farmer Brown is standing in the middle of his perfectly circular field feeling very content. It is midnight and there is no moon and unknown to the farmer, Martian zoologists are landing randomly at points on the circumference of his field. They land at one minute intervals, starting at midnight. As soon as there are martians at points A,B,C such that triangle ABC contains the center of the field, Farmer Brown will be teleported to the waiting space-ship and transported to spend the rest of his life as an exhibit in a Martian zoo. What is the expected time until he is abducted? Related Problem: http://pratikpoddarcse.blogspot.com/2009/10/semi-circle-covering-n-points-puzzle.html Solution: Posted on CMU Puzzle Toad ( http://www.cs.cmu.edu/puzzle/solution33.pdf ). Check my name in the acknowledgments \m/ \m/