66th Czech and Slovak Mathematical Olympiad

Question

To a sequence of n zeros and n ones, we assign the number of maximal contiguous runs of equal digits in it. (For instance, sequence 00111001 has four such runs: 00, 111, 00, and 1.) For a given n we sum up all the numbers assigned to all such sequences. Prove that the resulting sum is equal to (n + 1) 2nn.

Accepted Answer

Consider one such sequence and let us count (from left to right) how many maximal contiguous runs (from now on, just runs) it contains. We count a new run when it ends, that is when we hit a different digit or the right end. The number of runs is thus one more than the number of digits that follow a different digit (we say that the run changes at these positions). Instead of counting runs in different sequences, let us count sequences that change run at a given position.

There are

2 n - 1

possible positions to change the run (all the positions but the first one). There are two options for the digit at this position and this uniquely determines the digit at the preceding position. All the remaining positions can be arbitrarily filled with remaining

n - 1

zeros and

n - 1

ones. Altogether, we get

(2 n - 1) \cdot 2 \cdot (n - 1 2 n - 2)

changes of runs in all the sequences. Since in each of the

(n 2 n)

sequences there is one more run than there are changes, in total we obtain

2 (2 n - 1) (n - 1 2 n - 2) + (n 2 n) = 2 n (n 2 n - 1) + (n 2 n) = 2 n (n - 1 2 n - 1) + (n 2 n) = n (n 2 n) + (n 2 n) = (n + 1) (n 2 n),

where we used an obvious identity

k (k m) = m (k - 1 m - 1) .