12-я Международная Жаутыковская олимпиада, 2016 год

Числа $a_1$, $a_2$, $\ldots$, $a_{100}$ — перестановка чисел от 1 до 100. Пусть ${S_1} = {a_1},$ $ {S_2} = {a_1} + {a_2},$ ${S_{100}} = {a_1} + {a_2} + \ldots {a_{100}}.$ Какое наибольшее количество точных квадратов могло оказаться среди чисел $S_1$, $S_2$, $\ldots$, $S_{100}$? ( Н. Седракян )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: $60$.
Добавим к последовательности $S_1$, $S_2$, $\ldots$, $S_{100}$ начальный член $S_0=0$ и рассмотрим все члены ${S_{{n_0}}} < {S_{{n_1}}} < \ldots $, являющиеся квадратами: $S_{n_k}=m_k^2$ (в частности, $n_0=m_0=0$). Так как $S_{100}= 5050 < 72^2$, все $m_k$ не больше $71$. Если $m_{k+1}=m_k+1$, то $S_{n_{k+1}}-S_{n_k}=2m_k+1$ нечётно, поэтому среди чисел $a_{n_k+1}$, $\ldots$, $a_{n_{k+1}}$ есть нечётное. Так как нечётных чисел, не превосходящих 100, всего 50, то среди разностей $m_{k+1}-m_k$, не более $50$ равных $1$. Если в исходной последовательности найдётся $61$ квадрат, то $${m_{61}} = \left( {{m_{61}} - {m_{60}}} \right) + \left( {{m_{60}} - {m_{59}}} \right) + \ldots + \left( {{m_1} - {m_0}} \right) \geqslant 50 + 11 \cdot 2 = 72,$$ что невозможно.
Пример последовательности, в которой 60 квадратов, строится, например, так. Положим $a_i=2i-1$ при $1 \le i \le 50$, тогда мы используем все нечётные числа, а $S_i=i^2$. Далее, возьмём $a_{51+4i}=2+8i$, $a_{52+4i}=100-4i$, $a_{53+4i}=4+8i$, $a_{54+4i}=98-4i$ при $0 \le i \le 7$, при этом будут использованы все чётные числа от $70$ до $100 $ и все числа, дающие остатки 2 и $4$ при делении на $8$, от $2$ до $60$, а $S_{54+4i}-S_{50+4i}=204+8i$, поэтому $S_{54+4i}={(52+2i)^2}$. Наконец, последними $18$ членами последовательности будут $30$, $40$, $64$, $66$, $68$, $6$, $8$, $14$, $16$, $32$, $38$, $46$, $54$, $62$, $22$, $24$, $48$, $56$. Это даёт $S_{87} =66^2+ 2 \cdot 134= 68^2$, $S_{96} = 70^2$.

$Ответ$:Наибольшее количество точных квадратов равно 60

$Пример$: У нас $b_1=a_1,b_2=a_1+a_2,...,b_{100}=a_1+a_2+...+a_{100}$

$b_1=1,b_2=b_1+3=2^2,b_3=b_2+5=3^2,...,b_{49}=b_{48}+97=49^2,b_{50}=b_{49}+99=50^2$

Здесь мы пользуемся тем что $x^2+(2x+1)=(x+1)^2$, следовательно если $k \le 49$ при $b_k=k^2$ у нас $b_k+(2k+1)=(k+1)^2$ здесь мы взяли $k \le 49$ чтобы число $2k+1$ было меньше 100, для того чтобы число $b_k+2k+1$ могло быть равно $b_{k+1}$.Заметим что здесь у нас получилось 50 квадратов и мы воспользуемся(всемя нечетными числами)

$Далее$:

$50^2+82+62+42+18=52^2=b_{54}$

$52^2+84+64+44+20=54^2=b_{58}$

$54^2+86+66+46+22=56^2=b_{62}$

$56^2+88+68+48+24=58^2=b_{66}$

$58^2+90+70+50+26=60^2=b_{70}$

$60^2+92+72+52+28=62^2=b_{74}$

$62^2+94+74+54+30=64^2=b_{78}$

$64^2+96+76+56+32=66^2=b_{82}$

$66^2+98+78+58+34=68^2=b_{86}$

$68^2+100+80+60+36=70^2=b_{90}$

У нас все числа которые мы прибавляем к квадратам различны и все четны заметим что:

$(x+2)^2-x^2=4x+4$

$(x+4)^2-(x+2)^2=4x+12$, то есть увеличивается на 8 как и в нашем примере где разница квадратов с каждым разом увеличивается на 8 это и был пример на $60$ квадратов перейдем к доказательству

$Д-во$:Предположим что есть пример на 61 квадрат пусть эти числа

$c_{1}^2 \lt c_{2}^2 \lt ... \lt c_{61}^2$

Также заметим что $100+99+...+1=\frac{100*101}{2}$

$71^2=5041;72^2=5184$ $\Rightarrow$

$c_1 \lt c_2 \lt ... \lt c_{61} \le 71$

Пусть: $c_1+d_1=c_2,c_2+d_2=c_3,...,c_{60}+d_{60}=c_{61}$

Мы имеем из $d_1,d_2,...,d_{60}$ $max$ $50$ единиц

ведь $(x+1)^2-x^2=2x+1$ что нечетно также у нас среди чисел $1,2,...,100$ ровно 50 нечетных чисел откуда и следует больше $50$ единиц больше не может

Заметим что $c_{61}=c_1+(d_1+d_2+...+d_{60})$ если $c_1 \gt 1$ то $d_1+d_2+...+d_{60} \ge 70=50+20$ ведь там $max$ $50$ единиц а оставшиеся $10$ чисел минимум двойки откуда следует $c_{61} \ge 70+c_1 \gt 71$ то есть при $c_1 \gt 1$ получаем $Противоречие$

Если $c_1=1$ но тогда среди чисел $d_1,d_2,...,d_{60}$ будет $max$ $49$ единиц ведь 1 нечетное число мы уже использовали . Тогда $d_1+d_2+...+d_{60} \ge 49+22=71 \Rightarrow c_{61} \ge 1+71 \gt 71$

Получаем $Противоречие$

То есть среди чисел $b_1,b_2,...,b_{100}$ не может быть $61$ квадратов и мы привели пример для $60$, решение окончено