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

Задача

В начальный момент в куче было S камней, 1 < S < 46. Выполните следующие задания, в каждом случае обосновывая свой ответ. 1) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы. Если в куче будет 46, 45, 44, 43, 42: 46+1=47; 42+5=47 (и для промежуточных тоже надо прибавить 5), то Петя выигрывает первым ходом. 2) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. Если в куче будет 41 камень, то Петя не сможет выиграть, выигрывает Ваня своим первым ходом. Любым своим ходом Петя создает выигрышную ситуацию для Вани (42 или 46). 3) Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети. Петя должен создать для Вани проигрышную ситуацию, например, чтобы в куче был 41 камень. Это можно получить, если исходная ситуация будет либо 40, либо 36 (40+1=41; 36+5=41) 4) Укажите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, однако у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани. Если исходная ситуация 39, то Ваня выигрывает первым или вторым ходом.

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

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.$$

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