Maths Olympiad Prep

Library / /80 of 136

Combinatorics Difficulty 8.0 National Olympiad, round 2 Prove it Hong Kong

For a sequence with some ones and zeros, we count the number of continuous runs of equal digits in it. (For example the sequence 011001010011001010 has 77 continuous runs: 00, 1111, 0000, 11, 00, 11, 00.) Find the sum of the number of all continuous runs for all possible sequences with 20192019 ones and 20192019 zeros.

Solution

The answer is 2020(40382019)2020\binom{4038}{2019}.
We show that for all sequences with nn zeros and nn ones, the sum of all continuous runs is given by (n+1)(2nn)(n+1)\binom{2n}{n}.

We first count the number of changes, which means a pair of consecutive digits which is 0101 or 1010. There are 2n12n-1 positions for which changes may occur. For each fixed position, there are 22 ways to choose the pair of digits for this change, and (2n2n1)\binom{2n-2}{n-1} ways to put the remaining n1n-1 zeros and n1n-1 ones. Hence, there are
2(2n1)(2n2n1) 2(2n-1)\binom{2n-2}{n-1}
changes in total.

Now, for each sequence, the number of runs is 11 more than the number of changes. Since there are (2nn)\binom{2n}{n} sequences in total, the total number of runs is
2(2n1)(2n2n1)+(2nn)=2n(2n1n)+(2nn)=2n(2n1n1)+(2nn)=n(2nn)+(2nn)=(n+1)(2nn), \begin{aligned} & 2(2n-1)\binom{2n-2}{n-1} + \binom{2n}{n} \\ &= 2n\binom{2n-1}{n} + \binom{2n}{n} = 2n\binom{2n-1}{n-1} + \binom{2n}{n} \\ &= n\binom{2n}{n} + \binom{2n}{n} = (n+1)\binom{2n}{n}, \end{aligned}
using the fact k(mk)=m(m1k1)k\binom{m}{k} = m\binom{m-1}{k-1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.