2002 USA TST Problems/Problem 4
From AoPSWiki
Problem
(David Savitt)
Let 
be a positive integer and let 
be a set of 
elements. Let 
be a function from the set of two-element subsets of to 
. Assume that for any elements 
of , one of 
is equal to the sum of the other two. Show that there exist 
in such that 
are all equal to 0.
Solution
We will prove that for any integer 
, there exists a set 
of cardinality at least 
such that for any 
, 
.
Our base case is 
. Now, asume that there exists such an 
(
). We will consider two elements 
of to be related if 
, or if 
is divisible by 
. Any two elements of which are related to some 
must also be related to each other; similarly, any two elements of which are not related to 
must be related to each other. Thus the relation partitions into two equivalence classes; we pick the larger one, which must have at least elements, to be 
.
Thus there must exist an 
with at least three elements 
such that 
. But the only possible value of 
which is divisible by 
is zero.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
