Olympiad Maths Prep

Track / Stage 8 / 43 of 180 #1743 of 2000

Problem 1743

IMO Shortlist mid-range; USAMO P2/P5
Algebra Difficulty 8.2 Find the answer china_team_selection_test

Whether there are integers a1a_1, a2a_2, \cdots, that are different from each other, satisfying:
(1) For kN+\forall k\in\mathbb N_+, ak2>0a_{k^2}>0 and ak2+k<0a_{k^2+k}<0;
(2) For nN+\forall n\in\mathbb N_+, an+1an2023n\left| a_{n+1}-a_n\right|\leqslant 2023\sqrt n?

Official solution

To determine whether there exist integers a1,a2,a_1, a_2, \ldots that are distinct and satisfy the given conditions, we analyze the problem as follows:

1. For all kN+ k \in \mathbb{N}_+ , ak2>0 a_{k^2} > 0 and ak2+k<0 a_{k^2 + k} < 0 .
2. For all nN+ n \in \mathbb{N}_+ , an+1an2023n |a_{n+1} - a_n| \leq 2023 \sqrt{n} .

Assume such a sequence {an} \{a_n\} exists. Let f(k) f(k) denote an integer in the interval [k2,k2+k1][k^2, k^2 + k - 1] such that af(k)>0 a_{f(k)} > 0 and af(k)+1<0 a_{f(k) + 1} < 0 . Similarly, let g(k) g(k) denote an integer in the interval [k2+k,(k+1)21][k^2 + k, (k+1)^2 - 1] such that ag(k)<0 a_{g(k)} < 0 and ag(k)+1>0 a_{g(k) + 1} > 0 .

By the triangle inequality and the given condition an+1an2023n |a_{n+1} - a_n| \leq 2023 \sqrt{n} , we can bound the values of af(k)±C a_{f(k) \pm C} and ag(k)±C a_{g(k) \pm C} for any integer C C as follows:
af(k)±C2023(C+1)(k+1), |a_{f(k) \pm C}| \leq 2023 (C + 1) (k + 1),
ag(k)±C2023(C+1)(k+1). |a_{g(k) \pm C}| \leq 2023 (C + 1) (k + 1).

Consider a large integer N N and the number of terms t t such that atN2 |a_t| \leq N^2 . On one hand, this number must be at most 2N2+1 2N^2 + 1 .

On the other hand, if j j is finite and very small compared to N N , for each t[jN22023,(j+1)N22023] t \in \left[ \frac{jN^2}{2023}, \frac{(j+1)N^2}{2023} \right] , we need:
at=af(t)±C2023(C+1)(t+1), |a_t| = |a_{f(\lfloor \sqrt{t} \rfloor) \pm C}| \leq 2023 (C + 1) (\sqrt{t} + 1),
or
ag(t)±C2023(C+1)(t+1). |a_{g(\lfloor \sqrt{t} \rfloor) \pm C}| \leq 2023 (C + 1) (\sqrt{t} + 1).

This implies that C<N4046j C < \frac{N}{4046 \sqrt{j}} works for sure. There are N(j+1j)2023<N4100j \frac{N (\sqrt{j+1} - \sqrt{j})}{2023} < \frac{N}{4100 \sqrt{j}} intervals, so we can pick N2109j \frac{N^2}{10^9 j} terms that are guaranteed to be at most N2 N^2 .

By choosing j=exp(2109) j = \exp(2 \cdot 10^9) and N>exp(j) N > \exp(j) , we get that 2N2+1<3N2<N2(Hj1)109 2N^2 + 1 < 3N^2 < N^2 (H_j - 1) 10^{-9} . As the former is the number of possible terms that have absolute value at most N2 N^2 and the latter is the number of terms that must have absolute value at most N2 N^2 , we reach a contradiction.

Therefore, no such sequence {an} \{a_n\} exists.

The answer is: \boxed{\text{No}}.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.