Maths Olympiad Prep

Library / /291 of 520

Combinatorics Difficulty 6.6 National olympiad Prove it

4. (CZS 2) Assume that the set of all positive integers is decomposed into rr (disjoint) subsets A1A2Ar=NA_{1} \cup A_{2} \cup \cdots A_{r}=\mathbb{N}. Prove that one of them, say AiA_{i}, has the following property: There exists a positive mm such that for any kk one can find numbers a1,a2,,aka_{1}, a_{2}, \ldots, a_{k} in AiA_{i} with 0<aj+1ajm0<a_{j+1}-a_{j} \leq m (1jk1)(1 \leq j \leq k-1).

Solution

4. Assuming that A1A_{1} is not such a set AiA_{i}, it follows that for every mm there exist mm consecutive numbers not in A1A_{1}. It follows that A2A3ArA_{2} \cup A_{3} \cup \cdots \cup A_{r} contains arbitrarily long sequences of numbers. Inductively, let us assume that AjAj+1ArA_{j} \cup A_{j+1} \cup \cdots \cup A_{r} contains arbitrarily long sequences of consecutive numbers and none of A1,A2,,Aj1A_{1}, A_{2}, \ldots, A_{j-1} is the desired set AiA_{i}. Let us assume that AjA_{j} is also not AiA_{i}. Hence for each mm there exists k(m)k(m) such that among k(m)k(m) elements of AjA_{j} there exist two consecutive elements that differ by at least mm. Let us consider mk(m)m \cdot k(m) consecutive numbers in AjArA_{j} \cup \cdots \cup A_{r}, which exist by the induction hypothesis. Then either AjA_{j} contains fewer than k(m)k(m) of these integers, in which case Aj+1ArA_{j+1} \cup \cdots \cup A_{r} contains mm consecutive integers by the pigeonhole principle or AjA_{j} contains k(m)k(m) integers among which there exists a gap of length mm of consecutive integers that belong to Aj+1ArA_{j+1} \cup \cdots \cup A_{r}. Hence we have proven that Aj+1ArA_{j+1} \cup \cdots \cup A_{r} contains sequences of integers of arbitrary length. By induction, assuming that A1,A2,,Ar1A_{1}, A_{2}, \ldots, A_{r-1} do not satisfy the conditions to be the set AiA_{i}, it follows that ArA_{r} contains sequences of consecutive integers of arbitrary length and hence satisfies the conditions necessary for it to be the set AiA_{i}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.