3. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По какой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город 3?

Решение:

Для решения этой задачи будем считать количество путей, ведущих в каждый город, начиная от города А.

Город А: 1 путь (начальная точка).

Город Б: Из А ведет 1 путь. Итого: 1 путь.

Город Г: Из А ведет 1 путь. Итого: 1 путь.

Город В: Из Б ведет 1 путь. Из Г ведет 1 путь. Всего из В можно попасть в E. Из А в В напрямую пути нет. Итого: 1 путь (через Б).

Город Д: Из Б ведет 1 путь. Из В ведет 1 путь. Итого: 1 + 1 = 2 пути.

Город Е: Из В ведет 1 путь. Из Д ведет 2 пути. Всего из E можно попасть в Ж и З. Итого: 1 + 2 = 3 пути.

Город Ж: Из Е ведет 3 пути. Итого: 3 пути.

Город З: Из Е ведет 3 пути. Итого: 3 пути.

Посмотрим внимательно на рисунок:

• Пути из А: А → Б, А → Г.
• Из Б: Б → В, Б → Д.
• Из Г: Г → В.
• Из В: В → Д, В → Е.
• Из Д: Д → Е.
• Из Е: Е → Ж, Е → З.
• Из Ж: нет исходящих путей.

Теперь подсчитаем пути из А в З:

1. A → Б → В → Е → З
2. A → Б → В → Д → Е → З
3. A → Б → Д → Е → З
4. A → Г → В → Е → З
5. A → Г → В → Д → Е → З

Проверим еще раз. Пути из А:

1. А → Б → В → Е → З

2. А → Б → В → Д → Е → З

3. А → Б → Д → Е → З

4. А → Г → В → Е → З

5. А → Г → В → Д → Е → З

Ответ: 5.