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

Задача 2.1.1. Для ко­ди­ро­ва­ния букв О, К, Г, Д, Р ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). За­ко­ди­руй­те по­сле­до­ва­тель­ность букв ГО­РО­ДОК таким спо­со­бом и ре­зуль­тат за­пи­ши­те вось­ме­рич­ным кодом.

Задача 2.1.2. Для ко­ди­ро­ва­ния букв А, В, С, D ис­поль­зу­ют­ся трех­раз­ряд­ные по­сле­до­ва­тель­ные дво­ич­ные числа, на­чи­на­ю­щи­е­ся с 1 (от 100 до 111 со­от­вет­ствен­но). За­ко­ди­руй­те таким об­ра­зом по­сле­до­ва­тель­ность сим­во­лов CDAB и за­пи­ши­те ре­зуль­тат в шест­на­дца­те­рич­ном коде.

Задача 2.1.3. Все 5-буквенные слова, со­став­лен­ные из букв А, Н, П, за­пи­са­ны в ал­фа­вит­ном порядке. Вот на­ча­ло списка:

Задача 2.1.4. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Укажите номер первого слова, которое начинается с буквы У.

Задача 2.2.1. Сколько можно составить пятибуквенных слов, если используются только буквы A, B, C (каждая буква может повторяться несколько раз или не встречаться в слове вовсе).

Задача 2.2.2. Есть четыре флага разных цветов и четыре мачты. Сколько можно передать сообщений, если флаги вывешивать на мачты в разном порядке (на каждой мачте обязательно должен висеть один из флагов).

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

Задача 2.2.4. Сколько шестибуквенных слов можно составить из букв A,B,C,D, если буква A встречается в каждом слове ровно три раза, а остальные буквы могут присутствовать в любых количествах или не быть вообще.

Задача 2.2.5. В соревновании принимали участие 20 спортсменов. Какой объем памяти (бит) нужен, чтобы запомнить номера трех победителей?

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

Задача 2.2.7. В детскую игрушку «Набор юного шпиона» входят два одинаковых комплекта из четырех флажков различных цветов. Сколько различных тайных сообщений можно передать этими флажками, условившись менять выставленный флажок каждые пять минут и наблюдая за процессом 15 минут? Наблюдатель видит вынос первого флажка и две перемены флажка. При этом возможна смена флажка на флажок того же цвета.

Задача 2.2.8. Команды для некоторого устройства задаются тремя одинаковыми тумблерами. Сколько положений должно быть в тумблере, чтобы можно было закодировать 120 различных команд?

Задача 2.2.9. Метеостанция измеряет температуру в диапазоне от -8 до 8 с точностью 0,5 градусов. Сколько бит нужно, чтобы сохранить результаты одного измерения?

Задача 2.2.10. Какой объем памяти в байтах нужен, чтобы сохранить картинку размером 8X8 пикселей, при использовании палитры из 32   цветов?

Задача 2.2.11. Производится двухканальная звукозапись с частотой дискретизации 100 Гц. При записи использовались 256 уровней дискретизации. Запись длится 5 минут. Сколько байт требуется для сохранения звукозаписи?

Задача 2.2.12.  Производится од­но­ка­наль­ная (моно) зву­ко­за­пись с ча­сто­той дискретизации 48 кГц и глу­би­ной кодирования 16 бит. За­пись длится 2 минуты, ее ре­зуль­та­ты записываются в файл, сжа­тие данных не производится. Какое из при­ве­ден­ных ниже чисел наи­бо­лее близко к раз­ме­ру полученного файла, вы­ра­жен­но­му в мегабайтах?

Задача 2.2.13. B не­ко­то­рой стра­не ав­то­мо­биль­ный номер дли­ной 7 сим­во­лов со­став­ля­ют из за­глав­ных букв (ис­поль­зу­ют­ся толь­ко 33 раз­лич­ных буквы) и де­ся­тич­ных цифр в любом по­ряд­ке. Каж­дый такой номер в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством бай­тов (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов). Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 125 но­ме­ров.

Задача 2.2.14. Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?

Задача 2.2.15. Герасим составляет 7-буквенные коды из букв Г, Е, Р, А, С, И, М. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Герасим?

Задача 2.2.16. Левий составляет 5-буквенные коды из букв Л, Е, В, И, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕИ. Сколько различных кодов может составить Левий?

Задача 2.3.1. Для пе­ре­да­чи чисел по ка­на­лу с по­ме­ха­ми ис­поль­зу­ет­ся код про­вер­ки чет­но­сти. Каж­дая его цифра за­пи­сы­ва­ет­ся в дво­ич­ном пред­став­ле­нии, с до­бав­ле­ни­ем незначащих нулей до длины 4, и к по­лу­чив­шей­ся по­сле­до­ва­тель­но­сти до­пи­сы­ва­ет­ся сумма её эле­мен­тов по мо­ду­лю 2 (на­при­мер, если пе­ре­даём 23, то по­лу­чим по­сле­до­ва­тель­ность 0010100110). Опре­де­ли­те, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100000100110. Если фрагмент декодировать невозможно, обозначьте его буквой X.

Задача 2.3.2. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:

Задача 2.4.1. Какой объем информации в битах мы получим, кидая монетку два раза, если оба раза выпадет «орёл»?

Задача 2.4.2. На правильный тетраэдр (пирамиду из четырех правильных треугольников) нанесли числа 0, 1, 2, 3. Какой объем информации нужен, чтобы сохранить результат  одного кидания тетраэдра (грани, на которую он приземлится)?

Задача 2.4.3. Двое играют в «крестики-нолики» на поле 4 на 4 клетки. Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?

Задача 2.4.4. В кор­зи­не лежат чер­ные и белые шары. Среди них 18 чер­ных шаров. Со­об­ще­ние о том, что до­ста­ли белый шар, несет 2 бита информации. Сколь­ко всего шаров в корзине?

Задача 2.4.5. За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?

Задача 2.4.6. В закрытом ящике находятся 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?

Задача 2.5.1. Азбука Морзе поз­во­ля­ет кодировать сим­во­лы для со­об­ще­ний по радиосвязи, за­да­вая комбинацию точек и тире. Сколь­ко различных сим­во­лов (цифр, букв, зна­ков пунктуации и т. д.) можно закодировать, ис­поль­зуя код аз­бу­ки Морзе дли­ной не менее трёх и не более пяти сиг­на­лов (точек и тире)?

Задача 2.5.2.  Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех): К – 000, М – 10, А – 111, Р – 01, И – 101 . Из четырех сообщений в этом коде только одно прошло без ошибки и может быть корректно декодировано. Найдите его.

Задача 2.5.3.  Некоторые буквы русского алфавита закодировали неравномерным кодом (по две и три двоичные цифры): А – 010, Б – 111, В – 10, Г – 01, Д – 00. Напишите без пробелов букву, в которой для корректного декодирования нужно добавить третью цифру, и букву, в которой третья цифра избыточна для корректного декодирования.

Задача 2.5.4.  По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко пять букв: A, B, С, D, E. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, до­пус­ка­ю­щий од­но­знач­ное де­ко­ди­ро­ва­ние. Для букв A, B, C ис­поль­зу­ют­ся такие ко­до­вые слова:

A – 1, B – 010, C – 000.

Ука­жи­те крат­чай­шее ко­до­вое слово для буквы E, при ко­то­ром код будет до­пус­кать од­но­знач­ное де­ко­ди­ро­ва­ние. Если таких кодов не­сколь­ко, ука­жи­те код с наи­мень­шим чис­ло­вым зна­че­ни­ем.

Задача 2.5.5. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г – 110, И – 01, Т – 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН? 

Задача 2.6.1. Документ объемом 5 Мбайт можно передать с одного компьютера на другой двумя способами:

А) Сжать архиватором, передать архив по каналу связи, распаковать.

Б) Передать по каналу связи без использования архиватора.

Какой способ быстрее и насколько, если

– средняя скорость передачи данных по каналу связи составляет 2¹⁸ бит в секунду,

– объем сжатого архиватором документа равен 80% от исходного,

– время, требуемое на сжатие документа – 35 секунд, на распаковку – 3 секунды?

Задача 2.6.2. У Толи есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2¹⁹ бит в секунду. У Миши нет скоростного доступа в Интернет, но есть возможность получать информацию от Толи по низкоскоростному телефонному каналу со средней скоростью 2¹⁵ бит в секунду. Миша договорился с Толей, что тот будет скачивать для него данные объемом 5 Мбайт по высокоскоростному каналу и ретранслировать их Мише по низкоскоростному каналу.

Компьютер Толи может начать ретрансляцию данных не раньше, чем им будут получены первые 512 Кбайт этих данных. Каков минимальный возможный промежуток времени (в секундах) с момента начала скачивания Толей данных до полного их получения Мишей?

В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Задача 2.6.3.  Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 15 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 2 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б? В ответе запишите только целое число, единицу измерения писать не нужно.

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

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