Контрольные задания
Вопрос:

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

Фото задания: 9. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в…Фото задания

Ответ:

Решение:

Подсчитаем количество путей из города А в каждый город, двигаясь только вперед по стрелкам.

  • Из А:
    • А → А (1 путь)
  • В Б:
    • А → Б (1 путь)
  • В Г:
    • А → Г (1 путь)
  • В В:
    • А → Б → В (1 путь)
  • В Д:
    • А → Г → Д (1 путь)
  • В Е:
    • А → Б → В → Е (1 путь)
  • В Ж:
    • А → Г → Д → Ж (1 путь)
  • В З:
    • А → Г → З (1 путь)
  • В И:
    • А → Б → В → Е → И (1 путь)
  • В К:
    • А → Г → Д → Ж → К (1 путь)
  • В Л:
    • А → Б → В → Е → И → Л (1 путь)
    • А → Г → З → И → Л (1 путь)
    • А → Г → Д → Ж → К → Л (1 путь)
    • А → Г → Д → Ж → И → Л (1 путь)
    • А → Г → Д → И → Л (1 путь)

Подсчет путей:

Пути из А:

  • A: 1

Пути в Б:

  • A→Б: 1

Пути в Г:

  • A→Г: 1

Пути в В:

  • A→Б→В: 1

Пути в Д:

  • A→Г→Д: 1

Пути в Е:

  • A→Б→В→Е: 1

Пути в Ж:

  • A→Г→Д→Ж: 1

Пути в З:

  • A→Г→З: 1

Пути в И:

  • A→Б→В→Е→И: 1
  • A→Г→З→И: 1
  • A→Г→Д→Ж→И: 1

Пути в К:

  • A→Г→Д→Ж→К: 1

Пути в Л:

  • A→Б→В→Е→И→Л: 1
  • A→Г→З→И→Л: 1
  • A→Г→Д→Ж→К→Л: 1
  • A→Г→Д→Ж→И→Л: 1
  • A→Г→Д→И→Л: 1

Суммируем пути:

  • Город А: 1
  • Город Б: 1
  • Город Г: 1
  • Город В: 1 (из Б)
  • Город Д: 1 (из Г)
  • Город Е: 1 (из В)
  • Город Ж: 1 (из Д)
  • Город З: 1 (из Г)
  • Город И: 1 (из Е) + 1 (из З) + 1 (из Ж) = 3
  • Город К: 1 (из Ж)
  • Город Л: 1 (из И) + 1 (из К) = 1 + (1(из Ж)+1(из Д)) = 1 + 2 = 3

Пути в Л:

  • Из А в И: 3 пути
  • Из А в К: 1 путь

Пути в Л:

  • Путь через И: 3 пути (из А в И)
  • Путь через К: 1 путь (из А в К)

Пути к Л:

  • A → Б → В → Е → И → Л: 1
  • A → Г → З → И → Л: 1
  • A → Г → Д → Ж → И → Л: 1
  • A → Г → Д → Ж → К → Л: 1
  • A → Г → Д → И → Л: 1

Пересчитаем:

  • А: 1
  • Б: 1
  • Г: 1
  • В: 1
  • Д: 1
  • Е: 1
  • Ж: 1
  • З: 1
  • И: 1 (из Е) + 1 (из З) + 1 (из Ж) = 3
  • К: 1 (из Ж)
  • Л: 3 (из И) + 1 (из К) = 4

Посчитаем количество путей к каждому городу:

  • А: 1
  • Б: 1 (А→Б)
  • Г: 1 (А→Г)
  • В: 1 (А→Б→В)
  • Д: 1 (А→Г→Д)
  • Е: 1 (А→Б→В→Е)
  • Ж: 1 (А→Г→Д→Ж)
  • З: 1 (А→Г→З)
  • И: 1 (из Е) + 1 (из З) + 1 (из Ж) = 1 + 1 + 1 = 3
  • К: 1 (из Ж)
  • Л: 3 (из И) + 1 (из К) = 3 + 1 = 4

Ответ: 4