39
МАТЕМАТИЧЕСКИЙ
Таким образом, точки P, Q в задаче 2 являются точками Шалтая, а поскольку они изогонально сопряжены, то и точками Болтая. Подводя итог, отметим, что фактически в задачах 1 и 2 доказана равносильность следующих утверждений: x в треугольнике ABC отрезки AC и BC равны; x точки Брокара лежат на медианах из вершин A и B;
Об одной задаче LXV Международной математической олимпиады
Н.ПАНЮНИН
В этой статье будет рассказано об одной симпатичной задаче с прошедшей международной математической олимпиады. Вот ее условие. Улитка Турбо играет на доске, имеющей 2024 ряда и 2023 столбца, в следующую игру. В 2022 клетках доски прячутся монстры. Изначально Турбо не знает, где находится какой-либо из монстров, но она знает, что в каждом ряду, кроме первого и последнего, есть ровно один монстр и что в каждом столбце находится не более одного монстра. Турбо делает серию попыток, чтобы пройти из первого ряда в последний. При каждой попытке она может выбрать в качестве начальной любую клетку в первом ряду, а затем совершает серию перемещений из клетки в соседнюю клетку, имеющую общую сторону. (Ей разрешается возвращаться в ранее посещенные клетки.) Если она посещает клетку с монстром, то ее
DOI: https://doi.org/10.4213/kvant20240805
КРУЖОК
x точки Брокара лежат на симедианах из вершин A и B; x A-точка Шалтая совпадает с B-точкой Болтая; x точки Брокара являются точками Шалтая; x точки Брокара являются точками Болтая. Возможно, читатели смогут обнаружить другие свойства рассмотренной конструкции.
попытка завершается и она переносится обратно в первый ряд, чтобы начать новую попытку. Монстры не двигаются, а Турбо запоминает, есть ли в каждой посещенной ею клетке монстр. Если она достигнет любой клетки в последнем ряду, ее попытка завершается и игра оканчивается. Определите минимальное значение n такое, что у Турбо есть стратегия, которая, независимо от местонахождений монстров, гарантирует достижение последней строки за n попыток или раньше. Даже если вы восьмиклассник или семиклассник, попробуйте сначала решить задачу самостоятельно. Не исключено, что, прочитав решение или даже увидев ответ, вы поймете, что могли бы и сами найти решение. Заметим, тем не менее, что и участники, и даже руководители некоторых традиционно сильных команд имели сложности с этой задачей. Наибольшее суммарное количество баллов за эту задачу – 38 – получили ребята из российской команды. Сначала исследуем задачу. Занумеруем строки сверху вниз, а столбцы – слева направо. Клетку, располагающуюся в i-й строке и j-м столбце, будем обозначать i, j. Зеленым цветом будем обозначать поля, где точно нет монстров, красным – где есть монстры, желтым – подозрительные поля. Вместо доски 2023 u 2024 рассмотрим поле с 11 столбцами и 12 строками. Суть решения от этого не изменится, а общий случай оставим читателю. Пусть Турбо обнаружила монстра во второй строке, потратив на это одну попытку (рис. 1). Заметим, что в этом случае от монстров свободны все остальные клетки второй строки, слева и справа от монстра, а
40
КВАН T 2024/№8
Рис. 1
также все клетки столбца под монстром. Тогда, использовав еще одну попытку, чтобы понять, есть ли монстр в желтых клетках, не больше чем с третьей попытки Турбо доберется до цели по одному из синих путей. Однако проведенное рассуждение не проходит в случае, когда обнаруженный Турбо монстр находится с краю второй строки, например, слева (рис. 2). В этом случае, если Турбо будет проверять, свободна ли желтая клетка, она может наткнуться на монстра, потратив таким образом вторую попытку. Но обойти эту клетку, как в случае
с монстром не с краю, уже не получится: слева стена. Таким образом, для прохода в нижнюю строку могут понадобится четыре попытки: две уже использованы, а Турбо гарантированно может пройти только в третью строку. Если она будет продолжать действовать таким образом, то в случае диагонального расположения монстров (рис. 3) число попыток будет возрастать. Можно ли поступить как-то иначе? Решающим соображением, как быть в этом случае, является отказ от проверки монстров в крайних положениях. Теперь перейдем непосредственно к изложению решения. Пусть Турбо действует следующим образом. Во время первой попытки Турбо проверяет все клетки второй строки, кроме крайних 2,1 и 2,11. Если в одной их них есть монстр, то Турбо уже знает, как не более чем за три попытки дойти до нижней строки. Если же нет, то, оставив крайние клетки в качестве подозрительных (рис. 4), Турбо будет проверять клетки третьей строки. Снова не все, а начиная с 3,3 и до 3,9. Если в этих клетках окажется монстр, то опять же Турбо знает, как не более чем за три попытки дойти до последней строки.
Рис. 2
Рис. 4
Рис. 3
Рис. 5