CSE Blog - quant, math, computer science puzzles

Source: Peter Winkler, "Seven Puzzles You Think You Must Not Have Heard Correctly" (devised by Peter Bro Miltersen). Problem: The names of 100 prisoners are placed in 100 boxes, one name per box. Each prisoner enters alone and may open at most 50 boxes. Unless EVERY prisoner finds his own name, all are executed. Random guessing works with probability (1/2)^100. Find a strategy with success chance over 30%. Solution: Highlight the part between the * symbols for the answer. * Number the boxes 1-100. Each prisoner opens his own box, then the box of the name inside, following the chain. He succeeds iff his cycle has length at most 50. All survive iff no cycle exceeds 50: P(fail) = 1/51 + ... + 1/100 = 0.688, so P(survive) = 0.312, tending to 1 - ln 2 = 30.7%. *

Source: Sent to me by Pritish Kamath ( http://www.mit.edu/~pritish/ ) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclag...

Problem / Observation: The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically. Update (23 Oct 2014): Solution:  Posted by Mike Earnest and Taz in comments!

Source: Asked to a friend at Goldman Sachs Quant Interview Problem: Estimate the value of pi using a dice Update: (21 June 2014) Solution posted by Tushar Makkar, 'My first amateur attempt', Satadip, Gaurav Bajaj and me (Pratik) in comments. Thanks

Problem 1: Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm? Problem 2: Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly. Update (24 June 2014): Solution: Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks claimtoken-52ac74fbddf1e

Source: Mailed to me by Vashist Avadhanula (PhD Student at Columbia Business School, EE IITB 2013 Alumnus) Problem: Consider a case where you flip two fair coins at once (sample space is HH, HT, TH & TT) you repeat this experiment many times and note down the outputs as a sequence. What is the expected number of flips (one flip includes tossing of two coins) to arrive at the sequence HHTHHTT. Solution: Highlight the part between the * symbols for the answer. * Answer: 2^14 / 255 = 64 + 64/255 = 64.251 flips (each flip = both coins tossed together). Why it is not just 2^7/2 = 64 or 2^6 = 64: the 7-bit target HHTHHTT is not aligned to the coin-pair boundaries, and a flip is consumed even when the pattern completes on its first coin. Model it as a Markov chain on the longest suffix of the bit stream matching a prefix of HHTHHTT (7 transient states + absorbing). Each flip moves two bits at once; solving the 7 linear equations E_s = 1 + (1/4) * sum over the four two-bit outcome...

Source: Asked for a data scientist position at a technology startup in financial services sector in London Problem: Given python code to calculate maximum in an array of integers x def find_max(x):          max_num = x[0]          for i in x[1:]:         if i > max_num:             max_num = i   << Expected number of times this expression  was evaluated     return max_num Calculate the expected number of times the expression max_num = i was evaluated, given that array x was taken from a uniform random distribution. Solution: Highlight the part between the * symbols for the answer. * Answer: H_n - 1 = 1/2 + 1/3 + ... + 1/n, which is about ln(n) - 1 + gamma (roughly log n updates). Reason: the line max_num = i executes on iteration i exactly when the i-th element is the largest of the first i elements. For i.i.d. draws (with ties having pr...

Source: Jane Street Capital Interview (Quantnet) Problem: You are given a 100 sided die. After you roll once, you can choose to either get paid the dollar amount of that roll OR pay one dollar for one more roll. What is the expected value of the game? (There is no limit on the number of rolls.) Update (22 June 2014): Solution posted by me, Felix, JDGM, Sebastian, Fu Shi and Dumb Phoenix in comments!

Source: Discussion with Ashwin Rao ( http://zlemma.com , Ex-MD Morgan Stanley) and Gaurav Kumar (Credit Suisse IB, Ex-MS, GS, IITB CSE 2006, Booth 2012) Problem: Suppose teams A and B play in the world series of up to 7 games in which the first team to win 4 games wins the series and then no more games are played. Suppose that you want to bet on each individual game in such a way that when the series ends you will be ahead by exactly $100 if your team wins the series, or behind by exactly $100 if your team loses the series, no matter how many games it takes. How much would you bet on the first game? Update (22 June 2014): Solution posted by Alex, JDGM, Arnab in comments!

Source: Counter-intuitive Conundrums Problem: Someone hands you a deck of cards which you thoroughly shuffle. Next, you start to deal them, face-up, counting the cards as you go. “One, Two, Three …” The aim is to predict what the count will be when you encounter the second black Ace in the deck. If you had to select one position before you started to deal, what number would you select that maximizes your chance of guessing the location of the second black Ace? Solution: Posted by Sky in comments!

Source: Puzzle collection by Raphael Reischuk Problem: Assume the following 3-player game consisting of several rounds. Players A and B build a team, they have one fair coin each, and may initially talk to each other. Before starting the first round, however, no more communication between them is allowed until the end of the game. (Imagine they are separated in different places without any communication infrastructure.) A round of the game consists of the following steps:  (1) the team gives one dollar to player C.  (2) Both A and B toss their coins independently.  (3) Both A and B try to predict the other's coin by telling the guess to C. (No communication: A does not know the outcome of B's coin toss, and vice versa, nor the guess).  (4) If C verifies that both A and B guess the other's coin correctly, then C has to give 3 dollars back to the team.  Should C play this game? Previously Asked Coin Puzzles: Coin Balancing Coins Puzzle...

Source:  xkcd wiki Problem: The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants. You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza? You don't know which round number it is, but if you ask, the king will tell you. Does it matter? Disclaimer: Very easy problem! Update (31 January 2013): Title changed to "Pizza Distribution Puzzle" from "...

1) If cor(a,b)=0.5 and cor(a,c)=0.0, what is the range for cor(b,c) 2) A deck of pokers. Three choices: A: 26 black, 26 Red; B: 13 black, 13 Red; C: random 26 card from the deck. Take the first two cards, if same color, the win $1, otherwise lose $1. Which deck is best for you if you are playing? Why? 3) What is the probability of a random generator generating 10 consecutive numbers in ascending order (assume it is a perfect random generator) Update (24/12/2012): Solution posted by AH in comments! Solution explained in detail by me. Thanks

Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on " Post a Question " page. Problem: What is the probability that two uniform random points (to be precise: i.i.d. with respect to Lebesgue measure) in the square are such that center of the square lies in the circle formed by taking the points as diameter. Edit: Problem wording made more mathematical. Update: (24/12/2012) Correct solutions by Barun Kumar Kejriwal, Akhil Kumar, Aastha Airan, Arpit Goyal and Yashoteja in comments! Thanks a ton.

Source: 40 Puzzles and Problems in Probability and Mathematical Statistics (Interesting book by Wolfgang Schwarz) Inspiration: This problem demonstrates clearly the shortcomings of out grading system through exams Problem: Peter has an IQ of 90 whereas the IQ of Paula is 110. However, due to unsystematic biological or psychological day-to-day variation that is unrelated to the IQ per se, any single measurement of either IQ is distorted by an independent additive measurement error that has a zero-mean normal distribution with some variance. For example, if Paula’s IQ were measured repeatedly, the outcomes would be normally distributed with a mean of 110 (her “true” IQ) and some standard deviation. Suppose that either Peter or Paula is selected at random (p = 0.5), and his/her IQ is measured. You do not know who was selected, but you are told that the result of this first measurement is 105. Now the same person —whose identity is unknown to you — is measured a secon...

Source: http://www.stanford.edu/~gowthamr/puzzles.html Problem: Suppose the starting point of a particle undergoing Brownian motion in 2 dimensions is chosen uniformly at random on an imaginary circle C_1. Suppose there is a solid circle C_2 completely inside C_1, not necessarily concentric. Show that the particle hits the boundary of C_2 with uniform distribution. Book: I strongly recommend the book by Steven Shreve for understanding Brownian Motion and its applications in Financial Modelling (Its expensive! Flipkart Link: Stochastic Calculus for Finance II ) Update (4th Feb 2013): Solution posted by me in comments!

Source: IBM Ponder This July 2012 Problem very similar to   CSE Blog: Painting Coloured Balls  ( Link:  http://pratikpoddarcse.blogspot.in/2010/10/painting-coloured-balls.html  ) Problem: Alice and Bob are playing two games: they start simultaneously and the first one to win his game is the winner. Alice is given an urn with N balls, colored in N different colors and in every second she randomly picks two balls, colors the first ball in the color of the second ball and returns both to the urn. Her game is over once all the balls in the urn have the same color. Bob is given an urn with M balls, all colorless, and in every second he picks a random ball, color it, and puts it back to the urn. Bob's game is over once all his balls are colored. Our question is: what are the possible values of M for which (on average) Bob is expected to lose for N=80 and win for N=81?  We ask for possible Ms for which the expected time of Bob's game is smaller than Alice's...

Source: Quantnet Interview Questions Problem: If a car passes at the crosswalk on average every 10 seconds and you need 20 seconds to pass the road, how long does it take you on average to cross the road? Note that since the problem is not very well specified, make reasonable assumptions to solve it. It would be fun if before solving mathematically, you try and guess a time estimate. :-) Update (3rd January 2011): Solution posted by Santosh Ananthakrishnan (EE Final Year DD Student IIT Bombay) and Animesh Saxena (Manager at Karvy Private Wealth) in comments!

Source: Very standard problem in Quant interviews (Taken from quantnet, xkcd forums) Problem: A bowl of spaghetti contains n strands. Thor picks two ends at random and joins them together. He does this until no ends remain. What is the a) expected number of spaghetti loops in the bowl? b) expected average length of the loops? (in strands) c) expected number of k -hoops? ( a k -hoop is a loop made from k strands) Solution: Highlight the part between the * symbols for the answer. * a) Expected number of loops = 1 + 1/3 + 1/5 + ... + 1/(2n-1) (the sum of the first n odd reciprocals, about (ln n)/2 + ln 2 + gamma/2). When m strands (2m ends) remain, pick any end: the other end you join it to is uniformly one of the 2m - 1 remaining ends, and exactly one of those closes a loop. So a loop is created with probability 1/(2m-1) at that step, and summing the indicators over m = n, n-1, ..., 1 gives the answer (NG's recurrence; Rudradev Basak's generating funct...

Source: Asked to me by Chinmay Chouhan, Junior Undergraduate, CSE IITB Problem: Given the set of numbers from 1 to n : { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw? Update (Oct 30, 2011): Solution posted by Yashoteja Prabhu (RA at Microsoft Research, IITB CSE 2011 Alumnus), Garvit Juniwal (IITB CSE Senior Undergraduate), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer), Nikhil Garg (IITD CSE Senior Undergraduate) and Avinash in comments!