Maths Olympiad Prep

Library / /107 of 128

Combinatorics Difficulty 6.5 National Olympiad Prove it Philippines

Problem:

Each of the numbers in the set A={1,2,,2017}A=\{1,2, \ldots, 2017\} is colored either red or white. Prove that for n18n \geq 18, there exists a coloring of the numbers in AA such that any of its nn-term arithmetic sequences contains both colors. Inspired by Problem 891 from Putnam and Beyond, T. Andreescu and R. Gelca, Springer (2007)

Solution

Solution:

It suffices to show that for n18n \geq 18, the total number of colorings (without restriction) exceeds those that make some nn-term arithmetic sequence monochromatic.

There are 220172^{2017} colorings of a set with 2017 elements. The number of colorings that make a fixed nn-term sequence monochromatic is 222017n=22018n2 \cdot 2^{2017-n} = 2^{2018-n}, since the terms not in the sequence can be colored without restriction, while those in the sequence can be colored either all red or all white.

We now find the number of nn-term arithmetic sequences that can be obtained from AA. Such a sequence a,a+r,,a+(n1)ra, a+r, \ldots, a+(n-1) r is completely determined by the first term aa and common ratio rr, subject to the constraint a+(n1)r2017a+(n-1) r \leq 2017. For each value of aa, there are 2017an1\left\lfloor\frac{2017-a}{n-1}\right\rfloor sequences that start with aa. This means that the number of arithmetic sequences does not exceed
a=120172017an1=201620172(n1) \sum_{a=1}^{2017} \frac{2017-a}{n-1} = \frac{2016 \cdot 2017}{2(n-1)}
Therefore, the total number of colorings that make at least one arithmetic sequence monochromatic does not exceed
22018n201620172(n1) 2^{2018-n} \cdot \frac{2016 \cdot 2017}{2(n-1)}
But for n18n \geq 18,
22018n201620172(n1)22018n204820482(n1)=22039nn12202117<22017 \begin{aligned} 2^{2018-n} \cdot \frac{2016 \cdot 2017}{2(n-1)} & \leq 2^{2018-n} \cdot \frac{2048 \cdot 2048}{2(n-1)} \\ & = \frac{2^{2039-n}}{n-1} \leq \frac{2^{2021}}{17} < 2^{2017} \end{aligned}

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.