Задание 1 Вариант 3 Самостоятельная работа 8 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)
Петя и Ваня играют в «Цифры». Первоначально выбирается и записывается одна десятичная цифра $$N$$, $$0 \le N \le 8$$. Игроки ходят по очереди; начинает игру Петя. За один ход игрок может дописать к уже имеющейся строке цифр одну или две следующие по порядку значения цифры. Победителем считается игрок, написавший цифру $$9$$. Считается, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, с которой он может столкнуться при различной игре противника.
1) Укажите все значения $$N$$, при которых Петя может выиграть за один ход. Обоснуйте, что найдены все нужные значения $$N$$, и укажите выигрывающий ход для каждого указанного значения $$N$$.
2) Укажите такое значение $$N$$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
3) Укажите такие значения $$N$$, при которых у Пети есть выигрышная стратегия, причём:
• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для каждого указанного значения $$N$$ опишите выигрышную стратегию Пети.
4) Укажите значения $$N$$, при которых:
• Ваня не может выиграть за один ход;
• Ваня может выиграть своим вторым ходом независимо от того, как будет ходить Петя.
Для указанных значений $$N$$ опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани. На рёбрах дерева укажите, кто делает ход, в узлах — последовательность цифр.
П — проигрышная ситуация. В — выигрышная ситуация.
Обозначим позиции, в которых игрок, которому предстоит ход, может выиграть сразу, как выигрышные за один ход.
Если в строке уже стоит цифра:
- $$7$$ — можно дописать $$89$$ и сразу получить $$9$$;
- $$8$$ — можно дописать $$9$$ и сразу получить $$9$$;
- $$6$$ — любой ход переводит игру в позицию $$7$$ или $$8$$, а значит, соперник выигрывает следующим ходом;
- $$4$$ и $$5$$ — можно сделать ход в позицию $$6$$, после чего соперник уже не может выиграть сразу;
- $$3$$ — любой ход переводит игру в позицию $$4$$ или $$5$$, то есть в выигрышную для следующего игрока ситуацию.
Тогда получаем:
- Петя выигрывает за один ход при $$N=7$$ и $$N=8$$.
- При $$N=6$$ Петя не может выиграть за один ход, но любой его ход даёт Ване возможность выиграть своим первым ходом.
- При $$N=4$$ и $$N=5$$ у Пети есть выигрышная стратегия: он переводит игру в позицию $$6$$, после чего, как бы ни ходил Ваня, Петя выигрывает следующим ходом.
- При $$N=3$$ Ваня не может выиграть за один ход, но может выиграть своим вторым ходом.
Стратегия Вани при $$N=3$$:
- если Петя дописывает $$1$$, получается $$4$$, тогда Ваня дописывает $$2$$ и получает $$6$$;
- если Петя дописывает $$2$$, получается $$5$$, тогда Ваня дописывает $$1$$ и получает $$6$$.
После этого Петя вынужден перевести игру в $$7$$ или $$8$$, а Ваня следующим ходом дописывает $$89$$ или $$9$$ и выигрывает.
Дерево партий для стратегии Вани:
3 — Петя → 4 — Ваня → 6 — Петя → 7 — Ваня → 9
3 — Петя → 4 — Ваня → 6 — Петя → 8 — Ваня → 9
3 — Петя → 5 — Ваня → 6 — Петя → 7 — Ваня → 9
3 — Петя → 5 — Ваня → 6 — Петя → 8 — Ваня → 9
Ответ
1) $$N=7, 8$$.
2) $$N=6$$.
3) $$N=4, 5$$.
4) $$N=3$$.
