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.