2002 USA TST Problems/Problem 4

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

Page

Toolbox

Search

2002 USA TST Problems/Problem 4

Problem

Solution

Resources