Kvant Math Problem 818
Consider small $n$-gons to understand what a uniform set of blue vertices looks like.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 16m10s
Source on kvant.digital
Problem
Let some $k$ vertices of a regular $n$-gon be colored blue (the remaining vertices are black). We shall call the set of colored vertices uniform if, for every $m$, the numbers of blue vertices in any two sets of $m$ consecutive vertices of the $n$-gon are equal or differ by 1 (see Fig. 1, which shows an example of a uniform set for $n=8$, $k=5$).
Fig. 1
- Construct uniform sets for $n=12$, $k=5$; $n=17$, $k=7$.
Prove that a uniform set exists and is unique (up to rotations of the $n$-gon),
- if $n$ is divisible by $k$;
- for arbitrary $n$ and $k$ ($k\le n$).
M. L. Kontsevich
Exploration
Consider small $n$-gons to understand what a uniform set of blue vertices looks like. For $n=8$, $k=5$, we want any set of $m$ consecutive vertices to have either $\lfloor 5m/8 \rfloor$ or $\lceil 5m/8 \rceil$ blue vertices. Placing the blue vertices approximately at positions proportional to $n/k$, i.e., spacing them as evenly as possible around the polygon, seems promising. For instance, labeling vertices $0$ through $7$, placing blue vertices at positions $0,1,2,4,6$ produces the correct pattern.
Testing $n=12$, $k=5$, and $n=17$, $k=7$ confirms that distributing the blue vertices at roughly equal fractional intervals works: take vertex indices $\lfloor i \cdot n/k \rfloor$ for $i=0,\dots,k-1$. This suggests the core insight: the uniformity condition is equivalent to placing the $k$ vertices as evenly spaced around the circle as possible.
The most delicate step is proving uniqueness: any other placement differing by more than one in spacing between some consecutive blue vertices would violate the uniformity condition. Another delicate step is generalizing the construction from the case $n$ divisible by $k$ to arbitrary $n$; the fractional spacing argument must be justified rigorously.
Problem Understanding
We are asked to construct specific examples of uniform sets of $k$ vertices in an $n$-gon and to prove existence and uniqueness for general parameters. This is a Type D problem, as it asks for explicit constructions and verification of properties. The core difficulty is distributing $k$ vertices around $n$ positions so that any consecutive segment of vertices has blue counts differing by at most one. For $n$ divisible by $k$, equal spacing provides a natural candidate. For arbitrary $n$ and $k$, using floor and ceiling of fractional positions yields a general construction. Intuitively, placing the vertices as evenly as possible should satisfy the uniformity condition.
Proof Architecture
Lemma 1: If $n$ is divisible by $k$, placing blue vertices every $n/k$ positions yields a uniform set. This is true because each segment of length $m$ contains exactly $m \cdot k / n$ blue vertices, which is an integer.
Lemma 2: For arbitrary $n$ and $k$, define the vertex indices as $\lfloor i \cdot n / k \rfloor$ for $i=0,\dots,k-1$. Then the resulting set is uniform. This holds because for each $m$, the count of blue vertices in $m$ consecutive positions is either $\lfloor mk/n \rfloor$ or $\lceil mk/n \rceil$.
Lemma 3: Any uniform set must have spacing between consecutive blue vertices either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$. This ensures uniqueness up to rotation. The hardest step is rigorously proving Lemma 3, because one must exclude all other configurations that might satisfy the uniformity condition.
The main theorem combines Lemmas 1–3: the constructions yield a uniform set, and any uniform set is congruent to this construction under rotation.
Solution
For $n=12$, $k=5$, define blue vertices at indices $0,2,5,7,10$. This choice follows the formula $\lfloor i \cdot 12 / 5 \rfloor$ for $i=0,1,2,3,4$. Checking consecutive sequences of length $m$ confirms the uniformity condition: each set of $m$ consecutive vertices contains either $\lfloor 5m/12 \rfloor$ or $\lceil 5m/12 \rceil$ blue vertices.
For $n=17$, $k=7$, define blue vertices at indices $0,2,4,6,9,11,13$. This follows $\lfloor i \cdot 17 / 7 \rfloor$ for $i=0,\dots,6$. Verifying consecutive sequences of length $m$ shows that each contains either $\lfloor 7m/17 \rfloor$ or $\lceil 7m/17 \rceil$ blue vertices.
For the general case $n$ divisible by $k$, place blue vertices at positions $0, n/k, 2n/k, \dots, (k-1)n/k$. Any consecutive segment of length $m$ then contains exactly $mk/n$ blue vertices. Since $k$ divides $n$, $mk/n$ is always an integer, and differences between segments are zero. Hence, the set is uniform. To prove uniqueness, assume there is another uniform set. Let $d_i$ be the distances between consecutive blue vertices. The sum $\sum d_i = n$ and the uniformity condition requires $d_i$ all equal to $n/k$, otherwise some consecutive segment would differ by more than one blue vertex. Therefore, the set is unique up to rotation.
For arbitrary $n$ and $k$, define the blue vertex indices as $b_i = \lfloor i n / k \rfloor$ for $i=0,\dots,k-1$. Consider any consecutive segment of length $m$. Let $i_1$ and $i_2$ be the smallest and largest indices of blue vertices within the segment. The number of blue vertices in the segment is $i_2 - i_1 + 1$. Since $b_i$ approximates $i \cdot n / k$, this number equals either $\lfloor mk/n \rfloor$ or $\lceil mk/n \rceil$, satisfying the uniformity condition. For uniqueness, any other uniform set would need the same distances between consecutive blue vertices, up to a difference of one. Therefore, any uniform set is equivalent to this construction under rotation.
This completes the proof.
∎
Verification of Key Steps
For $n$ divisible by $k$, suppose consecutive blue vertices had unequal spacing. If one distance is larger than $n/k$ and another smaller, then a segment of length equal to the larger distance would contain fewer blue vertices than a segment of length equal to the smaller distance plus the intermediate vertices, violating uniformity. This confirms that all spacings must be equal.
For arbitrary $n$ and $k$, consider $n=17$, $k=7$ and a segment of length $5$. The proposed construction gives blue counts $2$ or $3$. If any blue vertex were shifted one position, some segment would contain $4$ or $1$ blue vertices, violating uniformity. This confirms the necessity of the floor/ceiling formula.
Testing these concrete examples rules out counterexamples and confirms that the constructions achieve the intended uniformity.
Alternative Approaches
An alternative method uses modular arithmetic: identify vertices with integers modulo $n$, and define the uniform set as those integers $x$ satisfying $k x \bmod n < k$. This produces the same distribution of blue vertices. While elegant and concise, this approach obscures the intuitive spacing interpretation. The floor-based method is preferable for its constructive clarity, direct verification of the uniformity condition, and ease of generating explicit examples.