Processing math: 40%

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


Пусть a1, a2, , a2014 — перестановка чисел 1, 2, , 2014. Какое наибольшее количество чисел среди чисел a21+a2, a22+a3, , a22013+a2014, a22014+a1 могут быть точными квадратами? ( Сатылханов К. )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Пусть xi=a2i+ai+1 для i=1, , 2014 (an+1=a1). Заметим, что если для x, y, kN верно x2+y=k2, то k>xkx+1, откуда y=k2x22x+1. Если ai1007, то ai+12014<2ai+1, откуда a2i<a2i+ai+1<(ai+1)2, то есть xi не может быть точным квадратом. Значит, ответ к задаче не превосходит 1006. Далее покажем как построить пример для 1006 полных квадратов. Пусть A={1,,2014}. Пусть a0=0, i=1,,2014: ai={2ai1+1, если ai11006,min Докажем, что \{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).