Using your Head is Permitted

August 2011 riddle

UPDATE (2 August): The solution this month should be presented in closed form (e.g. no recursion, no unbounded sums).

We allot a bit-string of length 2n randomly and uniformly from the set of bit-strings containing exactly n zeros and n ones.

What is the expected number of prefixes of this string that contain an equal number of zeros and of ones (including the empty string and the full-length string)?

As always: prove your answer.

List of solvers:

Jan Fricke (2 August 05:06)
Gaoyuan Chen (2 August 15:10)
Djinn Lu (2 August 18:21)
Albert Stadler (2 August 20:57)
Yan Wang (3 August 11:17)
Lu Wang (3 August 17:58)
Sanlee Xin (5 August 19:04)
Joseph DeVincentis (12 August 06:21)
Ganesh Lakshminarayana (16 August 02:32)
Daniel Bitin (17 August 07:48)
Liubing Yu (22 August 11:32)
Jens Voss (22 August 17:25)
Feifei Ji (24 August 01:13)
Wu Zhengkai (28 August 11:05)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page