Задание 15. Знание основных понятий и законов математической логики: все задания

Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).

Версия для печати

1. Задание#T30251

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П.

Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Е и при этом не проходящих через пункт Л?

Показать разбор и ответ

Рассмотрим пути из А в Е. Количество путей, ведущих в каждый пункт, равно сумме путей, ведущих в пункты, из которых можно попасть в данный. Буквами Б, В, …, Е будем обозначать количество путей из А в соответствующий пункт.

Б = А = 1

В = А = 1

Г = А + Б + В = 1 + 1 + 1 = 3

Д = Б + Г = 1 + 3 = 4

Е = Г + Д = 3 + 4 = 7

Если исключить из схемы пункт Л (через него по условию путь проходить не должен), то из Е в П остаётся два пути: ЕИКМП и ЕКМП.

Таким образом, из А в Е существует 7 путей, из Е в П (без захода в Л) – 2 пути. На каждом из участков маршрута можно выбрать путь независимо от другого участка, поэтому всего получается 7 · 2 = 14 путей.

Ответ: 14

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 13 тыс. раз. С ним справились 42% пользователей.

2. Задание#T30168

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П.

Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Г и при этом не проходящих через пункт Е?

Показать разбор и ответ

Из А в Г можно пройти тремя способами: АГ, АБГ, АВГ.

Рассмотрим пути из Г, не проходящие через Е. Количество путей, ведущих в каждый пункт, равно сумме путей, ведущих в пункты, из которых можно попасть в данный. Буквами Д, Ж, …, П будем обозначать количество путей из Г в соответствующий пункт.

Д = Г = 1

Ж = Д = 1

И = Г = 1

К = И = 1

Л = Д + Ж = 1 + 1 = 2

М = К + Л = 1 + 2 = 3

Н = Ж + Л = 1 + 2 = 3

П = Л + М + Н = 2 + 3 + 3 = 8

Таким образом, из А в Г существует 3 пути, из Г в П (без захода в Е) – 8 путей. На каждом из участков маршрута можно выбрать путь независимо от другого участка, поэтому всего получается 3 ⋅ 8 = 24 пути.

Ответ: 24

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 7 тыс. раз. С ним справились 57% пользователей.

3. Задание#T29786

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П.

Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Е?

Показать разбор и ответ

Разделим весь путь на части: из А в Е, из Е в Л (в П нельзя попасть, минуя пункт Л), из Л в П.

Рассмотрим пути из А в Е. Количество путей, ведущих в каждый пункт, равно сумме путей, ведущих в пункты, из которых можно попасть в данный. Буквами будем обозначать количество путей из А в соответствующий пункт.

А = 1

Б = А = 1

В = А = 1

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

И = В + Г = 5

Е = Г + Д + И = 10

Из Е в Л есть два пути: ЕЛ и ЕКЛ, из Л в П три пути: ЛП, ЛНП, ЛМП.

Путь на каждом из участков АЕ, ЕЛ и ЛП можно выбрать независимо от других участков, значит, общее количество путей равно 10 ⋅ 2 ⋅ 3 = 60.

Ответ: 60

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 5 тыс. раз. С ним справились 58% пользователей.

4. Задание#T29759

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П.

Сколько существует различных путей из пункта А в пункт П, проходящих через пункт И?

Показать разбор и ответ

Разделим весь путь на части: из А в И, из И в Л (в П нельзя попасть, минуя пункт Л), из Л в П.

Рассмотрим пути из А в И. Количество путей, ведущих в каждый пункт, равно сумме путей, ведущих в пункты, из которых можно попасть в данный. Буквами будем обозначать количество путей из А в соответствующий пункт.

А = 1

Б = А = 1

В = А = 1

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

Е = Г + Д = 5

И = В + Г + Е = 10

Из И в Л есть единственный путь ИКЛ, из Л в П три пути: ЛП, ЛНП, ЛМП. Путь на каждом из участков АИ, ИЛ и ЛП можно выбрать независимо от других участков, значит, общее количество путей равно 10 ⋅ 1 ⋅ 3 = 30.

Ответ: 30

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 4 тыс. раз. С ним справились 68% пользователей.

5. Задание#T9820

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

Сколько существует различных путей из города А в город П?

Показать ответ

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 6 тыс. раз. С ним справились 70% пользователей.

6. Задание#T9796

На рисунке представлена схема дорог, связывающих города

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

Сколько существует различных путей из города в город проходящих через город

Показать ответ

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 7 тыс. раз. С ним справились 64% пользователей.

7. Задание#T8646

На рисунке представлена схема дорог, связывающих города , , , , , , , , , , .

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

Сколько существует различных путей из города в город , проходящих через город ?

Показать ответ

Это задание решали 4 тыс. раз. С ним справились 80% пользователей.

8. Задание#T4907

На рисунке – схема дорог, связывающих пункты , , , , , , , , , , , .

Сколько существует различных путей из пункта в пункт , не проходящих через пункт ?

Показать разбор и ответ

Указание:

Разбейте путь на части – из в и из в , при этом удалив вершину и все пути, соединяющие её с другими вершинами.

Решение:

Схема устроена так, что путь обязательно пройдёт через город , поэтому его можно разделить на две части: из в , из в .

Пусть

– количество допустимых путей из пункта в пункт . Оно равно сумме количества путей из в каждый из пунктов, откуда есть прямая дорога в . Тогда получаем (пункт и связанные с ним дороги не рассматриваем):

(единственный способ попасть из в – остаться на месте)

Всего получается путей из в .

Из в можно пройти тремя путями:

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

пути.

Ответ: 33

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 7 тыс. раз. С ним справились 61% пользователей.

9. Задание#T4880

На рисунке – схема дорог, связывающих пункты , , , , , , , , , , , .

Сколько существует различных путей из пункта в пункт , не проходящих через пункт ?

Показать разбор и ответ

Указание:

Разбейте путь на части – из в , и из в , удалив вершину и все пути, соединяющие её с другими вершинами.

Решение:

Если удалить из схемы пункт , то из в можно пройти пятью способами:

Из в можно пройти тремя путями:

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

путей.

Ответ: 15

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 5 тыс. раз. С ним справились 64% пользователей.

10. Задание#T4853

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

Сколько существует различных путей из города А в город Н, проходящих через город Г?

Показать разбор и ответ

Указание:

Разбейте путь на части – из А в Г, из Г в К, из К в Н.

Решение:

Поскольку посещение города Г обязательно, путь из А в Н распадается на две части: из А в Г и из Г в Н. Кроме того, схема устроена так, что путь обязательно пройдёт через город К, поэтому получается три части: из А в Г, из Г в К, из К в Н.

Из А в Г можно пройти тремя путями: АБВГ, АВГ, АГ.

Из Г в К можно пройти тремя путями: ГЕЖК, ГЕИК, ГИК.

Из К в Н можно пройти двумя путями: КЛН, КМН.

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

путей.

Ответ: 18

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 5 тыс. раз. С ним справились 57% пользователей.

11. Задание#T4826

На рисунке изображена схема дорог, связывающих города , , , , , , , , , , , . По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город , проходящих через город ?

Показать разбор и ответ

Указание:

Разбейте путь на части – из в , из в , из в .

Решение:

Поскольку посещение города обязательно, путь из в распадается на две части: из в и из в . Кроме того, схема устроена так, что путь обязательно пройдёт через город , поэтому получается три части: из в , из в , из в .

Из в можно пройти тремя путями:

Из в можно пройти двумя путями:

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

путей.

Ответ: 18

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 6 тыс. раз. С ним справились 56% пользователей.

12. Задание#T2382

На рисунке — схема дорог, связывающих города , , , , , , . По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей, не содержащих циклов, из города в город ?

Показать разбор и ответ

2 аналогичных задания

Путь из в может лежать или не лежать через город . Рассмотрим оба случая.

Если путь лежит через E:
Разобьём путь из в на два этапа: сначала из в , потом из в .
1) Из в можно добраться 4 способами:

.
2) Из в можно добраться 3 способами:

.
Пути из в получаются комбинацией первых путей со вторыми (

).
Но нужно исключить пути c повторяющимися городами. Такой путь один:

(проходит дважды через город ).
Получается

путей.

Если путь не лежит через E:
Нужно добраться из в , не проходя через город . Тогда в можно попасть только из города , а в — только из города .
Получается путь (

).

Итого:

путей.

Ответ: 12

Это задание взято из Яндекс.ЕГЭ

Это задание решали 3 тыс. раз. С ним справились 17% пользователей.

13. Задание#T2370

На рисунке — схема дорог, связывающих города , , , , , , , , , , . По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город ?

Показать ответ

Это задание взято из Яндекс.ЕГЭ

Это задание решали 1 тыс. раз. С ним справились 70% пользователей.

14. Задание#T2356

На рисунке — схема дорог, связывающих города , , , , ,

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

Сколько существует различных путей из города в город ?

Показать ответ

Это задание взято из Яндекс.ЕГЭ

Это задание решали 1 тыс. раз. С ним справились 64% пользователей.

15. Задание#T2344

На рисунке — схема дорог, связывающих города , , , , , , , , , , , , , . По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город ?

Показать ответ

Это задание взято из Яндекс.ЕГЭ

Это задание решали 1 тыс. раз. С ним справились 65% пользователей.

0 баллов сегодня

дней без пропуска

вс

пн

вт

ср

чт

пт

сб