## Problem A3

Find the smallest number $\mathrm{n}$ such that given any $\mathrm{n}$ distinct numbers from $\{1,2,3, \ldots, 999\}$, one can choose four different numbers $\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}$ such that $\mathrm{a}+2 \mathrm{~b}+3 \mathrm{c}=\mathrm{d}$.


## Solution

Answer: $\mathrm{n}=835$.

Consider the set $S=\{166,167, \ldots, 999\}$. The smallest possible value for $a+2 b+3 c$, for distinct $\mathrm{a}, \mathrm{b}, \mathrm{c}$ in $\mathrm{S}$ is $168+2.167+3.166=1000$. So we cannot find distinct $\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}$ in $\mathrm{S}$ with $a+2 b+3 c=d$. So the smallest $n>834$.

Now suppose $\mathrm{S}$ is any subset of 835 elements which satisfies the condition. Take it elements to be $\mathrm{m}=\mathrm{a}_{1}<\mathrm{a}_{2}<\ldots<\mathrm{a}_{835}=\mathrm{M}$. Obviously $\mathrm{M} \geq \mathrm{m}+834 \geq 835$, so $-3 \mathrm{~m} \geq 3.834-3 \mathrm{M}$ and hence $M-3 \mathrm{~m} \geq 2502-2 \mathrm{M} \geq 2502-2.999=504$. Put $\mathrm{k}=\mathrm{M}-3 \mathrm{~m}$.

There are at least 167 disjoint pairs (a,b) of numbers taken from $\{1,2, \ldots, 999\}$ with $a+2 b=$ $\mathrm{k}$, namely

```
(k- - 2, 1)
(k-4, 2)

```

![](https://cdn.mathpix.com/cropped/2024_05_09_1d234a78607cd781abe6g-33.jpg?height=46&width=206&top_left_y=2210&top_left_x=248)

```

```

![](https://cdn.mathpix.com/cropped/2024_05_09_1d234a78607cd781abe6g-33.jpg?height=40&width=55&top_left_y=2287&top_left_x=248)

```
(k-334, 167) - note that in the extreme case k = 504 this is (170, 167)
```

At least one number from each pair must either (1) be $\mathrm{M}$ or $\mathrm{m}$ or (2) not belong to $\mathrm{S}$ - or otherwise we would have $a+2 b+3 m=M$ for distinct elements $a, b, m$ and $M$ in $S$. None of the numbers can be $M$ and at most one of them can be $m$, so we have at least 166 numbers which are not in S. That means S contains at most $999-166=833$ numbers. Contradiction.

So $\mathrm{S}$ cannot have 835 elements. Nor can it have more than 835 elements (or we just take a subset of 835 elements, which must also satisfy the condition, and get a contradiction).

