Competition problem — Combinatorics

Library / /18 of 45

Combinatorics Difficulty 5.3 AIME, harder Prove it Romania

Let $S$ be a subset with 673 elements of the set $\{1, 2, \dots, 2010\}$ . Prove that one can find two distinct elements of $S$ , say $a$ and $b$ such that $6$ divides $a + b$ .

Solution

Consider the following sets, each containing 335 elements
$\begin{align*} A &= \{6, 12, \dots, 2010\}, & B &= \{3, 9, 15, \dots, 2007\}, \\ C &= \{1, 7, 13, \dots, 2005\}, & D &= \{2, 8, 14, \dots, 2006\}, \\ E &= \{4, 10, 16, \dots, 2008\}, & F &= \{5, 11, 17, \dots, 2009\}. \end{align*}$
If $S$ contains two elements from $A$ or two elements from $B$ , their sum is divisible by $6$ . If not, the remaining $4$ sets contain at least $673 - 2 = 671$ elements from $S$ .

Consider the sets $C \cup F$ and $D \cup E$ , each containing $670$ elements. One of the intersections of $S$ with these, say $C \cup F$ , contains at least $336$ elements. Thus $S \cap C$ and $S \cap F$ contain each at least one element. Their sum is a multiple of $6$ , which is what was to be proven.

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.