Туймаада 2016

[SomePupil]

Математическая часть международной олимпиады. Перед каждой задачей записано имя автора задачи.

А. Голованов. 1. Последовательность $(a_n)$ задана условиями $a_1=0$,

$$a_{n+1} = \frac{a_1+a_2+\ldots+a_n}n+1.$$

Докажите, что $a_{2016} > \frac 12 + a_{1000}$.

А. Чухнов. 2. На одной из клеток клетчатой плоскости стоит кубик. На каждой грани кубика нарисована стрелочка в одном из четырёх направлений, параллельных сторонам грани. Антон смотрит на кубик сверху и перекатывает его через ребро в направлении, указанном стрелкой, нарисованной на верхней грани. Докажите, что кубик никогда не заметёт никакого квадрата $5\times5$.

А. Пастор. 3. Высоты $AA_1, BB_1, CC_1$ остроугольного треугольника $ABC$ пересекаются в точке $H$. Точки $A_0, B_0, C_0 -$ середины сторон $BC, CA$ и $AB$ соответственно. На отрезках $AH, BH$ и $HC_1$ отмечены точки $A_2, B_2, C_2$ соответственно, такие что $\angle{A_0B_2A_2} = \angle{B_0C_2B_2} = \angle{C_0A_2C_2} = 90^\circ$. Докажите, что прямые $AC_2, BA_2$ и $CB_2$ пересекаются в одной точке.

В. Шевелёв. 4. При каждом натуральном $k$ найдите число решений уравнения

$$8^k = x^3 + y^3 + z^3 - 3xyz$$

в неотрицательных целых числах $x, y, z,$ причем $0 \le x\le y\le z$.

[Human]

$\displaystyle1.\ a_n=H_{n-1}=\sum_{k=1}^{n-1}\frac1k,\ n\geqslant2$

[SomePupil]

Первый орешек расколот! Human вывел соотношение, из которого сразу же получаем:

$$a_{2016} - a_{1000} = \sum\limits_{k=1000}^{2015}\frac1k > \frac{1016}{2015} > \frac 12.$$

[sergei1961]

Кубический многочлен не раскладывается на множители?

[SomePupil]

sergei1961, если я отвечу, это уже будет подсказка. А хотя... Если бы не раскладывалось, то уравнение вообще было бы невозможно решить.

[DeBill]

(Оффтоп)

SomePupil в сообщении #1139117 писал(а):

если я отвечу, это уже будет подсказка.

Это - уже подсказка...

[Sonic86]

Про 4 все так пишут, будто она легкая, но ничего не пишут.
Ну напишу я, только у меня не особо простое решение:

$F=x^3+y^3+z^3-3xyz=(x+y+z)(x+\omega y+\omega^2 z)(x+\omega^2 y+\omega z), \ \ \omega^3=1$
Последние 2 множителя сопряжены. $2$ - простое в $\mathbb{Z}$ и $3\nmid 2-1$, значит $2$ - простое в $\mathbb{Z}[\omega]$. Значит 2,3-й множитель действительны: $y=z$, значит $F=(x+2y)(x-y)^2$.
$u=x-y, x=u+y, F=(u+3y)u^2=8^k$
Если $k=0$, то $u=1,y=0$.
Если $2|u$, то $2|y$, откуда уравнение $(u+3y)u^2=8^k$ сводится к уравнению $(u_1+3y_1)u_1^2=8^{k-1}$
Если $2\nmid u$, то $u=1, 3y=8^k-1$ - единственное решение есть только при четном $k$.
Значит всего $\left[\frac{k}{2}\right]$ решений.

Правильно хоть?

[waxtep]

Sonic86 в сообщении #1139353 писал(а):

Правильно хоть?

У меня по-другому получилось, для любого $k$ решение одно и при том тривиальное: $\{x,y,z\}=\{0,0,2^k\}$. Логика такая: мы можем положить $y=x+u, z=x+u+v, x,u,v\ge 0$, тогда исходное равенство эквивалентно $8^k=(3x+2u+v)(u^2+uv+v^2)$. Обе скобки должны быть степенями двойки, значит, $x,u,v$ по крайней мере четны; выделив двойку из этих трех чисел мы получим равенство того же вида; бесконечно так не поделаешь, значит, одно (и только одно) из $u,v$ равно нулю. При этом, $v=0$ решений не дает, т.к. должно быть одновременно $u=2^n$ и $3x+2u=2^n$, а $u=0$ дает упомянутое выше единственное тривиальное решение.

-- 22.07.2016, 00:57 --

А, нет, ерунду спорол то что один из множителей равен $4^n$, не означает, что другой должен быть равен $2^n$, а лишь $2^{3k-2n}$...

-- 22.07.2016, 01:35 --

В общем, похоже, всего $k+1$ решений, половина для $u=0$, а половина для $v=0$ (половина с точностью до $\pm 1$ если $k$ четно). Например, для $k=5$ годятся следующие тройки $x,y,z$:

$2730,2730,2732 168,168,176 0,0,32 10922,10923,10923 680,684,684 32,48,48$

[Shadow]

Назовем решение "базовым", если хотя бы одно из трех чисел нечетное.
$(x+y+z)(x^2+y^2+z^2-xy-yz-zx)=8^k$
При таких условиях оба сомножителя не могут быть четными, следовательно или $x+y+z=1$, что неинтересно, решение $(0,0,1)$ является базовым для $k=0$, или
$x^2+y^2+z^2-xy-yz-zx=1$

$(z-y)^2+(z-x)^2+(y-x)^2=2$
Сумма трех квадратов равна двум, решения ясны:
$(x,x,x+1)$, а также $(x,x+1,x+1)$
В первом случае $3x+1=8^k$, во втором $3x+2=8^k$
В зависимости от четности $k$ либо первое, либо второе уравнение имеет решение. Тоесть, для любого $k$ существует ровно одно базовое решение.
Нам нужно посчитать все базовые решения от $0$ до $k$ - их ровно $k+1$

[DeBill]

2. Странная какая-то задача. Или я чё не пОнял? И что значит "заметет"?
Нарисуем еще на каждой грани красную стрелку, противоположную существующей. Красные стрелки показывают, какая грань будет следующей верхней. (Если отметить центры граней, и соединить соответствующие центры по красным стрелкам, получим орграф с вершинами в вершинах октаэдра). Ясно, что, гуляя по стрелкам, мы вляпаемся в цикл. Какой длины?
а) 2. Тогда кубик будет дергаться по двум клеткам, и всего затопчет не боле $2+4$ клеток.
б) 3. Катание кубика показывает, что такому циклу соответствует движение по квадратику $2\times 2$. Мало.
в) 4. Пар противоположных вершин - три. Значит, в цикле есть така пара, пусть это
$A_1$ и $A_2$, Тогда цикл есть $A_1,Y, A_2, X$. Если $X,Y$ - противоположны, то кубик укатится по прямой в туман. Если нет, то - катаем - кубик катится по контуру квадратика $3\times3$. Мало.
г) 5. Одна вершинка не вошла, есть пара противоположных, и с одной стороны от них - одна вершинка, а с другой - две. Методом глядения на картинку видим, что, с точностью до переобозначений и симметрии, цикл есть $A_1,B_1,A_2,B_2,C_1$ (либо $A_1,B_1,A_2, C_1,B_2$ - но это то же самое). Катая кубик, видим: затопчет контур квадратика $6\times6$ со вдавленными углами ( в шахматной нотации:
$b_1$ (старт!), $ c_1,d_1,e_1,e_2; f_2$ (второй цикл)$f_3,f_4,f_5,e_5,e_6$ (третий) $d_6,c_6, b_6,b_5,a_5$ (четвертый ) $a_4,a_3,a_2,b_2,b_1$. Далее - зациклились). Итого: $20+1$ клеток (не боле)
д) 6. Расставим по кругу 6 точек: 2 красных, две синих и 2 зеленых, так, что одноцветные не стоят рядом. Это можно сделать (с точностью до перекрашивания и симметрий) двумями способами : либо все одноцветные - в противоположных вершина, либо только одна пара - в противоположных. Катание кубика показывает, что в обоих случаях он уедет в туман (за три перекатывания он "ходит конем" (в первом случае - конем $1+1$, во втором - обычным конем $2+1$), далее этот же ход повторяется ). Опять ни фига не вышло...

(Оффтоп)

Ну дурное какое-то решение. Может, как то четность-нечетность цикла обыграть - для 4 и 6 - едет в туман....

[SomePupil]

Shadow, изящно и правильно!

DeBill, да, вторая задача довольно странная. "Заметет квадрат $5\times 5$" означает "побывает в клетках, составляющих квадрат $5\times 5$".

DeBill писал(а):

Ясно, что, гуляя по стрелкам, мы вляпаемся в цикл

На самом деле, движение кубика может быть и без циклов. Чтобы убедиться в этом, достаточно заметить, что, когда кубик повторно оказывается некой гранью вверх, то стрелка на этой грани может быть направлена уже в другую сторону, чем прежде.

P. S. Задачи такого рода, как вторая, требуют решения определенного вида. Фокус тут в том, что надо расписать всё, что очевидно, а всё, что неочевидно $-$ замести под ковёр и сделать вид, что это очевидно. Да, это не то, что научные статьи писать $-$ тут олимпиада.

[DeBill]

SomePupil
Гуляя по стрелкам - на графе!
А - что движение бывает без циклов - так в решении как раз и получены три таких случая...

[Munin]

DeBill
Не хотите расписать все циклы на октаэдре и  додека  икосаэдре?

[Sergic Primazon]

2) Всего $24 $ положения кубика на плоскости, $12 $ пар отличающихся поворотом на $180^0 $.

Возможны $2 $ случая:

1. После нескольких ходов встретится два положения кубика образующих пару . Это может произойти не более чем за $12 $ ходов. Поэтому , в этом случае, мы "зациклимся" и сделаем до этого момента не более $24 $ ходов.

2. Не встретились два положения кубика образующих пару.
В этом случае у кубика на плоскости может быть не более $6 $ различных ориентаций ( по $1 $ на каждой из граней). Т.е. не далее чем за $6 $ ходов траектория либо "зациклится" , либо начнет повторяться со смещением (a, b), где $|a|+|b| \le 6 $.

[DeBill]

Sergic Primazon
Здорово! То-то мне мое решение не нравилось...
Munin

(Оффтоп)

Это Вы так шутите, да?
Я ж по рабоче-крестьянски, именно что расписал все циклы на октаэдре; зачем про это спрашивать? А вот насчет доде-ико - тут я не понял....Или у меня что-то с чувством юмора не то? Или не у меня?