Задание 19 ЕГЭ по информатике · B75BBC
ПовышеннаяКЭС 2.15
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 2 камня;
– убрать из кучи 4 камня;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 18, 16 или 5 камней.
Игра завершается, когда количество камней в куче становится не более 23. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 23 или менее камней. В начальный момент в куче было S камней, S ≥ 24.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
– убрать из кучи 2 камня;
– убрать из кучи 4 камня;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 18, 16 или 5 камней.
Игра завершается, когда количество камней в куче становится не более 23. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 23 или менее камней. В начальный момент в куче было S камней, S ≥ 24.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Показать ответ
96
Подсказки (3)
- Проверьте, при каких значениях S Петя может сразу получить количество камней не более 23.
- Ходы Пети дают значения S−2, S−4 и ⌊S/4⌋. Для значения S=96 после каждого хода рассмотрите ответный ход Вани.
- При S=96 Петя получает 94, 92 или 24. Ваня делением на 4 получает соответственно 23, 23 или 6 камней.
Решение
1. Петя выигрывает за один ход, если после одного из его ходов в куче останется не более 23 камней. Для деления на 4 это выполняется при ⌊S/4⌋≤23, то есть при S≤95. Поэтому минимальное значение, при котором Петя уже не может выиграть сразу, начинается с S=96.
⌊S4⌋≤23 при S≤95
2. Проверим значение S=96. После ходов Пети возможны кучи из 94, 92 и 24 камней.
3. Если осталось 94 или 92 камня, Ваня делит количество камней на 4 и получает 23 камня. Если осталось 24 камня, Ваня также делит кучу на 4 и получает 6 камней. Во всех случаях Ваня получает кучу не более 23 камней и выигрывает своим первым ходом.
⌊944⌋=23,⌊924⌋=23,⌊244⌋=6
⌊S4⌋≤23 при S≤95
2. Проверим значение S=96. После ходов Пети возможны кучи из 94, 92 и 24 камней.
3. Если осталось 94 или 92 камня, Ваня делит количество камней на 4 и получает 23 камня. Если осталось 24 камня, Ваня также делит кучу на 4 и получает 6 камней. Во всех случаях Ваня получает кучу не более 23 камней и выигрывает своим первым ходом.
⌊944⌋=23,⌊924⌋=23,⌊244⌋=6
Частые ошибки
- Проверяют только один возможный ход Пети, а не все три.
- Забывают, что результат деления округляется вниз.
- Выбирают значение меньше 96, не учитывая, что при S≤95 Петя может сразу разделить кучу на 4.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
19За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для…Ваня выигрывает первым ходом · 9555BE19За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три…Ваня выигрывает первым ходом · 95B91619За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для…Ваня выигрывает первым ходом · 98624A19За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два…Ваня выигрывает первым ходом · B3864F19За один ход игрок может: – убрать из кучи 3 камня; – убрать из кучи 7 камней; – уменьшить количество камней в…Ваня выигрывает первым ходом · B9E72319За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три…Ваня выигрывает первым ходом · B9EFC219За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два…Ваня выигрывает первым ходом · BDBF1A19За один ход игрок может добавить в кучу один или три камня либо увеличить количество камней в куче в два…Ваня выигрывает первым ходом · CCA614
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.