Kvant Math Problem 436
We are asked to partition all pairwise sums of two sets of ten numbers each into ten groups of ten, each with the same total.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m49s
Source on kvant.digital
Problem
Given 20 numbers $a_1$, $a_2$, $\ldots$, $a_{10}$, $b_1$, $b_2$, $\ldots$, $b_{10}$. Prove that the set of 100 numbers (not necessarily distinct) $a_1+b_1$, $a_1+b_2$, $\ldots$, $a_{10}+b_{10}$ can be partitioned into 10 subsets, each containing 10 numbers, so that the sum of the numbers in each subset is the same.
S. T. Berkolayko
Exploration
We are asked to partition all pairwise sums of two sets of ten numbers each into ten groups of ten, each with the same total. A natural first experiment is to try very small sets to see if any simple pattern emerges. Suppose $a_1, \dots, a_{10}$ are all equal and $b_1, \dots, b_{10}$ are also all equal. Then every sum is the same, and any grouping trivially works. If the $a_i$ and $b_j$ are distinct, one can try $a_i = i$ and $b_j = j$; then the $100$ sums are $i+j$ for $1 \le i,j \le 10$. Arranging them in a $10 \times 10$ table with rows indexed by $a_i$ and columns by $b_j$, the sum of the $i$-th row is $\sum_{j=1}^{10} (i+j)$, which increases with $i$, and the sum of the $j$-th column is $\sum_{i=1}^{10} (i+j)$, which increases with $j$. However, if we take diagonals modulo $10$, the sums seem to stabilize. This suggests that a combinatorial design, like taking one element from each $a_i$ and each $b_j$ in a cyclic pattern, could produce equal sums.
The crucial difficulty is finding a partition where each subset contains exactly one element from each "row" and each "column" of the $10 \times 10$ array of sums. This resembles constructing a Latin square and summing along diagonals.
Problem Understanding
The problem asks to prove the existence of a partition of the $100$ sums $a_i + b_j$ into $10$ subsets of $10$ numbers each, all with the same sum. This is a Type D problem, an existence statement. The core difficulty lies in ensuring that each subset sums to the same total regardless of the specific values of the $a_i$ and $b_j$. The intuition is that arranging the sums in a $10 \times 10$ table and selecting elements along diagonals modulo $10$ balances the contribution of each $a_i$ and each $b_j$ across all subsets.
Proof Architecture
Lemma 1: Let the sums $a_i + b_j$ be arranged in a $10 \times 10$ matrix with rows $i$ and columns $j$. Each row sum equals $10 a_i + \sum_{j=1}^{10} b_j$, and each column sum equals $10 b_j + \sum_{i=1}^{10} a_i$. This follows by factoring the sums in each row and column.
Lemma 2: Define subsets $S_k = { a_i + b_{(i+k-1 \bmod 10)+1} : i = 1, \dots, 10 }$ for $k=0,\dots,9$. Each subset contains exactly one element from each row and column. This holds because the map $i \mapsto (i+k-1 \bmod 10)+1$ is a bijection of ${1,\dots,10}$ for each $k$.
Lemma 3: The sum of the elements in each subset $S_k$ is independent of $k$. This holds because each subset contains each $a_i$ exactly once and each $b_j$ exactly once, so the total sum is $\sum_{i=1}^{10} a_i + \sum_{j=1}^{10} b_j$.
The hardest step is verifying that the subsets are disjoint and cover all $100$ sums without repetition.
Solution
Arrange the $100$ numbers $a_i + b_j$ in a $10 \times 10$ matrix $M$ where the $(i,j)$-th entry is $a_i + b_j$. Construct $10$ subsets $S_0, S_1, \dots, S_9$ as follows: for each $k = 0, 1, \dots, 9$, let
$$S_k = { a_i + b_{(i+k-1 \bmod 10)+1} : i = 1, \dots, 10 }.$$
Each subset $S_k$ contains exactly one element from each row and each column because the function $i \mapsto (i+k-1 \bmod 10)+1$ permutes ${1,2,\dots,10}$. Therefore the subsets are disjoint and together contain all $100$ numbers.
The sum of the elements in $S_k$ is
$$\sum_{i=1}^{10} \left(a_i + b_{(i+k-1 \bmod 10)+1}\right) = \sum_{i=1}^{10} a_i + \sum_{i=1}^{10} b_i,$$
since each $b_j$ appears exactly once in the sum. This sum is independent of $k$. Thus the $100$ numbers can be partitioned into $10$ subsets of $10$ numbers each, all having the same sum.
This completes the proof.
∎
Verification of Key Steps
Step one is confirming that the mapping $i \mapsto (i+k-1 \bmod 10)+1$ is indeed a bijection for each $k$. If two distinct $i_1$ and $i_2$ were mapped to the same column, we would have $(i_1+k-1 \bmod 10) = (i_2+k-1 \bmod 10)$, which implies $i_1 \equiv i_2 \pmod{10}$, contradicting $1 \le i_1, i_2 \le 10$. Step two is ensuring that each $b_j$ appears exactly once in each subset sum. Since the map is a permutation of ${1,\dots,10}$, every column index occurs exactly once. No element is counted twice, and all elements appear exactly once in some subset.
Alternative Approaches
One could approach the problem using graph-theoretic terminology by considering a complete bipartite graph $K_{10,10}$ with edges weighted by $a_i + b_j$. The task then becomes partitioning the edges into $10$ perfect matchings, each with the same total weight. This perspective generalizes to arbitrary $n \times n$ matrices. The main approach is preferable because it explicitly constructs the required subsets using simple arithmetic, avoiding abstraction and directly demonstrating the equal sums.