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?
No comments:
Post a Comment