Ломоносов, 2020, 9 класс, задача 2
Сколькими способами можно прочитать слово «РОТОР», двигаясь по буквам рисунка, если возвращаться по пути к пройденным буквам нельзя, а прочтения, отличающиеся только направлением, считаются одинаковыми?
Ответ
Ответ: .
Решение. Число способов прочтения, которые начинаются с верхней левой буквы «Р», равно , так как необходимо сделать шага по буквам и каждый шаг направлен вправо или вниз. Если вычеркнуть рассмотренную букву «Р», то остаётся подсчитать число оставшихся способов на рис. .
Рис. .
Рис. .
Рис. .
Рис. .
Зафиксируем теперь направление чтения: будем считать, что слово читается так, что первая буква «Р» в нём находится не ниже последней. Для правой верхней буквы «Р» получаем способа. Вычеркнем эту букву (рис. ) и рассмотрим следующую букву «Р». Число способов прочтения, начинающихся с неё, равно . Вычеркнем и эту букву, а также буквы «О», рядом с которыми не осталось ни одной буквы «Р», так как больше нет способов прочтения, содержащих эти буквы «О» (рис. ). Следующая буква «Р» находится в такой же позиции, что и предыдущая, поэтому с неё начинается также возможных способа. Наконец, вычеркнем её и расположенную выше букву «О» (рис. ). Тогда остаётся всего способ прочтения.
Итого получаем способов.