Разделы 
Дополнительно
Задача по математике - 13096
2023-06-23 
Евклид Парацельсо Бомбаст Умбуджо пытается пополнить свою скудную профессорскую зарплату, участвуя в состязаниях на приз компании по производству мыла. В одном из таких соревнований требовалось определить число путей, двигаясь по которым на данной диаграмме можно было бы прочитать слово $МAТНЕМАТIСIАN$: Умбуджо насчитал 1587 путей, начинающихся в одной из первых пяти строк. Когда подошло время сообщить результаты, он был весьма озадачен, чтобы не сказать больше. Помогите профессору сосчитать все пути, используя как можно меньше вычислений.
Решение:
Можно прокладывать путь, двигаясь «назад» от $N$. Если мы рассмотрим левую половину диаграммы, включая и центральный столбец, то при каждом шаге назад у нас есть выбор между двумя возможными направлениями, что дает нам $2^{12}$ путей. Удвоив это число и вычитая 1 (чтобы не сосчитать центральный столбец дважды), мы получим $2^{13} - 1 = 8191$ путь.
Евклид Парацельсо Бомбаст Умбуджо пытается пополнить свою скудную профессорскую зарплату, участвуя в состязаниях на приз компании по производству мыла. В одном из таких соревнований требовалось определить число путей, двигаясь по которым на данной диаграмме можно было бы прочитать слово $МAТНЕМАТIСIАN$: Умбуджо насчитал 1587 путей, начинающихся в одной из первых пяти строк. Когда подошло время сообщить результаты, он был весьма озадачен, чтобы не сказать больше. Помогите профессору сосчитать все пути, используя как можно меньше вычислений.
Решение:
Можно прокладывать путь, двигаясь «назад» от $N$. Если мы рассмотрим левую половину диаграммы, включая и центральный столбец, то при каждом шаге назад у нас есть выбор между двумя возможными направлениями, что дает нам $2^{12}$ путей. Удвоив это число и вычитая 1 (чтобы не сосчитать центральный столбец дважды), мы получим $2^{13} - 1 = 8191$ путь.
