CSE Blog - quant, math, computer science puzzles

Source: The Hidden Mathematics of Sport Problems: Football tables have been the basis of many a brainteaser over the years. These two puzzles ask you to work out what the scores were in all matches played so far this season. Puzzle 1: Each team played the others once, what were the scores in each match (2 points for a win, 1 for a draw)? Played Goals for Goals against Points United 2 1 0 3 City 2 2 1 2 Albion 2 0 2 1 Puzzle 2: The league table below got smudged in the rain, and is only partly legible. Eventually each team will play the others once, but the tournament isn't over yet. Can you find all the results? Played Won Lost Drawn Goals for Goals against Points Athletic 3 2 * * 4 4 * Rovers * 1 * 0 3 0 * Town * * * 0 1 1 * Wanderers * * * * * * * Update (27 Aug 2011): Solution posted by Gautam Kamath (EE, Senior Undergraduate, IIT Bombay) in comments!

Source: IMO 2011 Problem (sent to me by Dinesh Dharme, CSE IITB 2011 Alumnus, Credit Suisse Analyst) Problem: Let n > 0 be an integer. We are given a balance and n weights of weight 2^0, 2^1, . . . , 2^(n−1). We are to place each of the n weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed. Determine the number of ways in which this can be done. Disclaimer: As expected from an IMO problem, very difficult! But interesting solutions at www.math.leidenuniv.nl/~desmit/pop/2011_imo_final6.pdf Update   (25 Aug 2011): I did not write in clearly in the post. One of the solutions provided in the pdf is an oral 3 line solution to the problem. It cannot get smaller than this :P. Even if you have solved the problem, do have a look at th...

Source: A book on probability puzzles Problem: Suppose we play a game with a die where we roll and sum our rolls as long as we keep rolling larger values. For instance, we might roll a sequence like 1-3-4 and then roll a 2, so our sum would be 8. If we roll a 6 first, then we’re through and our sum is 6. Three questions about this game: (a) What is the expected value of the sum? (b) What is the expected value of the number of rolls? (c) If the game is played with an n-sided die, what happens to the expected number of rolls as n approaches infinity? Update (Aug 31, 2011) Solution posted by Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) and Siva in comments!

Source: Sent to me by Nikhil Garg (CSE Senior Undergrad, IITD) - who got this from Rudradev Basak Problem: There are K balls in a sack numbered 1 to K. Bob chooses a ball at random notes down its number and puts it back in sack. He does this process for N times. What is the expected value of the frequency of the most frequent element ? Best of Luck! I do not have the solution. So, tell me if you get one. Thanks.

Source: Asked to me by Prateek Srivastava (IITB CSE Alumnus 2010 and Yahoo! Software Engineer) (also asked in a quant firm placement test) Problem: We have an unlimited number of dice at our disposal. Let's roll the die. If the outcome is 1, 2, or 3, we stop; otherwise, if it is 4, 5, or 6, a corresponding number of dice are rolled. For example, if the first roll gives 5, then we roll 5 dice, and so on. This procedure continues for every rolled dice whose outcome is 4, 5, or 6. Let N denote the N-th round of rolls. What is the total expected value at the end of the N-th round of rolls? Update (17 July 2011): Solution posted by Unknown in comments. There is a slight ambiguity in the problem statement, so please do not waste a lot of time. Thanks.

Problem 1: Each cell in a square table contains a number. The sum of the two greatest numbers in each row is  a , and the sum of the two greatest numbers in each column is  b . Prove that  a = b . Problem 2:  Given some m x n table, and some numbers in its fields. You are allowed to change the sign in one row or one column simultaneously. Prove that You can obtain a table, with non-negative sums over each row and over each column. Update (11th June 2011): Solution to both problems posted by NG [Nikhil Garg (CSE IIT Delhi final year undergraduate student)] in comments! Thanks. Confession: I could never solve Problem 1 even after spending hours. :P :(

Source: http://www.quantnet.com/forum/threads/colored-runs-of-cards.6508/ Problem: There are 26 black(B) and 26 red(R) cards in a standard deck. A run is a maximum block of consecutive cards of the same color. For example, a sequence RRRRBBBRBRB of only 11 cards has 6 runs; namely, RRRR, BBB, R, B, R, B. Find the expected number of runs in a shuffled deck of cards. Update (29-05-2011): Solution: Posted by Siddhant Agarwal (EE IITB 2011 Alumnus) in comments! Select the text between * to see the solution. * Let us have n red cards and n black cards. Consider any sequence X_1,X_2..X_2n. Now define Y_1 = 1, Y_i = 1 if X_i and X_(i-1) are of diff colours Y_i = 0 otherwise. Clearly we have to find E[Y_1 + ..+Y_2n] E[Y_1] = 1 by def. E[Y_i] = E[Y_j] for all i,j>=2 by symmetry. Also E[Y_i] = $2*(\binom{2n-2}{n-1})/($\binom{2n}{n}) so ans = 1+(2n-1)*E[Y_i] = n+1 *