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