Перекладывание камней одна куча —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#14217

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

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет 33 или более камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 32.$

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

Известно, что Петя выигрывает в первый ход. Укажите минимальное значение $S,$ когда такая ситуация возможна.

Показать ответ и решение

Чтобы Петя победил своим первым ходом, он должен увеличить количество камней в куче на столько, чтобы их стало больше или равно 33. Эффективнее Пете будет удваивать $S,$ чем добавлять к нему 1. При каких $S$ будет выполняться $2 ⋅S >= 33$ ? При $S ≥ 17.$ Следовательно ответ $17.$

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 2#14218

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинания.

Показать ответ и решение

Петя может выиграть своим первым ходом при $S ≥ 17.$ Таким образом, если мы возьмем $S = 16,$ то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Но нам нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем $S = 15,$ чтобы Петя первым ходом добавил в кучу 1 камень и получил 16 камней. А из этой позиции Ваня уже любым своим ходом создаст выигрышную позицию для Пети, после чего Петя выиграет своим вторым ходом.

По такой же логике, в $S = 16$ можно попасть из $S = 8$ , что тоже является ответом.

Ответ: 815

Ошибка.
Попробуйте повторить позже

Задача 3#14219

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

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет 36 или более камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 35.$

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

Известно, что Петя выигрывает в первый ход. Укажите минимальное значение $S,$ когда такая ситуация возможна.

Показать ответ и решение

Чтобы Петя победил своим первым ходом, он должен увеличить количество камней в куче на столько, чтобы их стало больше или равно 36. Эффективнее Пете будет утраивать $S,$ чем добавлять к нему 2. При каких $S$ будет выполняться $3 ⋅S >= 36$ ? При $S ≥ 12.$ Следовательно ответ $12.$

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 4#14220

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинания.

Показать ответ и решение

Петя может выиграть своим первым ходом при $S ≥ 12.$ Таким образом, если мы возьмем $S = 11,$ или $S = 10$ то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Но нам нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем $S = 9,$ или $S = 8$ чтобы Петя первым ходом добавил в кучу 2 камня и получил 10 или 11 камней. А из этой позиции Ваня уже любым своим ходом создаст выигрышную позицию для Пети, после чего Петя выиграет своим вторым ходом.

Ответ: 89

Ошибка.
Попробуйте повторить позже

Задача 5#14221

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

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет $44$ или более камней. В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 43.$

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение $S$ , когда такая ситуация возможна.

Показать ответ и решение

Чтобы Ваня победил своим первым ходом, Петя должен увеличить количество камней в куче на столько, чтобы следующим ходом Ваня мог победить. Эффективнее Пете и Ване будет утраивать $S,$ чем добавлять к нему $1$ . При каких $S$ будет выполняться $3⋅3⋅S >= 44?$ При $S ≥ 5.$ Следовательно ответ $5.$

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 6#14222

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

Показать ответ и решение

Петя может выиграть своим первым ходом при $S ≥ 15.$ Таким образом, если мы возьмем $S = 14,$ то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Но нам нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем $S = 13,$ чтобы Петя первым ходом добавил в кучу $1$ камень и получил $14$ камней. А из этой позиции Ваня уже любым своим ходом создаст выигрышную позицию для Пети, после чего Петя выиграет своим вторым ходом.

Ответ: 13

03 Перекладывание камней одна куча