РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 11 № 5040 Добавить в вариант

Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 20 минут?

Спрятать решение

Решение.

После четного числа минут крот может находиться только в вершинах A и C. Обозначим через a_k и c_k число путей длины 2k, ведущих из A в A и из A в C соответственно. Заметим, что выполняются равенства $c_k плюс 1=a_k плюс 2 c_k$ и $a_k плюс 1=a_k плюс c_k.$ Отсюда

$c_k плюс 2=a_k плюс 1 плюс 2 c_k плюс 1=a_k плюс c_k плюс 2 c_k плюс 1=c_k плюс 1 минус 2 c_k плюс c_k плюс 2 c_k плюс 1=3 c_k плюс 1 минус c_k.$ $c_k плюс 2=a_k плюс 1 плюс 2 c_k плюс 1=a_k плюс c_k плюс 2 c_k плюс 1=$
$=c_k плюс 1 минус 2 c_k плюс c_k плюс 2 c_k плюс 1=3 c_k плюс 1 минус c_k.$

C₀	C₁	C₂	C₃	C₄	C₅	C₆	C₇	C₈	C₉	C₁₀	C₁₁	C₁₂	C₁₃	C₁₄	C₁₅
0	1	3	8	21	55	144	377	987	2584	6765	17711	46368	121393	317811	832040

Ответ: 6 765.

Аналоги к заданию № 4938: 4948 4998 5008 ...4948 4998 5008 5018 5040 5050 5226 Все

Олимпиада Университета Иннополис Innopolis Open, 10 класс, 1 тур (отборочный) 2 этап, 2019 год

Классификатор: Олимпиадная геометрия. Графы

Спрятать решение · Прототип задания · Помощь