Maths Olympiad Prep

Library / /18 of 32

Combinatorics Difficulty 5.8 AIME, harder Prove it Romania

Is it possible to partition the set of the positive integers into two subsets such that none of them contains an infinitely long (non-constant) arithmetic progression?

Solution

The answer is in the affirmative. For example, one can consider
A={1,3,4,7,8,9,13,14,15,16,21,},A = \{1, 3, 4, 7, 8, 9, 13, 14, 15, 16, 21, \dots\},
B={2,5,6,10,11,12,17,18,19,20,26,},B = \{2, 5, 6, 10, 11, 12, 17, 18, 19, 20, 26, \dots\},
i.e., for the infinite word W=w1w2wk=aba2b2anbnW = w_1w_2\cdots w_k \cdots = aba^2b^2\cdots a^nb^n\cdots, put AA the set of the indices ii for which wi=aw_i = a, and BB the set of the indices ii for which wi=bw_i = b. The terms of an arithmetic progression are equally spaced, while AA and BB both contain arbitrarily long gaps, hence the conclusion follows readily.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.