Prove that in a necklace consisting of $kX$ blue beads and $kY$ red beads, there exists a substring of length $X + Y$, with $X$ blue beads.

Question

Prove that in a necklace consisting of $kX$ blue beads and $kY$ red beads, there exists a substring of length $X + Y$, with $X$ blue beads and $Y$ red beads.

I found this claim while solving a competitive programming problem, and the proof provided seemed wrong. To check the claim, I coded a random checker in Python, and it seems that the claim is correct.

In the problem, by substring, I mean a continuous subsegment of the necklace. Also, since it's a necklace, the first and last beads are considered adjacent.

Answer 1

Consider the $k$ dijoint substrings of length $X+Y$, $(a_1,\cdots, a_{X+Y}),(a_{X+Y+1},\cdots, a_{2(X+Y)}), \cdots ,(a_{(k-1)(X+Y)+1},\cdots, a_{k(X+Y)})$.

Let $X_1, X_2, \cdots X_k$ be the number of blue beads in each of these substrings, assume none of these $X_i$'s equals $X$ (otherwise we are done), there must be a contigous pair such that $ X_i < X < X_{i+1}$ or $X_i > X > X_{i+1}$. Now consider the substrings $(a_{i(X+Y)+1},\cdots, a_{(i+1)(X+Y)}),(a_{i(X+Y)+2},\cdots, a_{(i+1)(X+Y)+1}),\cdots,(a_{(i+1)(X+Y)+1},\cdots, a_{(i+2)(X+Y)})$

as we move from one sequence to the next the number of blue beads will change by $1$, zero or $-1$ so there must be a point where the number of blue beads is $X$.