Задание 7 Параграф 11 ГДЗ Босова 11 класс (Информатика)

Задача

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

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

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

Подробный ответ

1) Петя выигрывает первым ходом, если после его хода в куче станет не менее $$47$$ камней. Значит, исходное число камней должно быть таким, чтобы можно было прибавить $$1$$ или $$5$$ и получить $$47$$ или больше:

$$S+1 \ge 47 \quad \text{или} \quad S+5 \ge 47.$$

Отсюда:

$$S \ge 46 \quad \text{или} \quad S \ge 42.$$

С учётом условия $$1<S<46$$ получаем все подходящие значения:

$$S=42, 43, 44, 45, 46.$$

Выигрывающие ходы:

$$42+5=47$$;
$$43+5=48$$;
$$44+5=49$$;
$$45+5=50$$;
$$46+1=47$$.

2) Петя не может выиграть за один ход, но Ваня может выиграть своим первым ходом, если после любого хода Пети в куче окажется $$42$$ или $$46$$ камней. Тогда Ваня добавит $$5$$ или $$1$$ и получит не менее $$47$$.

Такое значение:

$$S=41.$$

Действительно, Петя может получить только $$42$$ или $$46$$:

$$41+1=42$$, тогда Ваня делает $$42+5=47$$;
$$41+5=46$$, тогда Ваня делает $$46+1=47$$.

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

Такие начальные значения:

$$S=36 \quad \text{и} \quad S=40.$$

Стратегия Пети:

если $$S=36$$, Петя делает ход $$36+5=41$$;
если $$S=40$$, Петя делает ход $$40+1=41$$.

После любого хода Вани получается либо $$42$$, либо $$46$$, а Петя следующим ходом добирает до $$47$$ или больше:

$$41+1=42$$, затем $$42+5=47$$;
$$41+5=46$$, затем $$46+1=47$$.

4) Нужно найти такое значение $$S$$, при котором Ваня может гарантированно выиграть первым или вторым ходом, но не может выиграть первым ходом при любой игре Пети. Это значение:

$$S=39.$$

Стратегия Вани: