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.