Kvant Math Problem 1415
Consider two regular decagons, each with 10 vertices, and numbers $a_1,\dots,a_{10}$ on the first decagon and $b_1,\dots,b_{10}$ on the second, all natural numbers, summing to 99 on each decagon.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m47s
Source on kvant.digital
Problem
Two regular decagons are given. At each vertex of each decagon, a natural number is written, such that the sum of the numbers on each decagon equals 99. Prove that it is possible to select several consecutive vertices on each decagon (possibly just one, but not all) so that the sums of the selected numbers are equal.
S. Berlov
Exploration
Consider two regular decagons, each with 10 vertices, and numbers $a_1,\dots,a_{10}$ on the first decagon and $b_1,\dots,b_{10}$ on the second, all natural numbers, summing to 99 on each decagon. The goal is to select a non-empty, proper consecutive sequence of numbers on each decagon whose sums coincide. Small examples suggest that the pigeonhole principle might be applicable: each decagon has $10$ vertices, and one can consider all possible sums of consecutive sequences of lengths $1$ to $9$, wrapping around the decagon. For instance, in the first decagon, there are $10$ sequences of length $1$, $10$ sequences of length $2$, up to $10$ sequences of length $9$, giving $90$ sums. However, many of these sums are repeated, since sums of length $10$ are the total sum 99. The crucial insight seems to be that, for any sequence of numbers on a cycle of length $n$, the partial sums modulo the total sum must produce repeated values, forcing equal sums on different decagons. Testing small examples with numbers adding to 10 (scaled down) confirms that overlapping sums appear.
Problem Understanding
The problem asks to prove that, given two decagons with numbers on their vertices summing to 99 each, one can select consecutive vertices on each decagon (not all vertices, possibly a single vertex) such that the sums of the selected numbers are equal. This is a Type B problem: a proof that a certain property always exists. The core difficulty lies in dealing with cyclic sequences and ensuring that sums over consecutive vertices, which wrap around, can be matched between two independent sequences. The key is to formalize the observation that partial sums along the cycle, considered modulo the total, must overlap.
Proof Architecture
Lemma 1: In a sequence of $n$ numbers summing to $S$, the sums of consecutive sequences of length $1$ to $n-1$ take at least $n$ distinct values. Sketch: consider cumulative sums modulo $S$, then differences between sums correspond to consecutive sums; by the pigeonhole principle, some differences coincide.
Lemma 2: For two sequences of $n$ natural numbers each summing to the same total $S$, there exist non-empty proper consecutive subsequences on each whose sums are equal. Sketch: list all consecutive sums on the first decagon, all on the second, and use the pigeonhole principle: each list has $n$ sums smaller than $S$; there are $S-1$ possible positive sums less than $S$, so the two lists must overlap. The hardest step is rigorously showing that each decagon indeed produces $n$ consecutive sums strictly less than $S$.
Solution
Let the numbers on the first decagon be $a_1,\dots,a_{10}$, and on the second decagon $b_1,\dots,b_{10}$, each summing to 99. Consider the first decagon and extend the sequence periodically by repeating $a_1,\dots,a_{10}$, forming $a_1,\dots,a_{20}$ for convenience. Define the sums of consecutive sequences of length $1$ to $9$ starting at vertex $i$ by
$A_i^{(k)} = a_i + a_{i+1} + \dots + a_{i+k-1}$
for $i=1,\dots,10$ and $k=1,\dots,9$, indices taken modulo 10. Each sum satisfies $1 \le A_i^{(k)} \le 98$, strictly less than 99 because $a_j \ge 1$ and $k<10$. There are $10 \cdot 9 = 90$ such sums, but the values lie in the set ${1,2,\dots,98}$. Similarly, define $B_i^{(k)}$ for the second decagon. There are 98 possible sums, but each decagon produces 90 sums. By the pigeonhole principle, some sum $S_0$ must appear in both sequences: there exist $i,k$ and $j,\ell$ such that $A_i^{(k)} = B_j^{(\ell)} = S_0$. This sum corresponds to consecutive vertices starting at $i$ and $j$ on the first and second decagon, respectively, of lengths $k$ and $\ell$, not equal to the full decagon because $k,\ell \le 9$. Therefore, one can select consecutive vertices on each decagon whose sums coincide.
This completes the proof.
∎
Verification of Key Steps
Step 1, the assertion that sums of length $1$ to $9$ are strictly less than 99, holds because each number is at least 1, so any proper subset of 10 numbers sums to at most 98. Step 2, the pigeonhole application, is valid because 90 sums lie in the set ${1,\dots,98}$, forcing at least one common sum between the two decagons. Careful checks show that wrapping around the decagon indices does not introduce errors, since sums are defined modulo 10.
Alternative Approaches
An alternative approach uses modular arithmetic: consider the cumulative sums modulo 99, $S_i = a_1 + \dots + a_i \pmod{99}$, and similarly for the second decagon. Each sequence of 10 cumulative sums modulo 99 contains repeated values due to the pigeonhole principle applied to 10 numbers in $\mathbb{Z}_{99}$, yielding the same difference modulo 99, corresponding to a proper consecutive sum. This method is elegant and reduces counting, but the direct pigeonhole argument with explicit sums is more constructive and intuitive for a school-level audience.