Tuesday, April 11, 2006

Every Difference Counts. Topic: Algebra/Sequences & Series/Sets. Level: Olympiad.

Problem: (TJ USAMO) Let $x_1, x_2, x_3, \ldots$ be an infinite sequence of positive integers such that

$x_1 = 1$

$x_i < x_{i+1}$ for all positive integers $i$

$x_{n+1} \le 2n$ for each $n \ge 1$.

Show that for any integer $k$, there exist positive integers $i$ and $j$ such that $k = x_i-x_j$.

Solution: If we show the result for positive $k$, we can simply switch $i$ and $j$ to obtain the result for negative $k$. The case $k = 0$ is simply any $i = j$.

We claim that, for any positive integer $k$, there exist positive integers $i, j \le k+1$ such that $k = x_i-x_j$. Consider the set $S_k = \{1,2,\ldots,2k\}$. The given conditions require that $x_1, x_2, \ldots, x_{k+1}$ be distinct elements of $S_k$.

We partition $S_k$ into $k$ different sets, as follows:

$\{1,k+1\}$; $\{2,k+2\}$; $\ldots$; $\{k,2k\}$.

Since we have $k+1$ different elements and there are only $k$ sets in the partition, by the Pigeonhole Principle two elements must be in the same set. Let $x_i$ be the larger of the two and $x_j$ be the smaller. Then we clearly have $k = x_i-x_j$, as claimed.

$k$ was arbitrarily chosen, so we know that it holds for all positive integers $k$, completing the proof. QED.

--------------------

Comment: An interesting problem and good exercise in the Pigeonhole Principle. The application was subtle, yet upon seeing the solution very clear. Some hints may have been $n+1$ and $2n$ and the fact that we are looking for differences.

--------------------

Practice Problem: (TJ USAMO) $S$ is a set of eleven numbers are chosen from the set $\{1, 2, . . ., 99, 100 \}$. Show that two disjoint, non-empty subsets of $S$ have the same sum.