Fix integers $n\ge k\ge 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. Proposed by Alexandar Ivanov, Bulgaria.
Problem
Source: 2018 RMM Shortlist C2
Tags: combinatorics
21.02.2019 17:39
We claim that the answer is $n+k-1$. To show an example of collection of $n+k-2$ coins: take $\underbrace{1,1,\dotsc ,1}_{n} ,\underbrace{2,2,\dotsc ,2}_{k-2}$. A number $m$ is $n$-reachable only if it can be written of the form $x+2y$ where $x,y$ are non-negative integers that $x+y=n$ and $y\leqslant k-2$. Clearly, there're only $k-1$ such numbers. Also, it's clear that the collection is $n$-diverse. Now, for any collection of $n+k-1$ coins that is $n$-diverse, let the values of all the coins are $a_1\leqslant a_2\leqslant \cdots \leqslant a_{n+k-1}$. Let $S_i=a_i+a_{i+1}+\cdots +a_{n+i-1}$ for each $i=1,2,\dotsc ,k$. Clearly, all $S_i$s are $n$-reachable. So, we only need to show that $S_1<S_2<\cdots <S_k$. In particular, $S_i<S_{i+1}$ for all $i=1,2,\dotsc ,k-1$. Indeed, we have $$S_i=a_i+\sum_{j=i+1}^{n+i-1}{a_j}\leqslant a_{n+i}+\sum_{j=i+1}^{n+i-1}{a_j} =S_{i+1}.$$Note that if the equality occurs, then $a_i=a_{n+i}\implies a_i=a_{i+1}=\cdots =a_{n+i}$. This contradicts the $n$-diverse property.
27.03.2020 06:38
We claim the smallest such value of $D$ is $\boxed{n+k-1}$. Indeed, note that the configuration with $n$ coins worth $0$ and $k-2$ coins worth $0$ produces only $k-1$ different values (it produces all the integers from $0$ to $k-2$). Thus, we must have $D\le n+k-1$. We now show that $D=n+k-1$ is indeed $n$-diverse. Suppose the coins have values \[x_1\le x_2\le\cdots\le x_{n+k-1}.\]By taking the complement, it suffices to show that there are at least $n$ different values that can be made from collections of $k-1$ coins. Consider the true expression \begin{align*} \mathcal{C}_a:\,\,\,\,&(x_1+\cdots+x_{a-1})+x_a+(x_{n+a+1}+\cdots+x_{n+k-1}) \\ \le& (x_1+\cdots+x_{a-1})+x_{a+1}+(x_{n+a+1}+\cdots+x_{n+k-1}) \\ \le& (x_1+\cdots+x_{a-1})+x_{a+2}+(x_{n+a+1}+\cdots+x_{n+k-1}) \\ \vdots& \\ \le& (x_1+\cdots+x_{a-1})+x_{n+a}+(x_{n+a+1}+\cdots+x_{n+k-1}). \end{align*}We see that one of the inequality signs in \[x_a\le x_{a+1}\le\cdots\le x_{n+a}\]is strict, so one of the inequality signs in $\mathcal{C}_a$ is strict. We also have the true expression \[\mathcal{D}:\,\,\,\,\mathcal{C}_{k-1}\le\mathcal{C}_{k-2}\le\cdots\le\mathcal{C}_1.\]Since there is a strict inequality in each individual $\mathcal{C}_a$, the expression $\mathcal{D}$ has at least $k-1$ strict inequalities. Thus, it has at least $k$ distinct values, so we're done, as we have at least $k$ values made from groups of $k-1$.
23.05.2020 04:03
We claim the answer is $n+k-1$. We can get $n+k-2$ coins by taking $n$ ones and $k-2$ twos. Then we get a distinct value based on number of twos we choose, so we can have at most $k-1$ different values. Suppose we have $n+k-1$ coins, call them $x_1\le \cdots \le x_{n+k-1}$. Then we can take $x_i+x_{i+1}+\cdots+x_{i+n-1}$ for each $i=1,\ldots,k$, and these clearly give a increasing sequence of values. In fact, we claim further that this sequence is strictly increasing; this finishes as we will have $k$ distinct possible sums. If we ever had two consecutive sums equal, say $x_i+\cdots+x_{i+n-1} = x_{i+1}+\cdots+x_{i+n}$, then $x_i=\cdots=x_{i+n}$, contradicting $n$-diversity.
20.09.2020 15:41
We claim that $D=n+k-1$. Note that a suitable counterexample for $D=n+k-2$ is as follows : Take $\{ \underbrace {1,1,\dots, 1}_{n} , \underbrace {2,2,\dots, 2}_{k-2} \}$. It can be easily checked that the only reachable numbers are from $\{n,n+1,\dots, n+k-2\}$ which results in a contradiction. We now claim that $D=n+k+1$ works. Order the coins according to their value as $c_1\leq c_2\leq \dots \leq c_{n+k+1}$. Note that $c_i\neq c_{n+i}$ for all $1\leq i \leq k-1$. Hence we can find atleast $k-1$ pairwise distinct values $(a_i,b_i)_{i=1}^{k-1}$. Let $S$ denote the sum of the other $n-k+1$ elements. We now list out the $k$ possible sums as follows. Start with $S_0= S+\sum_{i=1}^{k-1} b_i$. For the $i$-th sum , we will change $b_i\mapsto a_i$. Its obvious that the $k$ sums hence obtained are distinct and we are done. $\blacksquare$