Problem

Source: 2018 RMM Shortlist C2

Tags: combinatorics



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.