Егэ по информатике 26 задание с буквами. Баллы за задания по информатике

Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 31 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 30.

Решение.

1. а) Паша может выиграть, если S = 21, ..., 30. При меньших значениях S за один ход нельзя получить кучу, в которой больше 30 камней. Паше достаточно увеличить количество камней на 10. При S 1. б) Вова может выиграть первым ходом (как бы ни играл Паша), если исходно в куче будет S = 20 камней. Тогда после первого хода Паши в куче будет 21 камень или 30 камней. В обоих случаях Ваня увеличивает количество камней на 10 и выигрывает в один ход.

2.  Возможные значения S: 10, 19. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 20 камней (при S=10 он увеличивает количество камней на 10; при S=19 - добавляет 1 камень). Эта позиция разобрана в п. 1 б. В ней игрок, который будет ходить (теперь это Вова), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.

3. Возможное значение S: 18. После первого хода Паши в куче будет 19 или 28 камней. Если в куче станет 28 камней, Вова увеличит количество камней на 10 и вы играет своим первым ходом. Ситуация, когда в куче 19 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Вова), выигрывает своим вторым ходом.

Гость 26.05.2014 12:31

Пункт 3. А как же ситуация, когда в кучке будет из­на­чаль­но 9 камней. После хода Паши кам­ней ста­но­вить­ся либо 10, либо 19, Вася до­би­ва­ет до 20 и даль­ше по пунк­ту 1.б.

Константин Лавров

Да, 9 - тоже является правильным ответом. Достаточно указать хотя бы одно верное значение.

Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 40.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

б) Укажите такое значение S. при котором Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.

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

3. Укажите значение S, при котором у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, однако у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вовы. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход, в узлах - количество камней в куче.

Решение.

1. а) Паша может выиграть, если S = 31, ..., 40. При меньших значениях S за один ход нельзя получить кучу, в которой больше 40 камней. Паше достаточно увеличить количество камней на 10. При S б) Вова может выиграть первым ходом (как бы ни играл Паша), если исходно в куче будет S = 30 камней. Тогда после первого хода Паши в куче будет 31 камень или 40 камней. В обоих случаях Ваня увеличивает количество камней на 10 и выигрывает в один ход.

2.  Возможные значения S: 20, 29. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 30 камней (при S = 20 он увеличивает количество камней на 10; при S = 29 добавляет 1 камень). Эта позиция разобрана в п. 1. б). В ней игрок, который будет ходить (теперь это Вова), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.

3. Возможное значение S: 28. После первого хода Паши в куче будет 29 или 38 камней. Если в куче станет 38 камней, Вова увеличит количество камней на 10 и вы играет своим первым ходом. Ситуация, когда в куче 29 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Вова), выигрывает своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Вовы. Заключительные позиции (в них выигрывает Вова) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).

Два иг-ро-ка, Петя и Ваня, иг-ра-ют в сле-ду-ю-щую игру. Перед ними лежат две кучки кам-ней, в пер-вой из ко-то-рых 2, а во вто-рой - 3 камня. У каж-до-го иг-ро-ка не-огра-ни-чен-но много кам-ней. Иг-ро-ки ходят по оче-ре-ди, пер-вый ход де-ла-ет Петя. Ход со-сто-ит в том, что игрок или утра-и-ва-ет число кам-ней в какой-то куче, или до-бав-ля-ет 4 камня в какую-то кучу. Игра за-вер-ша-ет-ся в тот мо-мент, когда общее число кам-ней в двух кучах ста-но-вит-ся не менее 31. Если в мо-мент за-вер-ше-ния игры общее число кам-ней в двух кучах не менее 40, то вы-иг-рал Петя, в про-тив-ном слу-чае - Ваня. Кто вы-иг-ры-ва-ет при без-оши-боч-ной игре обоих иг-ро-ков? Каким дол-жен быть пер-вый ход вы-иг-ры-ва-ю-ще-го иг-ро-ка? Ответ обос-нуй-те.

Решение.

Выигрывает Ваня.

Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделённые запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучах соответственно.

Таблица содержит все возможные варианты ходов первого игрока. Из неё видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.

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

Ответ обоснуйте.

Решение.

Выигрывает Петя, своим первым ходом он должен увеличить в 3 раза количество камней во второй куче. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучах соответственно.

Таблица содержит все возможные варианты ходов Васи. Из неё видно, что при любом его ответе у Пети имеется ход, приводящий к победе.

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

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 100.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

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

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

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани. Представьте его в виде рисунка или таблицы. Для каждого ребра дерева укажите, кто делает ход, для каждого узла - количество камней в позиции.

Решение.

1. а) Петя может выиграть, если S = 21, ..., 100. При меньших значениях S за один ход нельзя получить кучу, в которой больше 100 камней. Пете достаточно увеличить количество камней в 5 раз. При S 1. б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 20 камней. Тогда после первого хода Пети в куче будет 21 камень или 100 камней. В обоих случаях Ваня увеличивает количество камней в 5 раз и выигрывает в один ход.

2.  Возможные значения S: 4, 19. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 20 камней (при S = 4 он увеличивает количество камней в 5 раз; при S = 19 - добавляет 1 камень). Эта позиция разобрана в п. 1 б). В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.

3. Возможное значение S: 18. После первого хода Пети в куче будет 19 или 90 камней. Если в куче станет 90 камней, Ваня увеличит количество камней в 5 раз и выиграет своим первым ходом. Ситуация, когда в куче 19 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения допустимы).

Для эффективной подготовки по информатике для каждого задания дан краткий теоретический материал для выполнения задачи. Подобрано свыше 10 тренировочных заданий с разбором и ответами, разработанные на основе демоверсии прошлых лет.

Изменений в КИМ ЕГЭ 2020 г. по информатике и ИКТ нет.

Направления, по которым будет проведена проверка знаний:

• Программирование;
• Алгоритмизация;
• Средства ИКТ;
• Информационная деятельность;
• Информационные процессы.

Необходимые действия при подготовке :

• Повторение теоретического курса;
• Решение тестов по информатике онлайн ;
• Знание языков программирования;
• Подтянуть математику и математическую логику;
• Использовать более широкий спектр литературы – школьной программы для успеха на ЕГЭ недостаточно.

Структура экзамена

Длительность экзамена – 3 часа 55 минут (255 минут), полтора часа из которых рекомендовано уделить выполнению заданий первой части КИМов.

Задания в билетах разделены на блоки:

• Часть 1 - 23 задания с кратким ответом.
• Часть 2 - 4 задачи с развернутым ответом.

Из предложенных 23 заданий первой части экзаменационной работы 12 относятся к базовому уровню проверки знаний, 10 – повышенной сложности, 1 – высокому уровню сложности. Три задачи второй части высокого уровня сложности, одна – повышенного.

При решении обязательна запись развернутого ответа (произвольная форма).
В некоторых заданиях текст условия подан сразу на пяти языках программирования – для удобства учеников.

Баллы за задания по информатике

1 балл - за 1-23 задания
2 балла - 25.
З балла - 24, 26.
4 балла - 27.
Всего: 35 баллов.

Для поступления в технический вуз среднего уровня, необходимо набрать не менее 62 баллов. Чтобы поступить в столичный университет, количество баллов должно соответствовать 85-95.

Для успешного написания экзаменационной работы необходимо четкое владение теорией и постоянная практика в решении задач.

Твоя формула успеха

Труд + работа над ошибками + внимательно читать вопрос от начала и до конца, чтобы избежать ошибок = максимальный балл на ЕГЭ по информатике.

Сложность : высокая.
Примерное время решения : 20 минут
Тема: Математические основы программирования. Алгоритмы.
Подтема: Игры и стратегии
Что проверяется: Знание основных понятия, связанных с анализом игр с полной информацией. Умение определять выигрышные и проигрышные позиции.
Как может выглядеть задание? Например, так: Дано описание игры двух игроков с полной информацией. Нужно определить позиции, в которых указанный в условии игрок имеет выигрышную стратегию, позволяющую ему гарантированно выиграть в указанное количество ходов.

Как разбирать задачу.
Хороший разбор сделал К.Ю. Поляков в статье «ЕГЭ: новые стратегии (задача С3) » [Первое сентября. Информатика. 2013, январь. Стр. 22-27]. В статье есть много задач для самостоятельного решения. В статье есть только одна неточность: дерево, изображенное на стр.25, названо деревом «возможных вариантов игры». В контексте статьи понятно, о чем идет речь. Но при разборе статьи с учениками лучше уточнить: дерево возможных вариантов игры при выбранной стратегии Вани. Обычно деревом возможных вариантов игры (или просто деревом игры) называют дерево, изображающее все возможные партии. То есть, рассматриваются все возможные ходы Вани, а не только ходы, соответствующие определенной стратегии.

Замечание. Задача C3-2013 объединяет идеи задач C3-2011 и C3-2012. Преемственность с C3-2012 видна из разбора К.Ю.Полякова. См. также разбор C3-2012

Разбор 26 задания ЕГЭ 2017 года по информатике из демоверсии. Это задание из второй части высокого уровня сложности. Примерное время выполнения задания 30 минут. Максимальный балл за выполнение задания — 3.

Проверяемые элементы содержания:
— Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию.

Задание 26

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза . Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Если при этом в куче оказалось не более 30 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 17 камней и Паша удвоит количество камней в куче, то игра закончится, и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 19.

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

Выполните следующие задания.
1. а) При каких значениях числа S Паша может выиграть в один ход?
Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 18, 17, 16?
Опишите выигрышные стратегии для этих случаев.
2. У кого из игроков есть выигрышная стратегия при S = 9, 8? Опишите соответствующие выигрышные стратегии.
3. У кого из игроков есть выигрышная стратегия при S = 7? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

1. а) Паша может выиграть, если S = 19 или S = 10, 11, 12, 13, 14, 15. При S = 19 первым ходом нужно добавить в кучу один камень, при остальных указанных значениях S нужно удвоить количество камней.

б) При S = 16, 17 или 18 удваивать количество камней не имеет смысла, так как после такого хода выигрывает противник. Поэтому можно считать, что единственный возможный ход – это добавление в кучу одного камня.

При S = 18 после такого хода Паши в куче станет 19 камней. В этой позиции ходящий (т.е. Валя) выигрывает (смотрите пункт 1а) : при S = 18 Паша (игрок, который должен ходить первым) проигрывает.

Выигрышная стратегия есть у Вали.

При S = 17, после того как Паша своим первым ходом добавит один камень, в куче станет 18 камней. В этой позиции ходящий (т.е. Валя) проигрывает (смотрите выше) : при S = 17 Паша (игрок, который должен ходить первым) выигрывает. Выигрышная стратегия есть у Паши.

При S = 16 выигрышная стратегия есть у Вали. Действительно, если Паша первым ходом удваивает количество камней, то в куче становится 32 камня, и игра сразу заканчивается выигрышем Вали. Если Паша добавляет один камень, то в куче становится 17 камней. Как мы уже знаем, в этой позиции игрок, который должен ходить (т.е. Валя), выигрывает.

Во всех случаях выигрыш достигается тем, что при своём ходе игрок, имеющий выигрышную стратегию, должен добавить в кучу один камень.

Можно нарисовать деревья всех возможных партий для указанных значений S .
Другая возможность – (1) указать на то, что удваивать кучу не имеет смысла, и (2) последовательно сводить случай S = 18 к случаю S = 19, случай S = 17 – к случаю S = 18 и т.д.

2. При S = 9 или 8 выигрышная стратегия есть у Паши. Она состоит в том, чтобы удвоить количество камней в куче и получить кучу, в которой будет соответственно 18 или 16 камней. В обоих случаях игрок, который будет делать ход (теперь это Валя), проигрывает (смотрите пункт 1б) .

3. При S = 7 выигрышная стратегия есть у Вали. После первого хода Паши в куче может стать либо 8, либо 14 камней. В обеих этих позициях выигрывает игрок, который будет делать ход (теперь это Валя). Случай S = 8 рассмотрен в пункте 2 , случай S = 14 рассмотрен в пункте 1а .

В таблице изображено дерево возможных партий при описанной стратегии Вали. Заключительные позиции (в них выигрывает Валя) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).

Дерево всех партий, возможных при Валиной стратегии. Знаком >> обозначены позиции, в которых партия заканчивается.

В этой задаче наиболее сложная часть — это грамотно и логически корректно записать решение.

Итак, начнём с того, что попытаемся понять условие.

1. У нас есть две кучки камней и два игрока: первый (Петя) и второй (Ваня).
2. Игроки ходят по очереди.
3. За ход в любую из кучек можно либо добавить один камень, либо увеличить количество камней в кучке в два раза.
4. Как только суммарно в кучке стало 73 или более камня, игра заканчивается.
5. Тот, кто ходил последним, выиграл.

Важные замечания

1. Мы будем в некоторых заданиях строить дерево партий. Мы это обязаны делать согласно условию только в Задании 3. В Задании 2 мы не обязаны строить дерево партий.
2. В каждом из заданий недостаточно просто сказать, кто имеет выигрышную стратегию. Требуется также описать её и указать возможное количество шагов, которое потребуется для выигрыша.
3. Недостаточно назвать стратегию выигрышной. Нужно доказать , что она приводит к выигрышу. Даже очевидные утверждения требуют доказательств.

Задание 1.

Рассмотрим теперь Задание 1. В кучках — (6, 33) камней (первая часть Задания 1) и (8, 32) камней (вторая часть Задания 1). Нам нужно определить, у кого из игроков имеется выигрышная стратегия. Иными словами, кто из игроков при правильной игре обязательно выиграет вне зависимости от действий соперника.

Здесь и далее мы будем решение разбивать на две части. Вначале будет идти предварительное объяснение (его писать в ЕГЭ не нужно), а затем — "формальное решение", то есть то, что нужно писать в самом бланке ЕГЭ.

Обсуждение.

Давайте подумаем: первый игрок очевидно в один ход выиграть не может, так как что бы он не делал, суммарно 73 не будет. Самое "большое" действие, которое он может сделать, — это увеличить в 2 раза количество камней во второй кучке, сделав их 66. Но (6, 66) — это 72 камня, а не 73. Значит, первый в один ход явно выиграть не сможет. Однако второй — вполне сможет. Первый может сделать потенциально четыре действия: прибавить 1 к первой кучке, увеличить в 2 раза количество камней в первой кучке, прибавить 1 ко второй кучке, увеличить в 2 раза количество камней во второй кучке. Посмотрим, к чему это приведёт:

• (6,33) -> (7,33). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (7, 66). Суммарно — 73. Значит, второй выигрывает.
• (6,33) -> (12, 33). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (12, 66). Суммарно — 78. Значит, второй выигрывает.
• (6,33) -> (6,34). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (6, 68). Суммарно — 74. Значит, второй выигрывает.
• (6,33) -> (6,66). В этом случае второй игрок может увеличить в 2 раза количество камней во второй кучке. Получим (6, 132). Суммарно — 138. Значит, второй выигрывает.

Итого: как бы себя не вёл первый игрок, второй выиграет и в один ход.

Аналогично решается и с (8,32).

Формальное решение Задания 1.

Второй игрок имеет выигрышную стратегию. Докажем это и покажем эту стратегию. Для этого построим дерево партии для каждой из начальных позиции. В дереве партий мы будем указывать состояние обеих кучек в формате (a,b), где a — количество камней в первой кучке, b — количество камней во второй кучке. При ходе первого игрока мы будем рассматривать четыре возможных варианта его поведения: прибавить 1 к первой кучке, увеличить в 2 раза количество камней в первой кучке, прибавить 1 ко второй кучке, увеличить в 2 раза количество камней во второй кучке. Для второго игрока мы укажем по одному ходу, приводящему к выигрышу. Ходы будем показывать в виде стрелочек, рядом с которыми писать I в случае хода первого и II в случае хода второго.

Дерево партий для начальной позиции (6, 33).

Дерево партий для начальной позиции (8, 32).

Согласно дереву партий, вне зависимости от ходов первого у второго всегда есть выигрышная стратегия, позволяющая ему выиграть в один ход, описанная в деревьях (суммы после ходов Вани составляют слева-направо 73, 80, 74 и 136 соответственно). При этом, согласно дереву партий, второй игрок может выиграть ровно за один ход.

Задание 2

Формальное решение

Рассмотрим начальную позицию (6,32). Заметим, что она близка к (6,33) из Задания 1. В Задании 1 мы выяснили, что в позиции (6, 33) выигрывает второй, причём в один ход. Можно это условие переформулировать: в позиции (6,33) выигрывает в один ход тот, кто не ходит (то есть, ходит вторым). Или, иными словами, тот, кто ходит, проигрывает в один ход.

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

Аналогично в позиции (7, 32). Петя своим первым ходом добавляет +1 камень в первую кучку, получая позицию (8, 32). В этой позиции согласно тем же рассуждениям, тот, кто ходит, проигрывает. Будет ход Вани, поэтому Ваня проиграет. Выигрышная стратегия Пети заключается в следующем: Петя добавляет +1 камень в первую кучку, а затем следует стратегии Вани из Задания 1.

Аналогично в позиции (8, 31). Петя своим первым ходом добавляет +1 камень во вторую кучку, получая позицию (8, 32). В этой позиции согласно тем же рассуждениям, тот, кто ходит, проигрывает. Будет ход Вани, поэтому Ваня проиграет. Выигрышная стратегия Пети заключается в следующем: Петя добавляет +1 камень во вторую кучку, а затем следует стратегии Вани из Задания 1.

Задание 3

Обсуждение

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

Формальное решение

В начальной позиции (7, 31) выигрывает Ваня в один или два хода. Докажем это. Для этого построим дерево всех партий.

Дерево всех партий для начальной позиции (7, 31).

Согласно дереву всех партий Ваня выигрывает либо в один ход (в случае, если Петя увеличил в два раза количество камней в первой или второй кучках), либо в два хода (если Петя увеличил на 1 количество камней в первой или второй кучках).

Таким образом, в начальной позиции (7, 31) у Вани имеется выигрышная стратегия, при этом Ваня выиграет в один или два хода.

Евгений Смирнов

Эксперт в IT, учитель информатики