Ярослав всегда мечтал увидеть небоскрёбы, потому что в его родном Томске их нет.

Question

Реши задание на изображении

Расшифровка фото нейросетью:
Задача о мечте
Ярослав всегда мечтал увидеть небоскрёбы, потому что в его родном Томске их нет. Ближайшим подходящим городом оказался Екатеринбург, там стоит 52-этажная высотка «Исеть». Ярослав составил несколько маршрутов от Томска до Екатеринбурга; по дороге он хочет заехать к бабушке в Петропавловск. Сколько возможных маршрутов составил Ярослав?
[Рисунок: направленный граф. Сверху: ЕКАТЕРИНБУРГ, ТЮМЕНЬ, ОМСК, НОВОСИБИРСК, ТОМСК; ниже: КУРГАН, КЕМЕРОВО; ниже: ПЕТРОПАВЛОВСК, ПАВЛОДАР; внизу: ЧЕЛЯБИНСК, КОСТАНАЙ. Стрелки: ТОМСК → НОВОСИБИРСК; ТОМСК → КЕМЕРОВО; НОВОСИБИРСК → ОМСК; НОВОСИБИРСК → КЕМЕРОВО; КЕМЕРОВО → ПАВЛОДАР; ОМСК → ПАВЛОДАР; ОМСК → ТЮМЕНЬ; ОМСК → КУРГАН; ОМСК → ПЕТРОПАВЛОВСК; ПАВЛОДАР → ПЕТРОПАВЛОВСК; ТЮМЕНЬ → ЕКАТЕРИНБУРГ; ПЕТРОПАВЛОВСК → КУРГАН; ПЕТРОПАВЛОВСК → КОСТАНАЙ; КУРГАН → ЕКАТЕРИНБУРГ; КУРГАН → ЧЕЛЯБИНСК; КОСТАНАЙ → ЧЕЛЯБИНСК; ЧЕЛЯБИНСК → ЕКАТЕРИНБУРГ.]

Answer

Ответ: 12 маршрутов.

Разделим путь на два участка: до Петропавловска и после Петропавловска.

По стрелкам схемы до Петропавловска ведут 4 цепочки:

1. Томск → Новосибирск → Омск → Петропавловск

2. Томск → Кемерово → Павлодар → Петропавловск

3. Томск → Новосибирск → Кемерово → Павлодар → Петропавловск

4. Томск → Новосибирск → Омск → Павлодар → Петропавловск

От Петропавловска до Екатеринбурга есть 3 цепочки:

1. Петропавловск → Курган → Екатеринбург

2. Петропавловск → Курган → Челябинск → Екатеринбург

3. Петропавловск → Костанай → Челябинск → Екатеринбург

Каждый из первых 4 маршрутов можно продолжить любым из 3 вторых, поэтому:

$$
4\cdot3=12
$$

Проверка: Петропавловск в каждой комбинации встречается один раз, а после него все пути независимо ведут в Екатеринбург.