## Wednesday, February 8, 2006

### Pick As Many As You Can. Topic: Sets/Pigeonhole Principle. Level: AIME/Olympiad.

Problem: (WOOT Test 6 - #1) Let $A$ be a subset of $\{1, 2, \ldots , 2006\}$, such that for all $x, y \in A$ with $x \neq y$, the sum $x + y$ is not divisible by $1003$. Find, with proof, the maximum value of $|A|$ (the number of elements in $A$).

Solution: We claim that the maximum $|A|$ is $1003$.

Suppose there are at least $1004$ elements in $A$. Then for some $x \in \{1,2, \ldots, 2006 \}$ we have both $x \in A$ and $2006-x \in A$ by the Pigeonhole Principle. But the sum of these is $2006$, which is divisible by $1003$. Hence $|A| < 1004$.

Now we show that a set with $|A| = 1003$ exists. Consider $\{1,2,\ldots,501, 1003, 1004, \ldots, 1504 \}$. Since all the elements are $0,1,\ldots, 501 \pmod{1003}$ (and there is only one element divisible by $1003$), we clearly cannot have two sum to $0 \pmod{1003}$. QED.

--------------------

Comment: Didn't choose to do this problem on the test; it was pretty easy though. A good exercise in working with sets and the Pigeonhole Principle.

--------------------

Practice Problem: What would be the maximum $|A|$ if $x-y$ for any $x, y \in A$ is not divisible by $1003$ either?