|
|
 |
Условие
На прямой сидит конечное число лягушек в различных целых точках. За ход ровно одна лягушка прыгает на 1 вправо, причём они по-прежнему должны быть в различных точках. Мы вычислили, сколькими способами лягушки могут сделать n ходов (для некоторого начального расположения лягушек). Докажите, что если бы мы разрешили тем же лягушкам прыгать влево, запретив прыгать вправо, то способов сделать n ходов было бы столько же.
Решение
Назовём шаблоном последовательность из n слов, каждое из которых "Налево" или "Направо", где k-е слово указывает, в каком направлении на k-м ходу могут прыгать лягушки. Докажем большее: количество способов из данной позиции сделать n ходов так, чтобы лягушки не запрыгивали друг на друга, не зависит от шаблона. Заметим, что это количество равно количеству финальных позиций (с учётом кратностей).
Лемма 1. Изменение последнего направления шаблона не меняет количество финальных позиций.
Доказательство. Рассмотрим произвольную позицию перед последним ходом. Каждая позиция разбивается на группы подряд сидящих лягушек. Количество финальных позиций, из неё получаемых, равно количеству групп, поскольку из каждой группы только одна лягушка может прыгнуть влево и одна – вправо. Поэтому общее количество финальных позиций не изменится.
Лемма 2. Замена двух соседних противоположных направлений шаблона не меняет набор финальных позиций.
Доказательство. Пусть два шаблона отличаются только в ходах k и k + 1. Рассмотрим произвольную позицию перед k-м ходом. Каждому способу по одному шаблону сделать из неё два прыжка разными лягушками соответствует способ для второго шаблона: те же лягушки прыгают в другом порядке. Поскольку они прыгают в разных направлениях, то это тоже допустимые прыжки. В обоих вариантах получается одна и та же позиция.Каждому же способу по одному шаблону сделать два прыжка одной лягушкой (туда и обратно) соответствует способ сделать два прыжка по второму шаблону лягушкой, находящейся на другом краю той же группы лягушек. Оба варианта не меняют позицию.
Следовательно, для этих двух шаблонов наборы позиций после k + 1 ходов одни и те же, а дальше эти шаблоны совпадают.
Осталось заметить, что с помощью операций, указанных в леммах, можно от любого шаблона перейти к любому другому: операциями из леммы 2 можно как угодно переставлять направления, а операциями из леммы 1 как угодно менять число направлений вправо.
Замечания
12 баллов
