2002 USA TST Problems/Problem 4

Revision as of 15: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