Given is a natural number $n > 5$. On a circular strip of paper is written a sequence of zeros and ones. For each sequence $w$ of $n$ zeros and ones we count the number of ways to cut out a fragment from the strip on which is written $w$. It turned out that the largest number $M$ is achieved for the sequence $11 00...0$ ($n-2$ zeros) and the smallest - for the sequence $00...011$ ($n-2$ zeros). Prove that there is another sequence of $n$ zeros and ones that occurs exactly $M$ times.
Problem
Source: All-Russian 2022 10.6
Tags: combinatorics, All Russian Olympiad, Binary
VicKmath7
20.04.2022 20:38
Sketch of the official solution: Let $N$ be the number of appearances of a string $x=100...01$, where the zeros are at least $n-2$. Let $N_{0x}$ denote the number of appearances of $0x$, similarly for $1x, x1, x0$. Note that $N_{0x}+N_{1x}=N_{x0}+N_{x1}=N$, $N_{1x}=M$, $N_{x1} \leq N_{0x}$, so $N_{x0}=M$.
I find this a bit similar to ISL 2011 C6 - see the beginning of the official solution given in the shortlist.
starchan
20.03.2023 11:31
cute
Suppose there are $a_1$ 0s followed by $b_1$ 1s followed by $a_2$ 0s and so on until we reach $b_k$ 1s and complete the loop. Suppose there are $m$ occurences of $00\dots11$ where there are $n-2$ zeroes. Observe that if $k = 1$, then we have $m = M$ and any string of length $n$ must appear exactly $M$ times, so done. Henceforth, we assume $k > 1$. For a statement $X$, define it's truth as $1_X$ where $1_X = 0$ if $X$ is false and $1$ otherwise. The point is to observe that the string $00\dots 11$ appears precisely when the string of zeroes contains at least $n-2$ zeroes and the following string of ones contains at least $2$ ones. This implies that \[m = \sum_{i} (1_{a_i \geqslant (n-2)} \cdot 1_{b_i \geqslant 2}) \]and similarily \[M = \sum_{i} (1_{a_i \geqslant (n-2)} \cdot 1_{b_{i-1} \geqslant 2})\]where the sum is over $i \in \mathbb{Z}/k\mathbb{Z}$ and we read indices modulo $k$. Because $1_X + 1_{X'} = 1$, we have \[m = \sum_{i} 1_{a_i \geqslant (n-2)} - \sum_{i} 1_{a_i \geqslant (n-2)} \cdot 1_{b_i = 1}\]and similarily \[M = \sum_{i} 1_{a_i \geqslant (n-2)} - \sum_{i} 1_{a_i \geqslant (n-2)} \cdot 1_{b_{i-1} = 1}\]Now the trick is to observe that $\sum_{i} 1_{a_i \geqslant (n-2)} \cdot 1_{b_i = 1}$ is simply counting the number of occurences of the string $0000\dots 10$ where there are $n-1$ zeroes, and similarily $\sum_{i} 1_{a_i \geqslant (n-2)} \cdot 1_{b_{i-1} = 1}$ is counting the number of occurences of the string $0100\dots 0$ (there are $n-1$ zeroes). Denoting the counts of occurences of these strings by $X_1, X_2$ respectively, we obtain that $M-m = X_1-X_2$. Because $X_1-X_2 \leqslant M+(-m) = M-m$, equality must hold everywhere and we have $X_1 = M, X_2 = m$.
In particular the string $0\dots010$ appears exactly $M$ times and we are done.