Задания
Версия для печати и копирования в MS Word
Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями.
Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 30 минут?
Решение.
После четного числа минут крот может находиться только в вершинах A и C. Обозначим через ak и ck число путей длины 2k, ведущих из A в A и из A в C соответственно. Заметим, что выполняются равенства 
и 
Отсюда
| C0 | C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13 | C14 | C15 |
| 0 | 1 | 3 | 8 | 21 | 55 | 144 | 377 | 987 | 2584 | 6765 | 17711 | 46368 | 121393 | 317811 | 832040 |
Ответ: 832 040.
?
Олимпиада Университета Иннополис Innopolis Open, 10 класс, 1 тур (отборочный) 2 этап, 2019 годКлассификатор: Олимпиадная геометрия. Графы