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

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

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, учитель информатики

Для эффективной подготовки по информатике для каждого задания дан краткий теоретический материал для выполнения задачи. Подобрано свыше 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.

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

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

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

Открываем подписку на интерактивные тренажеры для подготовки к ЕГЭ 2016 года по информатике

Каждый обладающий картой Visa, MasterCard, кошельком Яндес.Деньги, и даже, имеющий положительный баланс на сотовом, может заказать 60 уникальных интерактивных анимаций для подготовки к ЕГЭ 2016 года по информатике не вставая из-за своего компьютера

Тренажер к задаче №26 демонстрационного варианта ЕГЭ 2015 г.
по информатике и ИКТ методом "Холмов и ям"

Самое простое решение задачи 26 или по старому С3
по информатике и ИКТ наглядным методом "Холмов и ям"

Пример решения задачи в случае увеличения камней в куче двумя способами "+1" и "*2"

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 22 или больше камней.
В начальный момент в куче было S камней, 1 <= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

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

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

Вопрос 1а.
Обратным ходом от "победы" определяем границы начальной выигрышной позиции: 22 – 1 = 21 и 22/2 = 11
Для любого числа, лежащего в границах данного диапазона справедлива следующая запись max0*2>= 22 или max0*2 > 21 (обводим данный диапазон сверху и обозначаем его как max0, что будет означать начальную выигрышную позицию или выигрыш за один ход)

1а) Петя выигрывает первым ходом при 11 <= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

Вопрос 1б. Для ответа на этот вопрос нужно найти позиции, условно назовем их min0 , из которых все возможные ходы ведут в начальную выигрышную позицию, отмеченную нами как max0 . Обратным ходом определяем «подозреваемые» позиции на min0 :
11/2=? нацело не делится, следовательно, такой позиции нет. Остается только S = 11-1=10
(но пока это только предполагаемый min0 , поэтому рисуем «яму» двумя чертами, что будет означать - не забыть о существовании 2х возможных ходов, которые нужно будет обязательно проверить!)

Проверяем предположение для S = 10 на min0. Эта проверка и послужит ответом на вопрос 1б
При S = 10 у Пети есть 2 хода, которыми он не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом:
Любой ход Пети «10+1=11» или 10*2=20 ведут в начальную выигрышную позицию Ваню, который, удвоив количество камней в куче, получает 22 или 40, что больше 21 и победа достанется Ване
Поэтому позицию S = 10 обводим снизу сплошной чертой (рисуем яму ) - min0 (начальный проигрыш или проигрыш за 1-й ход):

Ответ на вопрос 1б. может быть таким: При S = 10 у Пети есть 2 хода, которыми он не может выиграть, но при любом ходе Пети Ваня может выиграть своим первым ходом. Любой ход Пети «10+1=11» или «10*2=20» ведет в начальную выигрышную позицию Ваню, который, удвоив количество камней в куче, получает 22 или 40, что больше 21 и Ваня выигрывает

Вопрос 2 . Для того чтобы Петя гарантированно выиграл вторым ходом, т.е. оказался в позиции max0 , после хода Вани, ему необходимо своим первым ходом «посадить Ваню в яму ». Понятно, что таких позиций может быть две , значения которых находим обратным ходом и обязательно проверяем…
Первая подозрительная позиция «10-1=9»

S=9. Проверим данную позицию на гарантированность победы!
Если бы Петя играл в поддавки, он бы сделал ход «9*2 = 18» , но ему нужно выиграть, поэтому данный ход отбрасываем. Остается только «9+1 = 10», иВаня оказывается в «яме» - что приводит Петю к выигрышу вторым ходом вне зависимости от того, как сходит Ваня!

Вторая "подозрительная позиция" 10/2 = 5

S=5. Проверим данную позицию на гарантированность победы! Ход «5+1=6» , затягивает игру, поэтому его не рассматриваем (отбрасываем)
Остается только «5*2=10», иВаня оказывается в «яме» - что приводит Петю к выигрышу вторым ходом вне зависимости от того, как сходит Ваня!

Ответ 2 может быть таким:

При S = 5 и 9 Петя не может выиграть первым ходом, но он может выиграть вторым ходом и для этого ему достаточно из позиции S = 5 сделать ход «5*2 = 10», тем самым отправить Ваню в начальную проигрышную позицию или из позиции S = 9 отправить его в ту же позицию ходом «9+1=10»

Вопрос 3 . Ваня должен выиграть, следовательно, он должен оказаться на вершине max0 , это означает, что Петя непременно должен оказаться вmin0, куда его «посадит» Ваня изmax1 , анам остается найти такие позиции, из которых бы Петя однозначно попадал вmax1
Находим «подозрительные» позиции, которые могут привести Петю в max1 с помощью того же самого обратного хода:
9-1=8
9/2=? 9 на 2 не делится - отпадает
5-1=4
5/2=? 5 на 2 не делится - отпадает
Находим, что таких «подозрительных» позиций всего две, но их еще нужно проверить!

S=8. Проверим данную позицию на гарантированность проигрыша Пети!
Ход Пети 8+1=9 и Ваня выигрывает вторым ходом
Ход Пети 8*2=16 и Ваня выигрывает первым ходом
S=4. Проверим данную позицию на гарантированность проигрыша Пети!
Ход Пети 4+1=5 и он бы проиграл, но из этой позиции Пете выгоден ход 4*2=8, тем самым Ваня попадает в «яму» и проигрывает. Но нам нужно найти выигрышную стратегию Вани, поэтому позицию S=4 исключаем из претендентов и получаем окончательную «картину» :

3. В позиции S = 8 – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом, поскольку его победа зависит от хода Пети, поэтому у Вани есть стратегия выиграть либо первым, либо вторым ходом: Если Петя выбирает ход «+1», в куче становится 9 камней и Ваня выигрывает на 2-м ходу (см. ответ на вопрос 2). Если Петя выбирает ход «*2», Ваня выигрывает первым ходом, удвоив число камней в куче.

Полученный нами выше рисунок можно легко перерисовать в дерево игры, предварительно помечая красными линиями проигрышные ходы (толстая линия – «короткий ход » или «+1 », а тонкая – «длинный » или «*2 ») и зелеными – выигрышные. (красные толстые линии можно нарисовать горбами вверх, что будет совпадать с направлением «коротких» веток дерева игры)

Окончательно стратегическая картинка выигрыша Пети может выглядеть так:

С другими методами решения задач данного типа можно познакомиться здесь -