Maths Olympiad Prep

Library / China-TST-B /1 of 6

China-TST-B

Combinatorics Difficulty 8.2 Shortlist Prove it China

Does there exist a sequence of pairwise distinct integers a1,a2,…a_1, a_2, \dots that satisfies both of the following conditions?

a. For all positive integers kk, we have ak2>0a_{k^2} > 0 and ak2+k<0a_{k^2+k} < 0.

b. For all positive integers nn, we have ∣an+1−an∣≤2023n|a_{n+1} - a_n| \le 2023\sqrt{n}.

Solution

Proof. Such a sequence does not exist. We prove this by contradiction. Suppose there exists such a sequence. Take a positive integer NN satisfying
1N+1+1N+2+⋯+1N2>2024. \frac{1}{N+1} + \frac{1}{N+2} + \dots + \frac{1}{N^2} > 2024.
Such an NN exists because
∑k=N+1N21k≥∫N+1N2+11k=ln⁡N2+1N+1>ln⁡(N−1), \sum_{k=N+1}^{N^2} \frac{1}{k} \ge \int_{N+1}^{N^2+1} \frac{1}{k} = \ln \frac{N^2+1}{N+1} > \ln(N-1),
which can be arbitrarily large.
We prove that at least 4046N2+24046N^2 + 2 elements of a1,a2,…a_1, a_2, \dots fall into the interval S=[−2023N2,2023N2]S = [-2023N^2, 2023N^2], which contradicts the assumption that aia_i's are all distinct. To show this, it suffices to prove that for k=N,N+1,…,N2−1k = N, N+1, \dots, N^2-1,
(i) At least ⌊N2k+1⌋\lfloor \frac{N^2}{k+1} \rfloor elements of ak2,…,ak2+k−1a_{k^2}, \dots, a_{k^2+k-1} fall into SS.
(ii) At least ⌊N2k+1⌋\lfloor \frac{N^2}{k+1} \rfloor elements of ak2+k,…,ak2+2ka_{k^2+k}, \dots, a_{k^2+2k} fall into SS.
In this way, the total number of elements in SS is greater than or equal to
2∑k=N+1N2⌊N2k⌋≥2N2∑k=N+1N21k−2(N2−N)>2N2⋅2024−2N2+2N>4046N2+2. 2 \sum_{k=N+1}^{N^2} \left\lfloor \frac{N^2}{k} \right\rfloor \ge 2N^2 \sum_{k=N+1}^{N^2} \frac{1}{k} - 2(N^2 - N) > 2N^2 \cdot 2024 - 2N^2 + 2N > 4046N^2 + 2.
We will only prove (i), and the proof of (ii) is similar. Note that for ℓ∈{k2,k2+1,…,k2+k−1}\ell \in \{k^2, k^2 + 1, \dots, k^2 + k - 1\}, we have
∣aℓ+1−aℓ∣≤2023(k+1). |a_{\ell+1} - a_{\ell}| \le 2023(k+1).
We consider the following three cases.
(a) If there exists an aℓ≥2023N2a_\ell \ge 2023N^2 in the sequence ak2,…,ak2+k−1a_{k^2}, \dots, a_{k^2+k-1}, then (*) implies that there are at least ⌊2023N22023(k+1)⌋\lfloor \frac{2023N^2}{2023(k+1)} \rfloor elements in [0,2023N2][0, 2023N^2] among aℓ,aℓ+1,…,ak2+k−1a_\ell, a_{\ell+1}, \dots, a_{k^2+k-1}.
(b) If there exists an aℓ≤−2023N2a_\ell \le -2023N^2 in the sequence ak2,…,ak2+k−1a_{k^2}, \dots, a_{k^2+k-1}, then (*) implies that there are at least ⌊2023N22023(k+1)⌋\lfloor \frac{2023N^2}{2023(k+1)} \rfloor elements in [−2023N2,0][-2023N^2, 0] among ak2,ak2+1,…,aℓa_{k^2}, a_{k^2+1}, \dots, a_\ell.
(c) If neither (a) nor (b) holds, then all the elements in the sequence ak2,…,ak2+k−1a_{k^2}, \dots, a_{k^2+k-1} are within SS, and there are a total of k≥⌊N2k+1⌋k \ge \lfloor \frac{N^2}{k+1} \rfloor elements.
This completes the proof of (i), and the proof of (ii) can be similarly established. Therefore, a contradiction is reached, and thus such a sequence does not exist. □\square

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.