Профильная информатика:
подготовка к ЕГЭ и олимпиадам

1 2 3 4 5 6 7 8 9 10^Р 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Схема дорог, связывающая \(n\) городов, имеет следующую структуру: из любого города \(v_{i}\) с номером \(1\leq i<n\) существует дорога в любой город \(v_{j}\), имеющий номер \(i<j\leq n\). По каждой дороге можно двигаться только в одном направлении — из города \(v_{i}\) в город \(v_{j}\) (на схеме показано стрелкой).

Пример такой схемы при \(n=6\) представлен на рисунке.

Сколько существует различных путей из города \(v_{1}\) в город \(v_{n}\), если \(n=10\)?

Решение

По индукции можно вывести формулу \(m=2^{n-2}\).

Подробнее...