LIII Международная Математическая Олимпиада

[Tanechka]

А что, разве не подходит функция:
Если $a$ - чётное, то $f(a)=0$
Если $a$ - нечётное, то $f(a)=C$

[Профессор Снэйп]

Tanechka в сообщении #594646 писал(а):

А что, разве не подходит функция:
Если $a$ - чётное, то $f(a)=0$
Если $a$ - нечётное, то $f(a)=C$

Подходит!

Я ошибся. У меня под корнями разные выражения, а я эти корни сократил

-- Чт июл 12, 2012 13:49:19 --

Получил, что если $f(2a) = 4f(a)$, то $f(a)$ должно быть чётным.

Похоже, здесь надо остатки рассматривать...

-- Чт июл 12, 2012 13:57:58 --

Кстати, вот совсем простое наблюдение: если $f(c) = 0$, то $f(a+c) = f(a)$ для всех $a$.

[Cash]

$3f^2(0)=6f^2(0) \Rightarrow f(0) = 0$
$f^2(a)+f^2(-a) = 2f(a)f(-a) \Rightarrow f(a) = f(-a)$
$f^2(2a)+2f^2(a)=4f(2a)f(a)+2f^2(a)\Rightarrow f(2a)(f(2a)-4f(a)) = 0$

1) $f(2)=0$
если $f(a)=0$ , то $f(k+a)=f(k)$
Любая функция $f(2k)=0, f(2k+1)=n$ удовлетворяет условию

2) $f(2) = 4f(1)$
Для упрощения записи, положим $f(1)=1$ (расширив поле поиска до функций с областью значений в $\mathbb Q$).
Все остальные решения получатся умножением на константу.
Подставив $a=1, b=2, c=-3$ находим, что
$f(3)=9$ или $f(3)=1$

2а) $f(3) = 9$.
Покажем по индукции, что $f(k)=k^2$
База для $k=1,2,3$ верна.

$f^2(k+1)+k^4+1=(2k^2+2)f(k+1)+2k^2$
$f(k+1)=(k+1)^2$ или $f(k+1)=(k-1)^2$
То есть значения в соседних точках являются значениями соседних квадратов.
Если $k=2n+1$, то $f(k+1)=f(2n+2)=4f(n+1)=(2n+2)^2=(k+1)^2$
Если $k=2n$, то $f(k+2)=f(2n+2)=4f(n+1)=(2n+2)^2=(k+2)^2$
и $f(k+1)$ остается только один вариант $f(k+1)=(2n+1)^2=(k+1)^2$
Ч.т.д.
То есть мы или вынуждены повышать градус или успеть спуститься до нуля, как в случае

2б) $f(1)=1, f(2)=4, f(3)=1$, тогда $f(4)=0$
И семейство функций:
$f(4k+1)=n, f(4k+2)=4n, f(4k+3)=n, f(4k)=0$

[Профессор Снэйп]

По поводу $f(x) = x^2$. Мне показалось, надо ещё проверить, что функция удовлетворяет исходным условиям. И ведь действительно удовлетворяет, ибо

$$ a^4 + b^4 + c^4 - (2a^2b^2+ 2a^2c^2 + 2b^2c^2) = (a+b+c)(a - b - c)(a - b + c)(a + b - c) $$

КАК такое можно увидеть без матпакета?!!

[arqady]

Профессор Снэйп в сообщении #594693 писал(а):

$$ a^4 + b^4 + c^4 - (2a^2b^2+ 2a^2c^2 + 2b^2c^2) = (a+b+c)(a - b - c)(a - b + c)(a + b - c) $$

КАК такое можно увидеть без матпакета?!!

Это же известно и заезженно. Когда выводится формула, Герона можно ненароком и скобки раскрыть...

[Профессор Снэйп]

arqady в сообщении #594723 писал(а):

Это же известно и заезженно. Когда выводится формула, Герона можно ненароком и скобки раскрыть...

Кому-то может и известно, а мне нет.

[lyuk]

Задача 1.
Точки $F$ и $G$ лежат на окружности с диаметром $AJ$ (это вытекает из того, что углы $LFG$ и $KGJ$ равны половине угла $A$).
Отсюда бисектрисы $BF$ и $CG$ треугольников $ABS$ и $ACT$ есть их высотами. Значит, эти тругольники равнобелреные и $MS=MT$ и равны полупериметру $ABC$.

[lyuk]

Задача 3.1.Берем множество, состоящее из $2^k$ чисел и спрашиваем входит ли $x$ в это множество. Если $k+1$ раз ответили "да", то таки "да".

Теперь пусть $A$ ответил "нет". Рассмотрими, к примеру, числа $0, 1, \dots, 2^{k}-1$. Для каждого $i=1,\dots , k$ обозначим через $A_i$ множество из этих чисел, у которых на $i$-том месте в двоичной записи находится цифра ноль. $B$ последовательно спрашивает входит ли число $x$ в множество $A_i$. Считая все ответы ложными однозначно получим число $y$. Заметим, что $x\ne y$, иначе $A$ соврал $k+1$ раз подряд. Т.о., мы всегда можем уменьшить количество претендентов на один.

[Профессор Снэйп]

Там в 3.1 в условии косяк. Точнее, минимум два косяка. Первый заключается в том, что $N$ неожиданно поменялось на $n$. А второй в том, что написано $n \geqslant 2^k$, хотя по логике должно быть $N \leqslant 2^k$.

[lyuk]

Все правильно в условии 3.1. Число $N$ присутствует в игре только для того, чтобы ограничить количество претендентов на $x$. Если положить $N=n$, то игрок $B$ автоматически выигрывает. И относительно неравенств все правильно. Чем меньше $n$, тем сложнее игроку $B$ выиграть. Например, если $n=1$, то он должен угадать число $x$.

[Профессор Снэйп]

lyuk в сообщении #594812 писал(а):

Все правильно в условии 3.1. Число $N$ присутствует в игре только для того, чтобы ограничить количество претендентов на $x$. Если положить $N=n$, то игрок $B$ автоматически выигрывает. И относительно неравенств все правильно. Чем меньше $n$, тем сложнее игроку $B$ выиграть. Например, если $n=1$, то он должен угадать число $x$.

Не понял. Если $N = n = 1$, то $x = 1$ и ничего угадывать не надо. И игрок $B$ выигрывает первым же ходом.

-- Пт июл 13, 2012 14:35:07 --

А вообще-то да, $n$ и $N$ обозначают разное. Там просто всё так оформлено, что первый, коротенький абзац в условии задачи легко пропустить. Я на него вначале даже не обратил внимание.

[Dave]

Моё решение задачи 5.

Определение. Пусть имеется остроугольный треугольник. Корневым треугольником для этого треугольника назовём прямоугольный треугольник, гипотезуза которого совпадает с одной из сторон исходного треугольника, а вершина прямого угла лежит на высоте, опущенной на эту сторону (всего есть три корневых треугольника, соответствующих исходному).

Лемма. Катеты двух разных корневых треугольников, выходящие из одной вершины исходного треугольника, равны.
Доказательство. Пусть $PQR$ - исходный треугольник, $PQS$ - его корневой треугольник, $H$ - основание высоты, проведённой из вершины $R$. Т. к. $\triangle SQH \sim \triangle PQS$, то $\frac {SQ} {HQ}=\frac {PQ} {SQ}$, откуда $SQ=\sqrt {PQ \cdot HQ}=\sqrt {PQ \cdot RQ \cdot \cos {\angle PQR}}$. Но точно такую же формулу, ввиду симметричности, мы получили бы для катета $QT$ другого корневого треугольника $RQT$.

Вернёмся к исходной задаче. Проведём из т. $B$ перпендикуляр к прямой $AX$. Пусть он пересекает эту прямую в т. $E$, а прямую $CD$ - в т. $F$. Тогда т. $X$ будет ортоцентром треугольника $ABF$, через который проходит также третья высота, $BG$, а треугольник $ABC$ - его корневым треугольником. Докажем, что $ALF$ и $BKF$ также являются корневыми треугольниками $ABF$. Действительно, если $AL'F$ - корневой треугольник, то, по вышедоказанной лемме, $AL'=AC$. Но внутри высоты $BG$ есть только одна точка $L$, для которой $AL=AC$, значит $L'=L$. Аналогично доказываем, что $K'=K$, если $BK'F$ - корневой треугольник. Теперь ещё раз применим лемму и получим, что $FK=FL$, откуда будет следовать равенство прямоугольных треугольников $FMK$ и $FML$, а значит и требуемое равенство $MK=ML$.

[arqady]

Результаты:
http://www.imo-official.org/year_indivi ... rm=western

[zhoraster]

(почти оффтоп)

Это олимпиада войдет в историю прежде всего благодаря беспрецендентно маразматической проверке задачи 4.

Если участник просто писал "легко проверить, что решения подходят", но не проверял их, то он получал 5 баллов.

Если же, например, он проверял $f(x)=ax^2$ и 4-периодичное решение, а про 2-периодичное писал "легко проверить, что оно подходит", то он получал 6 баллов. Это касалось и работы, кажется, этого корейца, в которой проверка 4-периодического решения занимала страницу -- там были разобраны все, если я не ошибаюсь, двадцать различных вариантов для $a,b,c$.

За бессвязные потоки сознания, в которых всплывали пункты из мракин-схемы, можно было получить 3, а то и 4 балла.

За полностью выписанное решение, в котором в последней строчке участник делил на $f(4)$ и терял 4-периодическое решение (причем, если бы он просто задумался о нулевости $f(4)$, ему больше ничего делать не пришлось, поскольку уже были посчитаны $f(2), f(4)$ и доказана $t$-периодичность в случае $f(t)=0$), могли поставить 2 балла. (Мне до последней координации предлагали 2 балла, на последней предлагали 3; уже после того, как я не согласился, на ужине согласились на 4, чтобы не выносить на заседание жюри.)

Из-за всего этого маразма кто-то имеет 40 баллов, кто-то серебро вместо золота (хотя не известно, где бы проходили границы, если бы оценивали нормально), кто-то бронзу вместо серебра.

Я на последнем заседании жюри говорил: ну ок, что случилось, то случилось, была б нормальная проверка, были б другие границы, и неизвестно, больше ли людей выиграло или проиграло от этого. Но одно я предлагал исправить - давать honourable mention тем людям, у которых по этой задаче 5 или 6 баллов (такие баллы исключительно давались за отсутствие проверки): таких участников было ровно четверо. Увы, не проголосовали, так как это противоречило регламенту (то, что медалей больше половины, тоже ему противоречило, но никого не смутило).

[dm]

(почти оффтоп)

zhoraster в сообщении #597225 писал(а):

Если участник просто писал "легко проверить, что решения подходят", но не проверял их, то он получал 5 баллов.

Если же, например, он проверял $f(x)=ax^2$ и 4-периодичное решение, а про 2-периодичное писал "легко проверить, что оно подходит", то он получал 6 баллов.

При полном доказательстве, что других решений нет.

zhoraster в сообщении #597225 писал(а):

За бессвязные потоки сознания, в которых всплывали пункты из мракин-схемы, можно было получить 3, а то и 4 балла.

Думаю, здесь ты немного преувеличиваешь. 4 балла чаще всего получались, если было сделано следующее:
a) доказано $f(-a)=f(a)$ и $f(2a)=0\text{ или }4f(a)$,
b) доказано $f(a+1)=(\sqrt{f(a)}\pm\sqrt{f(1)})^2$,
d) подстановкой в уравнение хотя бы одной из функций - квадратичная, 2-периодическая, 4-периодическая - (но не всех из них, например, если какая-то из них потеряна) проверено, что это решение,
e-f-g) представлено двумя способами $f(n)=(\sqrt{f(n-1)}\pm\sqrt{f(1)})^2=(\sqrt{f(n-2)}\pm\sqrt{f(2)})^2$ - это начало индукционного шага для доказательства единственности непериодического (квадратичного) решения.
Это уже не совсем "бессвязный поток сознания"

zhoraster в сообщении #597225 писал(а):

Я на последнем заседании жюри говорил: ну ок, что случилось, то случилось, была б нормальная проверка, были б другие границы, и неизвестно, больше ли людей выиграло или проиграло от этого. Но одно я предлагал исправить - давать honourable mention тем людям, у которых по этой задаче 5 или 6 баллов (такие баллы исключительно давались за отсутствие проверки): таких участников было ровно четверо. Увы, не проголосовали, так как это противоречило регламенту (то, что медалей больше половины, тоже ему противоречило, но никого не смутило).

Кстати, вот прецедент обратного: на IMO 2005 Bar Goueta получил бронзу с 8 баллами (тогда как для всех она начиналась с 12 баллов), а Egor Shelukhin получил пг с 3 баллами (что меньше необходимых, но не достаточных 7 баллов).