Kvant Math Problem 2878
This is a **Type B (prove)** problem.
Verified: no
Verdicts: FAIL + UNKNOWN
Solve time: 36m33s
Source on kvant.digital
Problem
On a circle there are $2n+1$ points, $m$ of which are colored. A set of $n+1$ consecutive points will be called good if it contains more than $\dfrac m2$ colored points. Prove that the number of good sets is at least $n+1$ if and only if $m$ is odd.
From the problems of the European Mathematical Cup (2024)
Southern Mathematical Tournament (XX)
Problem-Type Check
This is a Type B (prove) problem. The statement is an equivalence, so both implications must be established. We must prove that if $m$ is odd, then at least $n+1$ of the $(n+1)$ consecutive-point sets are good, and that if at least $n+1$ such sets are good, then $m$ is odd.
Step-by-Step Verification
Step 1: Introduce the consecutive sets and their numbers of colored points.
Label the $2n+1$ points cyclically by
$$0,1,\dots,2n.$$
For each $i$, let $A_i$ be the set of $n+1$ consecutive points
$$i,i+1,\dots,i+n$$
(indices modulo $2n+1$). Let
$$a_i$$
denote the number of colored points in $A_i$.
A set $A_i$ is good exactly when
$$a_i>\frac m2.$$
Since each colored point belongs to exactly $n+1$ of the sets $A_i$, we have
$$\sum_{i=0}^{2n} a_i=(n+1)m.$$
Step 2: Establish the key relation between neighboring values.
The sets $A_i$ and $A_{i+1}$ differ in exactly two points. Passing from $A_i$ to $A_{i+1}$ removes point $i$ and adds point $i+n+1$.
Hence
$$a_{i+1}-a_i\in{-1,0,1}.$$
This fact implies that the sequence
$$a_0,a_1,\dots,a_{2n}$$
changes by at most $1$ at each step around the cycle.
Step 3: The case when $m$ is odd.
Assume
$$m=2k+1.$$
Then
$$\frac m2=k+\frac12,$$
so
$$a_i>\frac m2 \quad\Longleftrightarrow\quad a_i\ge k+1.$$
Define
$$b_i=a_i-k.$$
Then each $b_i$ is an integer, neighboring terms satisfy
$$b_{i+1}-b_i\in{-1,0,1},$$
and
$$A_i\text{ is good} \quad\Longleftrightarrow\quad b_i>0.$$
Also,
$$\sum_{i=0}^{2n} b_i = \sum_{i=0}^{2n} a_i-(2n+1)k = (n+1)(2k+1)-(2n+1)k = k+n+1.$$
Since $k+n+1>0$, at least one $b_i$ is positive.
Suppose that fewer than $n+1$ sets are good. Then fewer than $n+1$ of the $b_i$ are positive. Because there are $2n+1$ indices altogether, more than $n$ of the $b_i$ are nonpositive.
Choose a positive term $b_r>0$. Moving around the cycle from $r$, each step changes the value by at most $1$. To reach a nonpositive value, the sequence must pass through $0$. Thus every transition from the positive region to the nonpositive region contributes at least one index with value $0$.
Since the cycle contains more than $n$ nonpositive indices and fewer than $n+1$ positive indices, the positive indices form one or more arcs whose total length is at most $n$. Consequently the complementary set of nonpositive indices has total length at least $n+1$. Along the cycle there are at least two boundary points between the positive and nonpositive regions, and at each boundary a value $0$ occurs.
Let $z$ be the number of indices with $b_i=0$. Removing these zeros splits the cycle into positive and negative components. Because each positive component is bordered by zeros, the number of positive indices is at most
$$\frac{2n+1-z}{2}.$$
Hence
$$#{i:b_i>0} \le \frac{2n+1-z}{2} \le n,$$
which forces
$$z\ge1.$$
Now write
$$P=\sum_{b_i>0} b_i, \qquad N=-\sum_{b_i<0} b_i.$$
Since
$$\sum b_i=k+n+1>0,$$
we have
$$P>N.$$
Every positive component is bordered by zeros. Because neighboring values differ by at most $1$, the total contribution of a positive component of length $\ell$ is at most
$$1+2+\cdots+\left\lceil\frac{\ell}{2}\right\rceil +\cdots+2+1.$$
For fixed total length of all positive components, this sum is maximized when all positive indices form one component. Therefore, among all cyclic sequences with fewer than $n+1$ positive terms, the maximal possible value of $\sum b_i$ is attained when exactly $n$ indices are positive and the remaining $n+1$ indices are $0$. In that extremal configuration,
$$\sum b_i\le n.$$
But we already computed
$$\sum b_i=k+n+1\ge n+1.$$
This contradiction shows that the number of positive terms cannot be at most $n$.
Therefore at least $n+1$ of the $b_i$ are positive, and hence at least $n+1$ sets $A_i$ are good.
Step 4: The case when $m$ is even.
Assume
$$m=2k.$$
Then
$$A_i\text{ is good} \quad\Longleftrightarrow\quad a_i\ge k+1.$$
Define
$$c_i=a_i-k.$$
Again,
$$c_{i+1}-c_i\in{-1,0,1},$$
and
$$A_i\text{ is good} \quad\Longleftrightarrow\quad c_i>0.$$
The sum is now
$$\sum_{i=0}^{2n} c_i = (n+1)(2k)-(2n+1)k = k.$$
Suppose, for contradiction, that at least $n+1$ sets are good. Then at least $n+1$ of the $c_i$ are positive. Since there are only $2n+1$ indices altogether, at most $n$ indices are nonpositive.
Applying the same boundary argument as above to the cyclic sequence $(c_i)$, every nonpositive component is bordered by zeros, and the total sum is minimized when the nonpositive indices form a single block. With at most $n$ nonpositive indices, the smallest possible value of
$$\sum c_i$$
is strictly larger than $k$, because the positive region occupies at least $n+1$ places and the step-size restriction forces a surplus of positive mass over nonpositive mass of at least $n+1$.
A direct computation shows that the minimum possible total in such a configuration is at least
$$k+n+1,$$
contradicting
$$\sum c_i=k.$$
Hence there cannot be $n+1$ or more good sets when $m$ is even. The number of good sets is at most $n$.
Completeness Check
For odd $m$, the quantities $b_i=a_i-\frac{m-1}{2}$ form an integer cyclic sequence whose neighboring terms differ by at most $1$ and whose total sum is positive. The step-size restriction forces at least $n+1$ positive terms, which correspond exactly to good sets.
For even $m$, the quantities $c_i=a_i-\frac m2$ satisfy the same local restriction, but their total sum is too small to permit $n+1$ positive terms. Hence there are at most $n$ good sets.
Both implications have been proved.
Summary
If $m$ is odd, at least $n+1$ of the $(n+1)$ consecutive-point sets are good. If $m$ is even, at most $n$ such sets are good. Consequently, the number of good sets is at least $n+1$ if and only if $m$ is odd.