Образовательный портал Павла Добряка

3. ГРАФЫ И ДЕРЕВЬЯ

Множество задач в ЕГЭ решаются с помощью графов (вершин, соединенных ребрами) и деревьев. С первой такой задачей мы уже познакомились в разделе «Кодирование» (неравномерный код и условие Фано). В этом разделе приведены задачи на графы и деревья в чистом виде. Но графы и деревья также являются полезным инструментом для решения задач в других разделах, например, для решения систем логических уравнений и задач на рекурсию.

3.1. Простые задачи на графы и деревья

Задача 3.1.1. На рисунке приведен граф (множество вершин, соединенных ребрами). Сколько существует путей из вершины А в K?

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

Задача 3.1.2. Между населёнными пунк­та­ми A, B, C, D, E, F по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых при­ве­де­на в таб­ли­це. (От­сут­ствие числа в таб­ли­це озна­ча­ет, что пря­мой до­ро­ги между пунк­та­ми нет.)

 

A

B

C

D

E

F

A

 

4

 

 

 

 

B

4

 

6

3

6

 

C

 

6

 

 

4

 

D

 

3

 

 

2

 

E

 

6

4

2

 

5

F

 

 

 

 

5

 

 

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми A и F (при усло­вии, что пе­ре­дви­гать­ся можно толь­ко по по­стро­ен­ным до­ро­гам).

Задача 3.1.3. На ри­сун­ке схема дорог изоб­ра­же­на в виде графа, в таб­ли­це со­дер­жат­ся све­де­ния о дли­нах этих дорог.

 

 

 

 

П1

П2

П3

П4

П5

П6

П7

П1

 

5

 

10

 

 

 

П2

45

 

 

40

 

55

 

П3

 

 

 

 

15

60

 

П4

10

40

 

 

 

20

35

П5

 

 

15

 

 

55

 

П6

 

55

60

20

55

 

45

П7

 

 

 

35

 

45

 

 

 

Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Опре­де­ли­те, ка­ко­ва длина до­ро­ги из пунк­та Д в пункт Е. В от­ве­те за­пи­ши­те целое число – так, как оно ука­за­но в таб­ли­це.

Задача 3.1.4. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

П1

П2

П3

П4

П5

П6

П7

П8

П1

3

23

П2

25

44

46

П3

25

П4

37

34

42

П5

34

24

28

П6

44

24

29

П7

42

28

29

3

П8

23

46

31

 

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число.

Задача 3.1.5. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

 

 

П1

П2

П3

П4

П5

П6

П7

П1

 

 

7

 

13

12

 

П2

 

 

 

 

5

 

10

П3

7

 

 

 

15

6

11

П4

 

 

 

 

 

10

 

П5

13

5

15

 

 

 

8

П6

12

 

6

10

 

 

 

П7

 

10

11

 

8

 

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Укажите кратчайший путь из пункта А в пункт К. В ответе перечислите все населённые пункты, через которые проходит путь. Например, путь из Г в Д через Е и К записывается как ГЕКД.

Задача 3.1.6. Пу­те­ше­ствен­ник при­шел в 08:00 на ав­то­стан­цию по­сел­ка ЛЕС­НОЕ и уви­дел сле­ду­ю­щее рас­пи­са­ние ав­то­бу­сов:

 

От­прав­ле­ние из

При­бы­тие в

Время от­прав­ле­ния

Время при­бы­тия

Лес­ное

Озер­ное

07:45

08:55

Лу­го­вое

Лес­ное

08:00

09:10

По­ле­вое

Лес­ное

08:55

11:25

По­ле­вое

Лу­го­вое

09:10

10:10

Лес­ное

По­ле­вое

09:15

11:45

Озер­ное

По­ле­вое

09:15

10:30

Лес­ное

Лу­го­вое

09:20

10:30

Озер­ное

Лес­ное

09:25

10:35

Лу­го­вое

По­ле­вое

10:40

11:40

По­ле­вое

Озер­ное

10:45

12:00

 

Опре­де­ли­те самое ран­нее время, когда пу­те­ше­ствен­ник смо­жет ока­зать­ся в пунк­те ПО­ЛЕ­ВОЕ со­глас­но этому рас­пи­са­нию.

Задача 3.1.7. Во фраг­мен­те базы дан­ных представлены све­де­ния о род­ствен­ных отношениях. На ос­но­ва­нии приведённых дан­ных определите ID дяди Кор­зу­н П. А.

 

ID

Фа­ми­лия_И.О.

Пол

 

ID_Ро­ди­те­ля

ID_Ре­бен­ка

1072

Они­щен­ко А. Б.

Ж

 

1027

1072

1028

Они­щен­ко Б. Ф.

М

 

1027

1099

1099

Они­щен­ко И. Б.

М

 

1028

1072

1178

Они­щен­ко П. И.

М

 

1028

1099

1056

Они­щен­ко Т. И.

М

 

1072

1040

1065

Кор­зун А. И.

Ж

 

1072

1202

1131

Кор­зун А. П.

М

 

1072

1217

1061

Кор­зун Л. А.

М

 

1099

1156

1217

Кор­зун П. А.

Ж

 

1099

1178

1202

Зель­до­вич М. А.

М

 

1110

1156

1027

Ле­меш­ко Д. А.

Ж

 

1110

1178

1040

Ле­меш­ко В. А.

Ж

 

1131

1040

1046

Месяц К. Г.

М

 

1131

1202

1187

Лу­ки­на Р. Г.

Ж

 

1131

1217

1093

Фокс П. А.

Ж

 

1187

1061

1110

Друк Г. Р.

Ж

 

1187

1093

 

Задача 3.1.8. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите количество человек, у которых есть брат с разницей не более чем в 5 лет.

 

Таблица 1

 

ID

Фамилия_И. О.

Пол

Год рождения

2053

Сухорук К.К.

М

1975

2065

Лопухова В.А.

Ж

1980

2086

Зарецкий А.А.

М

1972

097

Сухорук Е.К.

Ж

2007

2118

Ларина О.Д.

Ж

1996

2124

Сухорук И.К.

М

2001

2

35

Кольцова Т.Х.

Ж

1995

2156

Рац А.П.

М

1993

2181

Сухорук Т.Н.

М

2015

2203

Сухорук П.И.

Ж

2018

2052

Гнатюк О.А.

М

1952

 

Таблица 2

ID_Родителя

ID_Ребенка

2065

2097

2053

2118

2052

2065

2052

2086

2053

2135

2052

2053

2065

2124

2086

2156

2156

181

2156

2203









Подробнее

3.2. Количество программ и чисел

Задача 3.2.1. Исполнитель может выполнять только две команды, которым присвоены номера:

  1. Прибавь 1
  2. Возведи во вторую степень

Напишите самую короткую программу, которая из числа 1 получает 37. Если таких программ несколько, напишите любую из них.

Задача 3.2.2. У исполнителя «Троечник» две команды, которым присвоены номера:
1. прибавь 3,
2. умножь на 3.
Первая из этих команд увеличивает число на экране на 3, вторая умножает его на 3. Программа - это последовательность номеров команд. Например, 121 - это программа прибавь 3, умножь на 3, прибавь 3. Эта программа преобразует число 1 в число 15. 
Запишите программу, которая преобразует число 6 в число 69 и содержит не более 5 команд. Если таких программ более одной, то запишите любую из них.

Задача 3.2.3. Исполнитель может выполнять только две команды, которым присвоены номера:

  1. Прибавь 1
  2. Умножь на 2

Сколько есть программ, которые число 1 преобразуют в число 21?
Задача 3.2.4. Исполнитель может выполнять только две команды, которым присвоены номера:

  1. Прибавь 1
  2. Прибавь 2

Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 4 команд?
Задача 3.2.5. Исполнитель может выполнять только две команды:

  1. Прибавь 3
  2. Вычти 2

Если в ходе вычислений появляется отрицательное число, то оно не выводится. Сколько различных чисел можно получить из числа 2 с помощью программ, которые содержат ровно 18 команд?
Задача 3.2.6. У исполнителя Калькулятор две команды: 
1. умножь на 15,
2. подели на 2.
Первая из них увеличивает число на экране в 15 раз, вторая – уменьшает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 4096 с помощью программы, которая содержит ровно 12 команд?

Задача 3.2.7. У исполнителя Калькулятор две команды: 
1. прибавь 2
2. прибавь 3.
 Первая из них увеличивает число на экране на 2, вторая — на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?

Задача 3.2.8. Исполнитель может выполнять только три команды:

  1. Прибавь 2
  2. Прибавь 4
  3. Прибавь 5

Сколько есть программ, которые число 31 преобразуют в число 51?
Задача 3.2.9. Исполнитель Фибо преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.
Программа для исполнителя Фибо — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 3 в число 20, и при этом траектория вычислений содержит число 9 и не содержит числа 15?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 9, 10, 12.

Подробнее

3.3. Задачи на теорию игр

Задача 3.3.1. Два игрока, Петя и Валя, иг­ра­ют в сле­ду­ю­щую игру. Перед ними лежат две кучки камней, в пер­вой из ко­то­рых 4, а во вто­рой - 3 камня. У каж­до­го иг­ро­ка не­огра­ни­чен­но много камней. Иг­ро­ки ходят по очереди, пер­вый ход де­ла­ет Петя. Ход со­сто­ит в том, что игрок или утра­и­ва­ет число кам­ней в какой-то куче, или до­бав­ля­ет 1 ка­мень в какую-то кучу. Игра за­вер­ша­ет­ся в тот момент, когда общее ко­ли­че­ство кам­ней в двух кучах ста­но­вит­ся не менее 20. Если в мо­мент за­вер­ше­ния игры общее число кам­ней в двух кучах не менее 35, то вы­иг­рал Валя, в про­тив­ном слу­чае - Петя. Кто вы­иг­ры­ва­ет при без­оши­боч­ной игре обоих игроков? Укажите стра­те­гию вы­иг­ры­ва­ю­ще­го иг­ро­ка - какой ход он дол­жен сде­лать в каж­дой из позиций, ко­то­рые могут ему встре­тить­ся при пра­виль­ной игре. Докажите, что опи­сан­ная стра­те­гия - выигрышная.

Задача 3.3.2. Два игрока, Петя и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или увеличить количество камней в куче в два раза. Игра завершается тогда, когда количество камней в куче становится ≥ 33. В начальный момент в куче было S камней: 1 ≤ S ≤ 32.

Задача 3.3.3. Задание такое же, как и в предыдущей задаче. Ходы: +2, +3, *2.

Конец игры ≤ 30. В начальный момент в куче было S камней: 1 ≤ S ≤ 29.

Задача 3.3.4. Два игрока, Петя и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может (1) добавить в кучу один камень или (2) увеличить количество камней в куче в два раза или (3) увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 30 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 60 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 30 камней и Петя утроит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было камней, 1 ≤ S ≤ 35. 

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при разной игре противника. 

Выполните следующие задания.

1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.

б) У кого из игроков есть выигрышная стратегия при S = 31, 32, 33, 34? Опишите выигрышные стратегии для этих случаев.

2. У кого из игроков есть выигрышная стратегия при S = 11? Опишите соответствующие выигрышные стратегии.

3. У кого из игроков есть выигрышная стратегия при S = 10? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции.

Задача 3.3.5. Два игрока, Петя и Валя, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 55. Победителем считается игрок, сделавший последний ход, то есть этим ходом достигший 55 камней или более.

В начальный момент в первой куче было 5 камней, во второй 1 ≤ S ≤ 49  

Задание 1. Укажите все значения S, при которых Петя может выиграть за один ход.

Задание 2. Сколько существует значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом?

Задание 3. Укажите такое значение S, при котором одновременно выполняются два условия:

у Вали есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

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

Задача 3.3.6. Два игрока, Петя и Валя, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. 

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при разной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.











Подробнее