4. (CZS 2) Assume that the set of all positive integers is decomposed into (disjoint) subsets . Prove that one of them, say , has the following property: There exists a positive such that for any one can find numbers in with .
Solution
4. Assuming that is not such a set , it follows that for every there exist consecutive numbers not in . It follows that contains arbitrarily long sequences of numbers. Inductively, let us assume that contains arbitrarily long sequences of consecutive numbers and none of is the desired set . Let us assume that is also not . Hence for each there exists such that among elements of there exist two consecutive elements that differ by at least . Let us consider consecutive numbers in , which exist by the induction hypothesis. Then either contains fewer than of these integers, in which case contains consecutive integers by the pigeonhole principle or contains integers among which there exists a gap of length of consecutive integers that belong to . Hence we have proven that contains sequences of integers of arbitrary length. By induction, assuming that do not satisfy the conditions to be the set , it follows that contains sequences of consecutive integers of arbitrary length and hence satisfies the conditions necessary for it to be the set .