MathDB

For a positive integer

n

define a sequence of zeros and ones to be balanced if it contains

n

zeros and

n

ones. Two balanced sequences

a

and

b

are neighbors if you can move one of the

2n

symbols of

a

to another position to form

b

. For instance, when

n = 4

, the balanced sequences

01101001

and

00110101

are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set

S

of at most

\frac{1}{n+1} \binom{2n}{n}

balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in

S

Problem Statement