CSE Blog - quant, math, computer science puzzles

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 *

Source: IBM Ponder This - May 2011 Problem Problem: A barcode is composed of a series of variable-width white and black bars. One of the important features of the barcode is that no bar be too wide; otherwise, the reader might get out of synchronization. Suppose we use the following barcode system, where we take a completely random sequence of bits and use it to build the bars. For example, the 7-bit-long sequence 0111001 will generate four bars of varying lengths: white(1), black(3), white(2), black(1). Such a system will generate, every once in a while, bars that are too wide. Let's call any black bar whose width is 20 bits or more a "bad bar". What is the expected number of bits in the bars that are between two adjacent bad bars? Other IBM Ponder This Problems on the blog: http://pratikpoddarcse.blogspot.com/2010/01/ibm-ponder-this-january-2010-puzzle.html http://pratikpoddarcse.blogspot.com/2009/11/ibm-ponder-this-november-challenge.html http://pr

Source: Very interesting problem taken from Tanya Khovanova’s Math Blog Problem: I found this cute problem in the Russian book Sharygin Geometry Olympiad by Zaslavsky, Protasov and Sharygin. Find numbers p and q that satisfy the equation: x 2 + px + q = 0. The book asks you to find a mistake in the following solution: By Viète’s formulae we get a system of equations p + q = − p , pq = q . Solving the system we get two solutions: p = q = 0 and p = 1, q = −2. What is wrong with this solution? Update (26-05-2011) Solution: Posted by Sudeep Kamath  (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus) in comments and of course on Tanya Khovanova’s Math Blog

Source: Quantnet Forums Problem: You are given a stick of length 1 and a supply of n identical needles of length h. Drop the n needles at random on the stick, subject to the following "needle discipline": needles should fit entirely within the stick (they cannot stick out). What is the probability that no two needles overlap? Let us assume that the stick is one-dimensional, so that the needles can only lie along the length of the stick. Update (26-05-2011) Solution: Posted by Siddhant Agarwal (EE IITB 2011 Alumnus), Ameya Ranade (CSE IITB 2009 Alumnus) and me in comments!