For a sequence with some ones and zeros, we count the number of continuous runs of equal digits in it. (For example the sequence has continuous runs: , , , , , , .) Find the sum of the number of all continuous runs for all possible sequences with ones and zeros.
Solution
The answer is .
We show that for all sequences with zeros and ones, the sum of all continuous runs is given by .
We first count the number of changes, which means a pair of consecutive digits which is or . There are positions for which changes may occur. For each fixed position, there are ways to choose the pair of digits for this change, and ways to put the remaining zeros and ones. Hence, there are
changes in total.
Now, for each sequence, the number of runs is more than the number of changes. Since there are sequences in total, the total number of runs is
using the fact .
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.