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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 60 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 30 камней и Петя утроит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 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) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.