Processing math: 26%

12-ші халықаралық Жәутіков олимпиадасы, 2016 жыл


Бізге 1,2,,100 сандарының алмастыруы болатын a1, a2, , a100 тізбегі берілген. S1=a1, S2=a1+a2, , S100=a1+a2++a100 деп белгілейік. S1, S2, , S100 сандарының ішінде ең көп дегенде қанша толық квадрат кездесуі мүмкін? ( Н. Седракян )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: 60.
Добавим к последовательности S1, S2, , S100 начальный член S0=0 и рассмотрим все члены Sn0<Sn1<, являющиеся квадратами: Snk=m2k (в частности, n0=m0=0). Так как S100=5050<722, все mk не больше 71. Если mk+1=mk+1, то Snk+1Snk=2mk+1 нечётно, поэтому среди чисел ank+1, , ank+1 есть нечётное. Так как нечётных чисел, не превосходящих 100, всего 50, то среди разностей mk+1mk, не более 50 равных 1. Если в исходной последовательности найдётся 61 квадрат, то m61=(m61m60)+(m60m59)++(m1m0) что невозможно.
Пример последовательности, в которой 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.

  1
3 года 11 месяца назад #

Ответ:Наибольшее количество точных квадратов равно 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, решение окончено