Maths Olympiad Prep

Library / /8 of 106

Combinatorics Difficulty 7.6 National olympiad, round 2 Find the answer

Is it possible to choose 19831983 distinct positive integers, all less than or equal to 10510^5, no three of which are consecutive terms of an arithmetic progression?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine whether it is possible to choose 19831983 distinct positive integers, all less than or equal to 10510^5, in such a way that no three of them form a consecutive arithmetic progression, we can approach this problem by constructing a suitable set of integers.

### Step-by-step Construction

1. Understanding the Constraint: We need to ensure that for any selection of three numbers a,b,ca, b, c from our set, where a<b<ca < b < c, the difference between consecutive terms is not constant, i.e., bacbb - a \neq c - b.

2. Strategizing the Selection:
- One common approach is to use numbers that space out sufficiently to prevent forming an arithmetic progression.
- For example, we can choose numbers from the series of triangular numbers or even-numbered positions in arithmetic sequences with large common differences.
- However, a simple and effective strategy involves considering the modulo constraint. Specifically, select numbers such that they do not fall into any simple arithmetic pattern when viewed under a smaller modulus.

3. Utilizing Modular Arithmetic:
- Specifically, we focus on numbers that satisfy a certain congruence condition. For instance, choose numbers of the form ak=1+3ka_k = 1 + 3k.
- This creates a separation that inherently prevents forming a subset where ba=cb=db - a = c - b = d for some common difference dd, particularly when dd is small compared to the spread achieved by selecting every third number.

4. Selection Feasibility:
- We determine the number of integers that can be chosen using this congruence condition by evaluating the sequence’s reach within the limits.
- For instance, if we select numbers ak=1+3ka_k = 1 + 3k up to 10510^5, the number of such numbers is approximately 10513+1\left\lfloor \frac{10^5 - 1}{3} \right\rfloor + 1.

5. Calculation & Conclusion:
- Evaluate the above expression: 999993+1=33333+1=33334\left\lfloor \frac{99999}{3} \right\rfloor + 1 = 33333 + 1 = 33334.
- This count, 3333433334, greatly exceeds 1983, fulfilling our goal of selecting 1983 numbers without forming an arithmetic progression of three terms.

In conclusion, by carefully choosing numbers as described, one can indeed select 1983 distinct positive integers below 10510^5 without forming an arithmetic progression. Thus, the answer is:
yes \boxed{\text{yes}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.