Контрольные задания
Вопрос:Фото задания: На рисунке - схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н. Сколько существует различных путей из пункта…Фото задания

Ответ:

Решение:

Будем считать количество путей, ведущих в каждую точку, начиная с А.

А: 1 путь

Б: 1 путь (А → Б)

В: 1 путь (А → В)

Г: 1 путь (А → В → Г)

Д: 2 пути (А → Б → Д, А → В → Д)

Ж: 2 пути (А → Б → Д → Ж, А → В → Д → Ж)

И: 2 пути (А → В → Г → И, А → В → Д → И)

К: 4 пути (А → Б → Д → Ж → К, А → В → Д → Ж → К, А → В → Г → И → К, А → В → Д → И → К)

Л: 3 пути (А → Б → Д → Ж → Л, А → В → Д → Ж → Л, А → В → Г → И → Л)

М: 4 пути (А → Б → Д → Ж → М, А → В → Д → Ж → М, А → В → Г → И → М, А → В → Д → И → М)

Н: 7 путей (К → Н, Л → Н, М → Н)

  • Пути через К: 4 пути → Н.
  • Пути через Л: 3 пути → Н.
  • Пути через М: 4 пути → Н.
  • Всего путей до Н: 4 + 3 + 4 = 11.

Теперь вычтем пути, проходящие через Е. Если путь проходит через Е, он должен идти из Д в Е.

Д → Е: 2 пути (А → В → Д → Е, А → Б → Д → Е)

Е → Ж: 2 пути (из Е в Ж)

Е → И: 2 пути (из Е в И)

Пути, проходящие через Е:

  • А → ... → Д → Е → Ж → ... → Н
  • А → ... → Д → Е → И → ... → Н

Считаем пути, которые проходят через Е:

  • А → В → Д → Е → Ж → К → Н (1 путь)
  • А → В → Д → Е → Ж → Л → Н (1 путь)
  • А → В → Д → Е → Ж → М → Н (1 путь)
  • А → В → Д → Е → И → К → Н (1 путь)
  • А → В → Д → Е → И → М → Н (1 путь)
  • А → Б → Д → Е → Ж → К → Н (1 путь)
  • А → Б → Д → Е → Ж → Л → Н (1 путь)
  • А → Б → Д → Е → Ж → М → Н (1 путь)
  • А → Б → Д → Е → И → К → Н (1 путь)
  • А → Б → Д → Е → И → М → Н (1 путь)

Всего путей, проходящих через Е: 10.

Общее количество путей до Н: 11.

Количество путей, проходящих через Е: 10.

Количество путей, не проходящих через Е: 11 - 10 = 1.

Проверка:

Пути из А в Н, не проходящие через Е:

  • А → Б → Д → Ж → К → Н
  • А → В → Д → Ж → К → Н
  • А → Б → Д → Ж → Л → Н
  • А → В → Д → Ж → Л → Н
  • А → Б → Д → Ж → М → Н
  • А → В → Д → Ж → М → Н
  • А → В → Г → И → К → Н
  • А → В → Г → И → М → Н

Всего 8 путей.

Пересчитаем пути из А в Н, не проходящие через Е:

А: 1

Б: 1 (А→Б)

В: 1 (А→В)

Г: 1 (А→В→Г)

Д: 2 (А→Б→Д, А→В→Д)

Ж: 2 (А→Б→Д→Ж, А→В→Д→Ж)

И: 1 (А→В→Г→И)

К: 2 (А→Б→Д→Ж→К, А→В→Д→Ж→К)

Л: 2 (А→Б→Д→Ж→Л, А→В→Д→Ж→Л)

М: 2 (А→В→Г→И→М, А→Б→Д→Ж→М)

Н: 2 + 2 + 2 = 6

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

А: 1

Б: 1

В: 1

Г: 1

Д: 2 (А->Б->Д, А->В->Д)

Ж: 2 (А->Б->Д->Ж, А->В->Д->Ж)

И: 1 (А->В->Г->И)

К: 3 (А->Б->Д->Ж->К, А->В->Д->Ж->К, А->В->Г->И->К)

Л: 2 (А->Б->Д->Ж->Л, А->В->Д->Ж->Л)

М: 3 (А->В->Г->И->М, А->Б->Д->Ж->М, А->В->Д->Ж->М)

Н: 3 + 2 + 3 = 8

Пути, не проходящие через Е:

А: 1

Б: 1

В: 1

Г: 1

Д: 2

Ж: 2

И: 1

К: 2 (через Ж)

Л: 2 (через Ж)

М: 3 (2 через Ж + 1 через И)

Н: 2 + 2 + 3 = 7

Ответ: 7