Difference between revisions of "2002 USA TST Problems/Problem 4"
5849206328x (talk | contribs) m (→Solution) |
|||
Line 6: | Line 6: | ||
== Solution == | == Solution == | ||
− | We will prove that for any integer <math> 0 \le k \le n-1 </math>, there exists a set <math> S_k \subseteq S </math> of cardinality at least <math> | + | We will prove that for any integer <math> 0 \le k \le n-1 </math>, there exists a set <math> S_k \subseteq S </math> of cardinality at least <math>2^{n-k} + 1 </math> such that for any <math> a, b \in S_k </math>, <math> 2^k \mid f(\{a,b\}) </math>. |
− | Our base case is <math> | + | Our base case is <math>S_0 = S </math>. Now, asume that there exists such an <math>S_{k-1} </math> (<math>1 \le k \le n</math>). We will consider two elements <math>a, b </math> of <math>S_{k-1} </math> to be ''related'' if <math>a=b </math>, or if <math>f(\{a,b\}) </math> is divisible by <math>2^k </math>. Any two elements of <math>S_{k-1} </math> which are related to some <math> a \in S_{k-1} </math> must also be related to each other; similarly, any two elements of <math>S_{k-1} </math> which are not related to <math>a </math> must be related to each other. Thus the relation partitions <math>S_{k-1} </math> into two [[equivalence class]]es; we pick the larger one, which must have at least <math>2^{n-k} + 1 </math> elements, to be <math>S_k </math>. |
− | Thus there must exist an <math> | + | Thus there must exist an <math>S_{n-1} </math> with at least three elements <math>a,b,c </math> such that <math> 2^{n-1} \mid f(\{a,b\}), f(\{b,c\}), f(\{c,a\}) </math>. But the only possible value of <math>{} f(\{x,y\}) </math> which is divisible by <math>2^{n-1} </math> is zero. |
Latest revision as of 13:34, 7 March 2010
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.