ГДЗ по информатике, 11 класс, Босова, номер 11.30: Моделирование на графах

План решения.

В данной игре побеждает тот, кто первым доводит количество камней в куче до 47 или более. За один ход можно добавить 1 или 5 камней. Для анализа позиций будем использовать метод «от обратного»: определим выигрышные и проигрышные позиции, начиная с целевого числа 47 и двигаясь назад к меньшим значениям S. Позиция называется выигрышной, если из неё существует ход в проигрышную позицию для соперника. Позиция называется проигрышной, если все возможные ходы из неё ведут в выигрышные позиции для соперника.

Вычисление по пунктам.

1) Значения S, при которых Петя выигрывает в один ход.

Петя выигрывает сразу, если после его хода сумма станет ≥47. Пусть текущее число камней S.
Если Петя добавляет 1 камень, то S+1≥47⇒S≥46. Так как максимальное начальное значение S=46, то при S=46 ход «+1» приводит к 47 (победа).
Если Петя добавляет 5 камней, то S+5≥47⇒S≥42.
Таким образом, при S∈{42,43,44,45,46} Петя может выиграть за один ход.
Выигрышные ходы:
- При S=42: ход +5 (42+5=47).
- При S=43: ход +5 (43+5=48).
- При S=44: ход +5 (44+5=49).
- При S=45: ход +5 (45+5=50).
- При S=46: ход +1 (46+1=47) или ход +5 (46+5=51).

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

Это означает, что позиция S является проигрышной для первого игрока (Пети), так как любой его ход переводит игру в позицию, из которой второй игрок (Ваня) выигрывает немедленно.
Рассмотрим позиции, из которых Ваня выигрывает в один ход. Это те же самые позиции, что мы нашли в пункте 1: V_win={42,43,44,45,46}.
Нам нужно найти такое S, чтобы из него нельзя было выиграть сразу (S<42), но любые ходы (+1 или +5) попадали бы во множество V_win.
Ходы из S: S+1 и S+5.
Условия:
1) S+1∈{42,...,46}⇒S∈{41,...,45}.
2) S+5∈{42,...,46}⇒S∈{37,...,41}.
Пересечение этих множеств: S=41.
Проверка для S=41:
- Если Петя делает ход +1, получается 42. Ваня добавляет 5, получает 47 и выигрывает.
- Если Петя делает ход +5, получается 46. Ваня добавляет 1, получает 47 и выигрывает.
Ответ: S=41. Стратегия Вани: отвечать на ход Пети таким образом, чтобы сумма стала 47 или больше (если Петя добавил 1, Ваня добавляет 5; если Петя добавил 5, Ваня добавляет 1).

3) Два значения S, при которых у Пети есть стратегия выигрыша вторым ходом независимо от игры Вани.

Это значит, что позиция S является выигрышной для Пети, но он не может выиграть первым ходом. То есть из S существуют ходы, которые приводят к проигрышным позициям для Вани. Мы уже знаем одну такую проигрышную позицию для того, кто ходит следующим: это S=41 (позиция, где игрок, делающий ход, проигрывает, так как соперник выигрывает сразу).
Значит, нам нужны такие S, из которых можно попасть в 41.
Возможные ходы в 41:
- Из S=40 ход +1 ведет к 41.
- Из S=36 ход +5 ведет к 41.
Проверим, могут ли эти игроки выиграть первым ходом?
Для S=40: макс. результат 40+5=45<47. Не выигрывает сразу.
Для S=36: макс. результат 36+5=41<47. Не выигрывает сразу.
Стратегия Пети:
- При S=40: Петя делает ход +1, оставляя Ване 41. Как показано выше, из 41 любой ход Вани позволяет Пете выиграть следующим ходом (так как Ваня попадет в диапазон 42-46, откуда Петя доберет до 47).
- При S=36: Петя делает ход +5, оставляя Ване 41. Далее аналогично.
Ответ: S=36 и S=40.

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

Фраза «у Вани есть стратегия... против любой игры Пети» означает, что начальная позиция S является проигрышной для первого игрока (Пети). То есть из S все ходы ведут в выигрышные позиции для второго игрока (Вани).
Мы уже нашли одну проигрышную позицию: S=41. Но в условии сказано, что у Пети нет стратегии выигрыша первым ходом (что верно для 41), но Ваня выигрывает своим первым ходом? Нет, в пункте 2 мы разобрали случай, когда Ваня выигрывает своим первым ходом. Здесь же формулировка «стратегия выигрыша первым или вторым ходом» подразумевает, что Ваня может выиграть либо сразу после хода Пети (если Петя ошибется/попадет в выигрышную зону для Вани), либо позже. Однако ключевое слово — «против любой игры Пети». Это стандартное определение проигрышной позиции для текущего игрока.
Давайте найдем следующую проигрышную позицию ниже 41.
Позиция проигрышна, если все ходы из неё ведут в выигрышные позиции.
Выигрышные позиции (где можно попасть в проигрышную):
Мы знаем, что 41 — проигрышная.
Значит, позиции, из которых можно попасть в 41, являются выигрышными: это 40 (ход +1) и 36 (ход +5).
Теперь ищем позицию S, из которой ходы ведут только в выигрышные позиции (40, 36 и другие выигрышные).
Рассмотрим S=35. Ходы: 35+1=36 (выигрышная для следующего игрока, т.е. Вани), 35+5=40 (выигрышная для следующего игрока, т.е. Вани).
Если оба хода ведут в позиции, где следующий игрок (Ваня) имеет выигрышную стратегию, то текущий игрок (Петя) находится в проигрышной позиции.
Проверим, может ли Петя выиграть первым ходом при S=35? Максимум 35+5=40<47. Нет.
Проверим стратегию Вани при S=35:
- Если Петя ходит +1 (получается 36), Ваня находится в выигрышной позиции 36. Его стратегия: сделать ход +5, оставив Пете 41. Теперь Петя в проигрышной позиции 41. Любой ход Пети (в 42 или 46) позволит Ване выиграть следующим ходом (добавив 5 или 1 соответственно). Итого Ваня выигрывает своим вторым ходом.
- Если Петя ходит +5 (получается 40), Ваня находится в выигрышной позиции 40. Его стратегия: сделать ход +1, оставив Пете 41. Далее аналогично: Петя обречен, Ваня выигрывает своим вторым ходом.
Таким образом, при S=35 Ваня выигрывает всегда (своим вторым ходом). Условие «первым или вторым» выполнено (он выигрывает вторым).
Есть ли другие кандидаты? Обычно в таких задачах ищут минимальную проигрышную позицию или конкретную по контексту. Пункт 4 часто требует построения дерева. Дерево для S=35:
nRoot:35
\nChild 1: 36 (ход Пети +1)
Grandchild 1.1: 41 (ход Вани +5) -> Проигрышная для Пети
Great-grandchild 1.1.1: 42 (ход Пети +1) -> Выигрышная для Вани (ход +5)
Great-grandchild 1.1.2: 46 (ход Пети +5) -> Выигрышная для Вани (ход +1)
\nChild 2: 40 (ход Пети +5)
Grandchild 2.1: 41 (ход Вани +1) -> Проигрышная для Пети
... аналогично ...
Ответ: S=35.

Проверка.

1) S=42..46: Петя добирает до 47+. Верно.
2) S=41: Петя оставляет 42 или 46. Ваня добирает до 47. Верно.
3) S=36,40: Петя оставляет 41. Ваня попадает в ловушку 41 и проигрывает. Верно.
4) S=35: Петя оставляет 36 или 40. Оба варианта — выигрышные позиции для Вани (так как из них можно оставить Пете 41). Ваня использует эту возможность, оставляет Пете 41, а затем выигрывает. Петя не может выиграть первым ходом. Верно.