На рисунке изображена схема дорог, связывающих гороA, B, C, D, E, F, G, H, I, J, К. По каждой дороге можно двигатьтолько в одном направлении, указанном стрелкой. Скольсуществует различных путей из города А в город К?

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

Начнем с города А. Из города А можно попасть в города B, C, D, F, G.

• Количество путей в город B: 1
• Количество путей в город C: 1
• Количество путей в город D: 1
• Количество путей в город F: 1
• Количество путей в город G: 1

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

• Из города B можно попасть только в город F. Количество путей в город F через B: 1 (путь A → B → F)
• Из города C можно попасть только в город D. Количество путей в город D через C: 1 (путь A → C → D)
• Из города D можно попасть в города E и H. Количество путей:
  • в город E через D: 1 (путь A → D → E)
  • в город H через D: 1 (путь A → D → H)
• Город F ведет в города G и J. Количество путей:
  • в город G через F: 1 + 1 = 2 (путь A → F → G и путь A → B → F → G)
  • в город J через F: 1 + 1 = 2 (путь A → F → J и путь A → B → F → J)
• Город G ведет в города H и I. Количество путей:
  • в город H через G: 1 + 2 = 3 (путь A → G → H и путь A → F → G → H и путь A → B → F → G → H)
  • в город I через G: 1 + 2 = 3 (путь A → G → I и путь A → F → G → I и путь A → B → F → G → I)
• Из города E можно попасть в город H. Количество путей в город H через E: 1 (путь A → D → E → H)
• В город H можно попасть из E, D, G. Общее количество путей в город H: 1 + 1 + 3 = 5
• В город I можно попасть только из города G. Количество путей в город I: 3
• В город J можно попасть из городов F и I. Общее количество путей в город J: 2 + 3 = 5
• В город H можно попасть из городов D, E, G. Общее количество путей в город H: 1 + 1 + (1+1) = 4. А также есть путь из E, то есть + 1. Итого 5.
• В город K можно попасть из городов H и J. Общее количество путей в город K: 5 + 5 = 10

Всего получается 16 путей из города A в город K.

Ответ: 16