2002 USA TST Problems/Problem 4
(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.
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.