
C2. Fix integers $n \geq k \geq 2$. We call a collection of integral valued coins $n$-diverse if no value occurs in it more than $n$ times. Given such a collection, a number $S$ is $n$-reachable if that collection contains $n$ coins whose sum of values equals $S$. Find the least positive integer $D$ such that for any $n$-diverse collection of $D$ coins there are at least $k$ numbers that are $n$-reachable.

Bulgaria, Alexandar Ivanov


Solution. The required number is $D=n+k-1$. We first show that $n+k-2$ coins are not enough. Indeed, if a collection consists of $n$ coins of value 1 and $k-2(<n)$ coins of value 2 , then all $n$-reachable numbers have the form $x+2 y=n+y$ (since $x+y=n$ ), where $y \in\{0,1, \ldots, k-2\}$. Thus, there are only $k-1$ such numbers.

To prove that the number $D=n+k-1$ suffices, we make use of the following lemma. In the sequel, we denote a coin and its value by the same letter.

Lemma. In any $n$-diverse collection of $D$ coins one may find $D-n$ disjoint pairs, each consisting of two coins of distinct values.

Proof. Enumerate the coins $c_{1} \leq c_{2} \leq \cdots \leq c_{D}$ in a non-decreasing order according to their values. Then the desired pairs are $\left(c_{1}, c_{n+1}\right),\left(c_{2}, c_{n+2}\right), \ldots,\left(c_{D-n}, c_{D}\right)$ : they are clearly disjoint, and the equality $c_{i}=c_{n+i}$ would yield $c_{i}=c_{i+1}=\cdots=c_{i+n}$ which contradicts $n$-diversity of the collection.

Now, given any $n$-diverse collection of $D=n+k-1$ coins, apply the lemma to find pairs $\left(a_{1}, b_{1}\right),\left(a_{2}, b_{2}\right), \ldots,\left(a_{k-1}, b_{k-1}\right)$; the coins in each pair are listed so that $a_{i}<b_{i}$ for every $i=1,2, \ldots, k-1$. Let $c_{1}, \ldots, c_{n-k+1}$ be the other coins in the collection.

Set $S=c_{1}+c_{2}+\cdots+c_{n-k+1}$. Then each of the $k$ sums

$$
S_{m}=S+\sum_{i=1}^{m} a_{i}+\sum_{i=m+1}^{k-1} b_{i}, \quad m=0,1, \ldots, k-1
$$

is clearly $n$-reachable. Moreover, the inequalities imposed on the pairs yield $S_{0}<S_{1}<\cdots<$ $S_{k-1}$, so we have found $k$ distinct $n$-reachable numbers, as required.

Remark. One may notice that the ideas in the solution above are close to those used in the classical proof of the celebrated Erdős-Ginzburg-Ziv theorem.
