Whether there are integers $a_1$, $a_2$, $\cdots$, that are different from each other, satisfying: (1) For $\forall k\in\mathbb N_+$, $a_{k^2}>0$ and $a_{k^2+k}<0$; (2) For $\forall n\in\mathbb N_+$, $\left| a_{n+1}-a_n\right|\leqslant 2023\sqrt n$?
Problem
Source: 2023 China TST Problem 17
Tags: algebra, combinatorics, China TST
29.03.2023 18:40
07.04.2024 06:01
The distinct condition implies $\sum_{i=1}^{N^2}\frac1{\max(1,|a_i|)}=O(\log N)$ while by splitting into $N$ groups of the form $a_{i^2}$, $\ldots$, $a_{(i+1)^2-1}$, the two conditions give the lower bound $\theta\left(\frac1i\left(\frac11+\cdots+\frac1i\right)\right)$, so taking the sum implies that the sum is at least $\theta(\log^2N)>O(\log N)$, contradiction.
27.10.2024 19:02
Great problem. We prove the For any positive constant $C$ There do not exist integers $a_1$, $a_2$, $\cdots$, that are different from each other, satisfying: (1) For $\forall k\in\mathbb N_+$, $a_{k^2}>0$ and $a_{k^2+k}<0$; (2) For $\forall n\in\mathbb N_+$, $\left| a_{n+1}-a_n\right|\leqslant C\lfloor \sqrt{n} \rfloor$ Assume the contrary , For large enough $k$ consider the interval $[k^2,k^2+k]$ For any $a_{i}$ , and $i$ in this interval color $a_{i}$ red if its $<0$ and green otherwise. For any green colored term $a_{i}$ define its "valuation" to be $d(a_{i})$ that is if $a_{j}$ is closest red colored item to it in $a_{k^2},....,a_{k^2+k-1},a_{k^2+k}$ say $a_{j}$ then $|j-i|$ is minimized then $d(a_{i})=|j-i|$ Similarly define for red colored ones as the closest green one. Define the net evaluation of red $d_{R}$ in $[k^2,k^2+k]$ intevral to be the sum of reciprocals of all the valuations of red colored terms and define for green $d_{G}$ similarly. Then it is easy to see $d_{G}+d_{R} \to \infty$ as $k$ gets larger using harmonic series divergence Easy to observe that for any $|a_{i}| \leq Cd(a_{i})k$. Now here comes the main step for large numbers $T$ count the number of positive and negative integers in $a_{i}$ such that $|a_i| \leq T$ . As $d_{G}+d_{R} \to \infty$ gets easy to see eventually for large $T$ this counts exceeds $2T+1$ which is contradiction