Она имеет отчетливый алгоритмический оттенок. Не очень легкое для понимания условие. В 2021 ямок положены в произвольном порядке 2021 пронумерованных ореха. На шагу номер k у ореха под номером k его соседи меняются местами. Иногда оба его соседа будут больше, чем он, по номерам, иногда оба меньше. Надо доказать, что хотя бы один раз случится, что один сосед будет больше, а другой - меньше. Просто-таки просится идея найти какой-нибудь удобный инвариант всего порядка орехов, но я такого найти не смог, хотя пытался. В итоге мое решение немного по-другому работает.
Я думал об этой задаче с перерывами наверное часов 6, и сегодня добил до решения, когда выбирал сыр в витрине магазина. Я извинился перед продавщицей, с которой говорил, отошел в угол, уставился в пол и додумал главную идею до конца.
Дальше идет мое решение, если хотите решать сами, не смотрите.
[Spoiler (click to open)]
Введем немного терминологии. Когда на k-m шагу у ореха номер k меняются местами соседи, назовем это "орех номер k стреляет". Если в какой-то момент времени шаг номер k уже случился, то орех номер k называется "выстрелившим", а если еще не случился - "невыстрелившим". Далее, если в момент выстрела оба соседа больше по номерам, чем стреляющий орех, назовем это "выстрел вверх". Если оба меньше, назовем это "выстрел вниз". Если один меньше, один больше - "выстрел наискосок". Наша задача - доказать, что есть хотя бы один выстрел наискосок. Для этого мы прямо сейчас предположим, что их нет ни одного, и в конце придем к противоречию.
Итак, выстрелы могут быть только вверх (меняются местами два соседа номерами больше нашего) или вниз (номерами меньше нашего). Отсюда мы делаем следующее важное НАБЛЮДЕНИЕ: при любом обмене мест на место невыстрелившего ореха приходит другой невыстреливший, а на место выстрелившего - другой выстреливший. Это соответствует выстрелу вниз и выстрелу вверх соответственно.
Теперь о главной идее доказательства. Я хочу доказать, что на протяжении всех 2021 шагов выстрелов вверх встречается меньше, чем выстрелов вниз. Обратите внимание, что первый выстрел (орех номер 1) всегда вверх, последний (орех номер 2021) всегда вниз. На первых номерах преобладают выстрелы вверх, на последних вниз, посредине может быть по-разному, но я хочу доказать, что всего выстрелов вверх меньше, чем вниз.
Предположим, что я это доказал. Теперь представим себе, что мы взяли конечное состояние, после 2021-го выстрела, и разматываем его в обратном направлении: сначала опять меняем соседей 2021-го, потом соседей 2020-го и так далее. В конце мы придем к исходному состоянию. Используя ровно то же доказательство, что я сейчас приведу ниже (про то, что выстрелов вверх меньше), но с заменой везде "вверх" и "вниз" симметрично, можно видеть, что "обратное направление" доказывает, что наоборот, выстрелов вниз меньше, чем выстрелов вверх. Это и есть противоречие, которое нам нужно, и после этого доказательство завершено. Это может показаться немного сложным для понимания или "читерством", но продумайте эту идею симметрии и "размотки обратно" как следует, она работает.
Теперь мне осталось доказать, что выстрелов вверх (когда меняются соседями с большими номерами) меньше, чем выстрелов вниз (меняются соседями с меньшими номерами). Рассмотрим четыре ямки, идущие подряд, назовем их A B C D в этом порядке. Предположим, что только что произошел выстрел вверх в орехе, который лежит в ямке C, и вот теперь в ямках лежат какие-то орехи примерно так:
A=? B=300 C=100 D=?
Я взял тут B=300 и C=100 для наглядности, на самом деле там могут быть любые номера, кроме того, что номер в B > номера в C, потому что это был выстрел ВВЕРХ. Я теперь хочу доказать следующие два утверждения:
Во-первых, больше уже никогда не выстрелит орех в ямке C. Это следует из НАБЛЮДЕНИЯ выше: в C сейчас лежит выстреливший орех, и туда может в будущем придти только выстреливший орех.
Во-вторых, когда орех в ямке B выстрелит, какой бы номер это ни был, это будет выстрел ВНИЗ. Почему это верно? Рассмотрим следующее свойство: "в B лежит невыстреливший орех, а в C лежит выстреливший орех". Это свойство верно прямо сейчас, но когда-нибудь оно станет неверным, потому что все орехи рано или поздно выстрелят. Однако орех в C уже никогда не выстрелит (только что доказано), а выстрелы в ямках A и D, хотя и могут заменить орехи в B и C на другие, сохраняют тот факт, что в B невыстреливший, а в C выстреливший (согласно НАБЛЮДЕНИЮ). Значит, это изменится только когда выстрелит орех в B, и в этот момент в C будет лежать уже выстреливший орех, т.е. меньший по номеру, чем в B. Значит, это будет выстрел ВНИЗ.
Для чего мне нужно было это техническое рассуждение? Я теперь могу сказать, что каждый выстрел вверх из какой-то ямки порождает две ямки - слева и справа от стреляющей - которые точно рано или поздно выстрелят вниз (в абзаце выше мы рассмотрели это для ямки слева, но для ямки справа работает точно такой же аргумент). Более того, выстрелившая вверх ямка уже никогда не выстрелит снова. Это не значит, однако, что выстрелов вниз в два раза больше, чем вверх - потому что каждая из этих "порожденных ямок справа и слева" может также быть "порождена" выстрелом вверх с другой стороны. Поэтому некоторые выстрелы вверх "порождают" два новых кандидата на выстрел вниз, некоторые только один, некоторые даже ноль, потому что их ямки слева и справа уже "порождены" предыдущими выстрелами вверх.
Мы можем, однако, оценить число выстрелов вниз с помощью графа. Каждый раз, когда стреляет ВВЕРХ орех из какой-то ямки, представьте себе, что мы проводим ребро, соединяющее ямки слева и справа от стреляющей. Обе вершины этого ребра когда-нибудь выстрелят ВНИЗ. Из-за того, что выстрелившая вверх ямка больше не стреляет, ребро создается только один раз. Иногда эти ребра присоединяются концами друг к другу. Если ребро появилось с двумя новыми кандидатами, то это тривиальный пример ДЕРЕВА (графа без циклов). Когда ребро присоединяется к существующей вершине (один новый кандидат), это расширяет дерево. Когда ребро соединяет два существующих кандидата, это соединяются вместе два дерева в одно. В общем случае по мере того, как происходят выстрелы вверх и создают новые ребра, мы получаем лес (набор деревьев из одного или больше). В любом дереве число вершин на 1 больше числа ребер, а если в лесу больше одного дерева, так тем более больше. Единственный способ для нашего леса перестать быть лесом - это если замкнется цикл из этих ребер. Каждое ребро соединяет ямки на расстоянии 2 друг от друга. Казалось бы, если обойти все ямки по кругу, есть надежда замкнуть цикл - но нам помогает то, что 2021 нечетное число, и после обхода по кругу мы попадем "между" начальных ребер, а не присоединяемся к ним. Полный цикл из таких ребер может быть только длиной 2021, но ясно, что не может быть, чтобы все 2021 шага были выстрелами вверх, так что это невозможно. Значит, мы всегда будем иметь в лучшем случае одно дерево, а то и несколько, и число вершин > числа ребер. Но число вершин это число гарантированных выстрелов вниз, а число ребер это число происшедших выстрелов вверх. Что и требовалось доказать.