Задание 19 ЕГЭ по информатике · 16371A
ПовышеннаяКЭС 2.15
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 2 камня;
– убрать из кучи 4 камня;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 18, 16 или 6 камней.
Игра завершается, когда количество камней в куче становится не более 17. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 17 или менее камней. В начальный момент в куче было S камней, S ≥ 18.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
– убрать из кучи 2 камня;
– убрать из кучи 4 камня;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 18, 16 или 6 камней.
Игра завершается, когда количество камней в куче становится не более 17. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 17 или менее камней. В начальный момент в куче было S камней, S ≥ 18.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Показать ответ
54
Подсказки (3)
- Определите, при каких значениях S Петя может сразу получить количество камней не более 17.
- После хода Пети возможны позиции S−2, S−4 и ⌊S/3⌋. Для прямой победы нужно, чтобы одна из них была не больше 17.
- Петя не может выиграть за один ход при S≥54. Проверьте для S=54 позиции 52, 50 и 18: из каждой Ваня может получить не более 17 камней.
Решение
1. Петя выигрывает за один ход, если после одного из его ходов количество камней становится не более 17.
S−2≤17илиS−4≤17или⌊S3⌋≤17
2. Для третьего варианта условие выполняется при S≤53. Поэтому при S=54 Петя уже не может выиграть за один ход: после его ходов остаётся 52, 50 или 18 камней.
3. Из позиции 52 Ваня делит количество камней на 3 и получает ⌊52/3⌋=17. Из позиции 50 он получает ⌊50/3⌋=16, а из позиции 18 убирает 2 камня и получает 16.
4. Следовательно, S=54 удовлетворяет условию. Все меньшие значения не подходят, так как при S≤53 Петя может выиграть делением кучи на 3 за один ход.
S−2≤17илиS−4≤17или⌊S3⌋≤17
2. Для третьего варианта условие выполняется при S≤53. Поэтому при S=54 Петя уже не может выиграть за один ход: после его ходов остаётся 52, 50 или 18 камней.
3. Из позиции 52 Ваня делит количество камней на 3 и получает ⌊52/3⌋=17. Из позиции 50 он получает ⌊50/3⌋=16, а из позиции 18 убирает 2 камня и получает 16.
4. Следовательно, S=54 удовлетворяет условию. Все меньшие значения не подходят, так как при S≤53 Петя может выиграть делением кучи на 3 за один ход.
Частые ошибки
- Забывают округление результата деления вниз.
- Проверяют только один из возможных ходов Пети.
- Считают достаточным, чтобы Ваня имел выигрышный ход только после одного варианта хода Пети.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
19За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней…Ваня выигрывает первым ходом19За один ход игрок может: – добавить в одну из куч (по своему выбору) 2 камня; – увеличить количество камней в…Ваня выигрывает первым ходом · 0A61A419За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для…Ваня выигрывает первым ходом · 0EE09319За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два…Ваня выигрывает первым ходом · 10FE2519За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три…Ваня выигрывает первым ходом · 17A12219За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза.…Ваня выигрывает первым ходом · 2C24A719За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три…Ваня выигрывает первым ходом · 34770719За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два…Ваня выигрывает первым ходом · 35A49A
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.