Задания
Версия для печати и копирования в MS Word
Тип 9 № 18263
i

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

Спрятать решение

Ре­ше­ние.

Ко­ли­че­ство путей до го­ро­да X  =  ко­ли­че­ство путей до­брать­ся в любой из тех го­ро­дов, из ко­то­рых есть до­ро­га в Х.

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

С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов:

А = 1;

Б = А = 1;

В = А + Б = 1 + 1 = 2;

Д = А = 1;

Г = А + В = 1 + 2 = 3;

Е = Б + В = 1 + 2 = 3;

Ж = Г + Д = 3 + 1 = 4;

З = В + Г + Е + Ж = 2 + 3 + 3 + 4 = 12;

И = Е = 3;

К = Ж = 4;

Л = Е + Ж + З + И + К = 3 + 4 + 12 + 3 + 4 = 26.

 

Ответ: 26.

Раздел кодификатора ФИПИ: 2.5.2 Диа­грам­мы, планы, карты.