Maths Olympiad Prep

Library / /17 of 42

Combinatorics Difficulty 5.8 AIME, harder Prove it Romania

A natural number n5n \ge 5 will be called *special* if, no matter how we choose five distinct numbers from 1,2,3,,n1, 2, 3, \ldots, n, we find among them four distinct numbers a,b,c,da, b, c, d so that a+b=c+da + b = c + d.

a) Prove that n=6n = 6 is special.

b) Find all the special numbers.

Solution

a) Since 1+6=2+5=3+41+6 = 2+5 = 3+4, every set of 55 numbers from 1,2,3,4,5,61, 2, 3, 4, 5, 6 contains 44 distinct numbers a,b,c,da, b, c, d so that a+b=c+d=7a + b = c + d = 7.

b) Indeed, no 44 numbers out of 1,2,3,5,81, 2, 3, 5, 8 provide equal sums: if we do not choose 88, then 5+a>b+c5+a > b+c, for every a,b,c{1,2,3}a, b, c \in \{1, 2, 3\}, and if we choose 88, then 8+a>b+c8+a > b+c, for every a,b,c{1,2,3,5}a, b, c \in \{1, 2, 3, 5\}.
The number n=7n = 7 is special. Indeed:
* if we do not choose 77, 44, or 11, then the argument from a) applies to the sums 1+6=2+5=3+41+6=2+5=3+4, 1+7=2+6=3+51+7=2+6=3+5, respectively 2+7=3+6=4+52+7=3+6=4+5;
* if we choose 11, 44, or 77 and two of the numbers 2,3,5,62, 3, 5, 6, then we get the equal sums 1+4=3+21+4=3+2, 1+5=2+41+5=2+4, 1+7=2+61+7=2+6, 1+7=3+51+7=3+5, 3+7=4+63+7=4+6, or 4+7=5+64+7=5+6.
Since 55 is, obviously, special, the special numbers are 55, 66 and 77.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.