Assume that the set of all positive integers is decomposed into $r$ disjoint subsets $A_{1}, A_{2}, \cdots, A_{r}$ $A_{1} \cup A_{2} \cup \cdots \cup A_{r}= \mathbb{N}$. Prove that one of them, say $A_{i}$, has the following property: There exist a positive integer $m$ such that for any $k$ one can find numbers $a_{1}, \cdots, a_{k}$ in $A_{i}$ with $0 < a_{j+1}-a_{j} \le m \; (1\le j \le k-1)$.
Problem
Source:
Tags: induction
hxy09
02.05.2009 12:54
An easy induction on $ r$
kamil9876
09.12.2009 12:11
firstly, a bit of terminology: we will call such a sequence of integers a "k-chain, m arrow" Lemma: If a set $ S$ satisfies this property, and $ S = A \cup B$ with $ A$ and $ B$ disjoint, then at least one of these parts must satisfy the property. Proof: Suppose $ A$ does not satisfy the property(let's denote this property as P). Now to construct $ A$, we remove some elements from $ S$ and have the removed elements go to $ B$ and the remained elements stay in $ A$. So $ S$ does satisfy $ P$ for $ m = m_0$, but $ A$ does not. Therefore for at least some $ k = k_0$, $ A$ does not satisfy the property for $ m = m_o$. However in $ S$ there exists a $ k_o K$ chain $ m_o$ narrow for all $ K$. Hence we had to remove at least $ K$ elements from this chain(to eliminate the existence of any $ k_o$ chains). Hence these $ K$ removed elements form a $ K$ chain $ k_o m_o$ narrow in $ B$. But this argument works for all $ K$ and hence $ B$ satisfies $ P$ where $ m = k_om_o$ there. $ \blacksquare$ Now this lemma is in fact equivalent to the result since we can construct our partition in a finite number of steps: $ N = A_1 \cup S_1$ If $ A_1$ satisfies $ P$ we are done, if not $ S_1$ does by the lemma. And $ S_1 = A_2 \cup S_2$... ie and we keep applying this argument and if no $ A_i$ satisfies P then eventually we get $ S_{r - 2} = A_{r - 1} \cup A_r$ and so by the lemma at least one of these sets must satisfy $ P$