Задание 1 Вариант 3 Самостоятельная работа 8 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)

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

Обозначим позиции, в которых игрок, которому предстоит ход, может выиграть сразу, как выигрышные за один ход.

Если в строке уже стоит цифра:

• $$7$$ — можно дописать $$89$$ и сразу получить $$9$$;
• $$8$$ — можно дописать $$9$$ и сразу получить $$9$$;
• $$6$$ — любой ход переводит игру в позицию $$7$$ или $$8$$, а значит, соперник выигрывает следующим ходом;
• $$4$$ и $$5$$ — можно сделать ход в позицию $$6$$, после чего соперник уже не может выиграть сразу;
• $$3$$ — любой ход переводит игру в позицию $$4$$ или $$5$$, то есть в выигрышную для следующего игрока ситуацию.

Тогда получаем:

1. Петя выигрывает за один ход при $$N=7$$ и $$N=8$$.
2. При $$N=6$$ Петя не может выиграть за один ход, но любой его ход даёт Ване возможность выиграть своим первым ходом.
3. При $$N=4$$ и $$N=5$$ у Пети есть выигрышная стратегия: он переводит игру в позицию $$6$$, после чего, как бы ни ходил Ваня, Петя выигрывает следующим ходом.
4. При $$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$$.