Find the smallest number n such that given any n distinct numbers from {1, 2, 3, ... , 999}, one can choose four different numbers a, b, c, d such that a + 2b + 3c = d.
Solution
Answer: n = 835.
Consider the set S = {166, 167, ... , 999}. The smallest possible value for a + 2b + 3c, for distinct a, b, c in S is 168 + 2.167 + 3.166 = 1000. So we cannot find distinct a, b, c, d in S with a + 2b + 3c = d. So the smallest n > 834.
Now suppose S is any subset of 835 elements which satisfies the condition. Take it elements to be m = a1 < a2 < ... < a835 = M. Obviously M ≥ m + 834 ≥ 835, so -3m ≥ 3.834 - 3M and hence M - 3m ≥ 2502 - 2M ≥ 2502 - 2.999 = 504. Put k = M - 3m.
There are at least 167 disjoint pairs (a, b) of numbers taken from {1, 2, ... , 999} with a + 2b = k, namely
(k - 2, 1) (k - 4, 2) (k - 6, 3) ... (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 M or m or (2) not belong to S - or otherwise we would have a + 2b + 3m = 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 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).
© John Scholes
jscholes@kalva.demon.co.uk
24 Oct 2002