Республиканская олимпиада по математике, 2014 год, 11 класс

Пусть ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{2014}}$ — перестановка чисел 1, 2, $\ldots$, 2014. Какое наибольшее количество чисел среди чисел $a_{1}^{2}+{{a}_{2}}$, $a_{2}^{2}+{{a}_{3}}$, $\ldots$, $a_{2013}^{2}+{{a}_{2014}}$, $a_{2014}^{2}+{{a}_{1}}$ могут быть точными квадратами? ( Сатылханов К. )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Пусть $x_i = a_i^2 + a_{i+1}$ для $i = 1,~\ldots, ~2014$ ($a_{n+1} = a_1$). Заметим, что если для $x$, $y$, $k \in \mathbb{N}$ верно $x^2 + y = k^2$, то $k > x \Rightarrow k \geq x+1$, откуда $y = k^2 - x^2 \geq 2x+1$. Если $a_i \geq 1007,$ то $a_{i+1} \leq 2014 < 2a_{i} + 1$, откуда $$ a_i^2 < a_{i}^2 + a_{i+1} < (a_i + 1)^2, $$ то есть $x_i$ не может быть точным квадратом. Значит, ответ к задаче не превосходит $1006$. Далее покажем как построить пример для 1006 полных квадратов. Пусть $A = \{1, \ldots, 2014 \}$. Пусть $a_0 = 0$, $i = 1, \ldots, 2014$: \begin{equation*} a_i = \begin{cases} 2a_{i-1} + 1, & \text{ если } a_{i-1} \leq 1006,\\ \min(A \setminus \{a_{1}, \ldots, a_{i-1} \}), & \text{ если } a_{i-1} \geq 1007. \end{cases} \end{equation*} Докажем, что $\{a_1, \ldots, a_{2014} \} = A.$ Пусть $X_i = \{i\ |\ a_{i} = 2a_{i-1} + 1 \}$ и $Y = \{ i\ |\ a_i = \min(A \setminus \{a_{1}, \ldots, a_{i-1} \})\}$, тогда $X \cap Y = \emptyset$ и $X \cup Y = A.$ Предположим, $~\exists~ i \in Y$, что $a_{i}$ нечетный. Пусть $k = (a_i - 1)/2 \leq 1006$, если $~\exists~ t \leq i-1,$ что $k = a_t,$ то $a_{t+1} = 2a_t + 1 = a_i \implies i \in X$, что невозможно. Тогда $k \neq a_t ~\forall~ t \leq i-1 \implies k \in A\setminus\{a_1, \ldots, a_{i-1}\}$ и $k < a_i,$ откуда $a_i = \min(A \setminus \{a_{1}, \ldots, a_{i-1} \}) > k,$ что невозможно. Значит, $~\forall~ i \in Y$ $a_i$ четное и $~\forall~ i \in X$ $a_i = 2a_{i-1} + 1$ — нечетное. Отсюда следует, что $~\forall~ i \neq j$ и $i,j \in Y \implies$ $a_i \neq a_j$ ($i < j$, то $a_j = \min(A \setminus \{a_{1}, \ldots, a_{j-1} \}) \neq a_i$). Предположим, что $~\exists~ i < j$ и $i,j \in X$ такие, что $a_i = a_j$ и среди них рассмотрим с минимальной суммой $i + j$. Тогда $a_{i-1} = a_{i}/2 = a_{j}/2 = a_{j-1}$ и $i + j -2 < i+j,$ что невозможно. Тогда $~\forall~ i \neq j$ и $i,j \in X$ $a_i \neq a_j$, то есть $\{a_1, \ldots, a_{2014} \} = A$. К тому же, $~\forall~ i \in X$ мы имеем $a_{i} = 2a_{i-1} + 1$ и $a_{i-1}^2 + a_i = (a_{i-1} + 1)^2$, а так как $|X| = 1007$ (все нечетные числа), у нас будет ровно $1006$ полных квадратов (исключая $0^2 + 1^2 = 1^2$).