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://pratikpoddarcse.blogsp…

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: x2 + 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!