IMO 1996 SL C3

Origin: USA | Category: Combinatorics

Problem

Let $k, m, n$ be integers such that $1 < n \leq m-1 \leq k$. Determine the maximum size of a subset $S$ of the set ${1, 2, 3, \ldots, k}$ such that no $n$ distinct elements of $S$ add up to $m$.

Solution

Denote the required maximum size by $M_k(m, n)$. If $m < \frac{n(n+1)}{2}$, then trivially $M_k(m, n) = k$, so from now on we assume that $m \geq \frac{n(n+1)}{2}$.

First we give a lower bound for $M_k(m, n)$. Let $r = r_k(m, n)$ be the largest integer such that

$$r + (r + 1) + \cdots + (r + n - 1) \leq m.$$

This is equivalent to

$$n r + \frac{n(n-1)}{2} \leq m,$$

so

$$r = \left\lfloor \frac{m - \frac{n(n-1)}{2}}{n} \right\rfloor.$$

Clearly no $n$ elements from ${r+1, r+2, \ldots, k}$ add up to $m$, so

$$M_k(m, n) \geq k - r_k(m, n) = k - \left\lfloor \frac{m - \frac{n(n-1)}{2}}{n} \right\rfloor. \tag{1}$$

We claim that $M_k(m, n)$ is actually equal to $k - r_k(m, n)$. To show this, we shall prove by induction on $n$ that if no $n$ elements of a set $S \subseteq {1, 2, \ldots, k}$ add up to $m$, then

$$|S| \leq k - r_k(m, n).$$

For $n = 2$ the claim is true, because then for each $i = 1, \ldots, r_k(m, 2) = \lfloor \frac{m-1}{2} \rfloor$, at least one of $i$ and $m-i$ must be excluded from $S$.

Now let us assume that $n > 2$ and that the result holds for $n-1$. Suppose that $S \subseteq {1, 2, \ldots, k}$ does not contain $n$ distinct elements with sum $m$, and let $x$ be the smallest element of $S$. We may assume that $x \leq r_k(m, n)$, because otherwise the statement is clear. Consider the set

$$S' = {y - x \mid y \in S, y \neq x}.$$

Then $S'$ is a subset of ${1, 2, \ldots, k-x}$ no $n-1$ elements of which have sum $m - n x$. Also, it is easily checked that

$$n-1 \leq m - n x - 1 \leq k - x,$$

so we may apply the induction hypothesis, which yields

$$|S| \leq 1 + (k - x - r_k(m - n x, n-1)) = k - \left\lfloor \frac{m - n x - \frac{(n-1)(n-2)}{2}}{n-1} \right\rfloor. \tag{2}$$

On the other hand,

$$\left\lfloor \frac{m - n x - \frac{(n-1)(n-2)}{2}}{n-1} \right\rfloor - r_k(m, n) = \frac{m - n x - \frac{(n-1)(n-2)}{2}}{n-1} - \frac{m - \frac{n(n-1)}{2}}{n} \geq 0$$

because $x \leq r_k(m, n)$. Hence (2) implies $|S| \leq k - r_k(m, n)$ as claimed.