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 the pd

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!