Maths Olympiad Prep

Library / /1 of 7

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+1an2023n|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+1N21kN+1N2+11k=lnN2+1N+1>ln(N1), \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,,N21k = N, N+1, \dots, N^2-1,
(i) At least N2k+1\lfloor \frac{N^2}{k+1} \rfloor elements of ak2,,ak2+k1a_{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
2k=N+1N2N2k2N2k=N+1N21k2(N2N)>2N220242N2+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+k1}\ell \in \{k^2, k^2 + 1, \dots, k^2 + k - 1\}, we have
a+1a2023(k+1). |a_{\ell+1} - a_{\ell}| \le 2023(k+1).
We consider the following three cases.
(a) If there exists an a2023N2a_\ell \ge 2023N^2 in the sequence ak2,,ak2+k1a_{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+k1a_\ell, a_{\ell+1}, \dots, a_{k^2+k-1}.
(b) If there exists an a2023N2a_\ell \le -2023N^2 in the sequence ak2,,ak2+k1a_{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,,aa_{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+k1a_{k^2}, \dots, a_{k^2+k-1} are within SS, and there are a total of kN2k+1k \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.