Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2002 USA TST Problems/Problem 4"

 
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> \displaystyle 2^{n-k} + 1 </math> such that for any <math> a, b \in S_k </math>, <math> 2^k \mid f(\{a,b\}) </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> \displaystyle S_0 = S </math>.  Now, asume that there exists such an <math> \displaystyle S_{k-1} </math> (<math>1 \le k \le n</math>).  We will consider two elements <math> \displaystyle a, b </math> of <math> \displaystyle S_{k-1} </math> to be ''related'' if <math> \displaystyle a=b </math>, or if <math> \displaystyle f(\{a,b\}) </math> is divisible by <math> \displaystyle 2^k </math>.  Any two elements of <math> \displaystyle 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> \displaystyle S_{k-1} </math> which are not related to <math> \displaystyle a </math> must be related to each other.  Thus the relation partitions <math> \displaystyle S_{k-1} </math> into two [[equivalence class]]es; we pick the larger one, which must have at least <math> \displaystyle 2^{n-k} + 1 </math> elements, to be <math> \displaystyle S_k </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> \displaystyle S_{n-1} </math> with at least three elements <math> \displaystyle 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> \displaystyle {} f(\{x,y\}) </math> which is divisible by <math> \displaystyle 2^{k-1} </math> is zero.
+
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 14:34, 7 March 2010

Problem

(David Savitt) Let $\displaystyle n$ be a positive integer and let $\displaystyle S$ be a set of $\displaystyle 2^n+1$ elements. Let $\displaystyle f$ be a function from the set of two-element subsets of $\displaystyle S$ to $\{0, \dots, 2^{n-1}-1\}$. Assume that for any elements $\displaystyle x, y, z$ of $\displaystyle S$, one of $\displaystyle f(\{x,y\}), f(\{y,z\}), f(\{z, x\})$ is equal to the sum of the other two. Show that there exist $\displaystyle a, b, c$ in $\displaystyle S$ such that $\displaystyle f(\{a,b\}), f(\{b,c\}), f(\{c,a\})$ are all equal to 0.

Solution

We will prove that for any integer $0 \le k \le n-1$, there exists a set $S_k \subseteq S$ of cardinality at least $2^{n-k} + 1$ such that for any $a, b \in S_k$, $2^k \mid f(\{a,b\})$.

Our base case is $S_0 = S$. Now, asume that there exists such an $S_{k-1}$ ($1 \le k \le n$). We will consider two elements $a, b$ of $S_{k-1}$ to be related if $a=b$, or if $f(\{a,b\})$ is divisible by $2^k$. Any two elements of $S_{k-1}$ which are related to some $a \in S_{k-1}$ must also be related to each other; similarly, any two elements of $S_{k-1}$ which are not related to $a$ must be related to each other. Thus the relation partitions $S_{k-1}$ into two equivalence classes; we pick the larger one, which must have at least $2^{n-k} + 1$ elements, to be $S_k$.

Thus there must exist an $S_{n-1}$ with at least three elements $a,b,c$ such that $2^{n-1} \mid f(\{a,b\}), f(\{b,c\}), f(\{c,a\})$. But the only possible value of ${} f(\{x,y\})$ which is divisible by $2^{n-1}$ is zero.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_USA_TST_Problems/Problem_4&oldid=33833"