Question

Кузнечики сидят на крайних левых 15 звеньях цепи длиной в M звеньев, по одному кузнечику на звене. Кузнечики играют в чехарду по таким правилам: перепрыгивать можно только вправо, только на свободное звено, и это должно быть либо соседнее звено с тем, на котором ранее сидел прыгающий кузнечик, либо через одно, если соседнее уже занято. При каком наименьшем M все кузнечики смогут сесть на цепи в обратном порядке без свободных звеньев между соседями?

Answer 1

Так как кузнечики не умеют прыгать влево, то понадобится хотя бы 29 звеньев для того, чтобы кузнечики сели в обратном порядке (все должны перепрыгнуть через 15-ого, так что понадобится как минимум 14 звеньев для того, чтобы их разместить). Докажем, что 29 звеньев не хватит. 15-ый кузнечик в таком случае должен будет остаться на своём месте, 14-ый либо останется, либо прыгнет на 16-ое место, так что 13-ый кузнечик не сможет через них перепрыгнуть, так как нельзя прыгать через двух кузнечиков. Докажем теперь, что 30 звеньев хватит. Сперва 15-ый кузнечик прыгает на 16-ое место, затем 13-ый прыгает на 18-ое..., в конце 1-ый прыгает на 30-ое место. Так как кузнечики прыгали только через кузнечиков, стоящих на чётных местах, не было случая, когда кузнечик не смог перепрыгнуть через двух подряд стоящих. Теперь все кузнечики стоят на чётных местах. После этого 2-ой прыгает на 29-ое место, 4-ый - на 27-ое место..., в конце 14-ый прыгает на 17-ое место. Все смогли перепрыгнуть, так как на пути до их места не было кузнечиков на нечётных местах.

Ответ: 30 звеньев.

Answer 2

Для решения этой задачи можно воспользоваться методом математической индукции.

Пусть мы уже знаем, что для цепи длиной M звеньев кузнечики могут сесть в обратном порядке без свободных звеньев между соседями. Рассмотрим цепь длиной M+1 звено. Первый кузнечик может занять самое правое звено, оставив цепь длиной M, и остальные кузнечики могут сесть в обратном порядке на оставшейся цепи в соответствии с предположением индукции. Если же первый кузнечик займет второе справа звено, то остальные кузнечики могут занять свои места на цепи длиной M-1, начиная со второго звена слева. Таким образом, для цепи длиной M+1 звено мы можем найти минимальное значение M, при котором кузнечики могут сесть в обратном порядке без свободных звеньев между соседями, следующим образом:

1. Если первый кузнечик займет самое правое звено, то наименьшее значение M равно наименьшему значению M для цепи длиной M.
2. Если первый кузнечик займет второе справа звено, то наименьшее значение M равно наименьшему значению M для цепи длиной M-1.

Таким образом, мы можем рекурсивно вычислить наименьшее значение M для цепи длиной 15 звеньев. Начнем с M=1 и будем увеличивать M до тех пор, пока кузнечики не смогут сесть в обратном порядке без свободных звеньев между соседями. Если при каком-то значении M это возможно, то это и будет ответом на задачу.

Для M=1 кузнечики могут сесть в обратном порядке без свободных звеньев между соседями, так как цепь состоит только из одного звена. Для M=2 также возможно расположение кузнечиков без свободных звеньев между соседями: они могут занять звенья в порядке 2-1. Для M=3 такое расположение уже невозможно: если первый кузнечик займет крайнее правое звено, то второй кузнечик должен з