Sunday, September 27, 2026

Cycle lemma

For $n,m,k\in\mathbb{N}_0$ with $m\ge kn$, every arrangement of $m$ $1$s and $n$ $0$s in a circle has exactly $m-nk$ positions such that every nonempty clockwise segment starting there has more than $k$ times as many $1$s as $0$s.



===========================================

Proof

We assume that $m-nk>0$, since otherwise the statement is easy to check.

We only need to check the segments of length at most $m+n$. Given an arrangement $p_1,p_2,\dots,p_{m+n}$, we draw an infinite lattice path $L$ on the $xy$-plane passing through points $$\mathcal{P}=\left\{P_0=(0,0),P_1,P_2,\dots,P_{m+n},P_{m+n+1},\dots\right\}$$ where the unit step from $P_{i-1}$ from $P_i$ is east or north bound if $p_i=0$ or $p_i=1$, respectively. For $i>m+n$ let $p_i:=p_{i-m-n}$. We associate every point $P(x,y)$ with $$f(P):=y-kx.$$ As we go along $L$, the $f$-value starts from $0$ and at each step either drops by $k$ or increases by $1$. We have for $i\ge0$ $$f\left(P_{i+m+n}\right)=f\left(P_i\right)+m-nk.$$

A starting point $p\in\mathcal{P}$ is valid if each of the next $m+n$ points from $\mathcal{P}$ above it has a higher $f$-value than $p$. Below, we describe an algorithm, with proof, that gives every possible valid starting point $P_i$ for $i\in[0,m+n)$.

Let $P_{i_1}\in\mathcal{P}$ be the fartherest point from $P_0$ with the minimum $f$-value among all points from $\mathcal{P}$. We have $i_1<m+n$, or else $$f\left(P_{i_1-m-n}\right)< q_1:=f(P_{i_1})$$ and we have a contradiction. Moreover, $P_{i_1}$ is the valid starting point closest to $P_0$ because every point below $P_{i_1}$ has $f$-value at least $q_1$.

For every $j\in[2,m-nk]$, we find $P_{i_j}\in\mathcal{P}$, the fartherest point above $P_{i_{j-1}}$ and below $P_{m+n}$ with $f$-value $q_j:=q_{j-1}+1$. We have $i_j<m+n$ because $$q_j\le q_{m-nk}=q_1+m-nk-1\le m-nk-1<m-nk=f\left(P_{m+n}\right).$$ Every point between $P_{i_{j-1}}$ and $P_{i_j}$, exclusive, cannot be valid because it has $f$-value at least $q_j$. Also, $P_{i_j}$ is a valid starting point because the endpoint of any segment starting from $P_{i_j}$ that goes beyond $P_{m+n}$ has $f$-value at least $$q_1+m-nk\ge q_1+j=1+q_j.$$

Finally, no point between $P_{i_{m-nk}}$ and $P_{m+n}$, exclusive, is a valid starting point. Each of those points, say $P_r$, has $f$-value at least $$q_{m-nk}+1=q_1+m-nk=f\left(P_{i_1+m+n}\right).$$ So any segment starting from $P_r$ and ending at $P_{i_1+m+n}$ does not have more than $k$ times as many $1$s as $0$s.