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

2002 USA TST Problems/Problem 4

Revision as of 14:10, 4 April 2007 by Boy Soprano II (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 $\displaystyle 2^{n-k} + 1$ such that for any $a, b \in S_k$, $2^k \mid f(\{a,b\})$.

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

Thus there must exist an $\displaystyle S_{n-1}$ with at least three elements $\displaystyle a,b,c$ such that $2^n-1 \mid f(\{a,b\}), f(\{b,c\}), f(\{c,a\})$. But the only possible value of $\displaystyle {} f(\{x,y\})$ which is divisible by $\displaystyle 2^{k-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=14359"