Это самая скандальная задача с IMO за последние несколько лет! Что же в ней такого? Одни говорят, что она очень легкая и что она забыла вообще на самой сложной олимпиаде по математике в мире, а другие что она очень красивая и сложная.
Давайте взглянем на результаты. Первые четыре места заняли США, Китай, Россия и Южная Корея. А если смотреть топ по нашей задаче, то Россия - на первом месте; Беларусь - на втором (в глобальном рейтинге на пятом); на третьем - США; а вот Китай - на шестнадцатом; а Южная Корея вообще на 82 месте, когда в глобальном рейтинге на четвертом!
В этом и причина всех скандалов. Много кто говорит, что задача слишком простая для IMO и её и на базовом ЕГЭ по математике все решат, а кто-то что она наоборот очень красивая, ну вот например Китайцы её не решили.
Условие
Улитка Турбо играет на доске, имеющей 2024 ряда и 2023 столбца, в следующую игру.
В 2022 клетках доски прячутся монстры. Изначально Турбо не знает, где находится какой-либо из монстров, но она знает, что в каждом ряду, кроме первого и последнего, есть ровно один монстр и что в каждом столбце находится не более одного монстра.
Турбо делает серию попыток, чтобы пройти из первого ряда в последний. При каждой попытке она может выбрать в качестве начальной любую клетку в первом ряду, а затем совершает серию перемещений из клетки в соседнюю клетку, имеющую общую сторону. (Ей разрешается возвращаться в ранее посещенные клетки.)
Если она посещает клетку с монстром, то её попытка завершается, и она переносится обратно в первый ряд, чтобы начать новую попытку. Монстры не двигаются, а Турбо запоминает, есть ли в каждой посещенной ею клетке монстр. Если она достигнет любой клетки в последнем ряду, её попытка завершается и игра оканчивается.
Определите минимальное значение n такое, что у Турбо есть стратегия, которая, независимо от местонахождений монстров, гарантирует достижение последней строки за n попыток или раньше
Решение
Оценка
Нам нужно гарантировать что улитка дойдёт до нижней строки таблицы, то есть найти такое число n, что улитка в любом случае за n попыток доползёт до низа.
Понятно, что хотя бы одну попытку мы точно потратим, ибо как только мы выползем с безопасной первой строки можем напороться на монстра, и вот улитка уже расплатилась одной жизнью.
Сможет ли улитка пройти эту полосу препятствий умерев только один раз? Если улитка уже наткнулась на какого-то бандита, то следующая встреча с монстром уже может быть на третьей строке, если первого монстра улитка встретила как только вышла из первой строки во вторую.
Без двух смертей улитке получается не обойтись. А вот на две смерти - есть стратегия.
Как улитке действовать?
Наверное самое важное условие во всей задаче - в одной строке и в одном столбце может быть только один монстр. То есть если мы наткнемся на монстра, то мы знаем, что он "выпускает лучики безопасности", то есть в остальных клетках его строки и столбца безопасно. По факту если мы "подкопаемся" под этого монстра, то мы сможем дойти до низа легко и проста, ведь под ним по условию монстров не будет. Это - самая главная и основная мысль в решении.
Самое простое и лаконичное решение заключается в том что Турбо гуляет по второй строке и ищет в ней монстра. Если этот монстр стоит не на краю этой строки, то мы с одной из двух сторон этого монстра можем обойти и таким образом мы "подкопались под монстра".
А что если монстр "на краю" второй строки? Тогда мы отступаем одну клетку от этого монстра и спускаемся по диагонали. Если мы на этой диагонали не наткнёмся на монстра, то мы просто придём вниз. Если же наткнёмся то второй монстр открывает нам путь к безопасной зоне под первым монстром.
Почему азиаты не решили?
Ответ простой - они тоже люди, а не киборги.
Возможно они с самого начала построили неправильную гипотезу и начали доказывать её и искать оценку под неё. И начали доказывать гипотезу зависящую от сторон треугольника, а случай n=const им почему-то по каким-то причинам не понравился.
У задачи нет никакой особой идеи, и "русская смекалочка" - здесь роль сыграла, но догадаться до этого решения мог и любой участник сборной Китая.
Возможно в азиатских сборных при подготовке дали задачу, которая очень похожа на эту "на первый взгляд", но на самом деле это совсем другая задача.
Большое спасибо за прочтение статьи :D
Больше интересного контента каждый день в телеграм канале "Сложно-простая математика".
Подписывайтесь, не забывайте ставить лайки и писать комментарии. Надеюсь, что мы не прощаемся :-3!