Задание №1054: Задание 1
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: – убрать из кучи 2 камня; – убрать из кучи 4 камня; – уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего). Например , из кучи в 20 камней за один ход можно получить кучу из 18, 16 или 6 камней. Игра завершается, когда количество камней в куче становится не более 17. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 17 или менее камней. В начальный момент в куче было S камней, S ≥ 18. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное значение S , при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Что проверяет это задание
Задание относится к теме «Задание 1». Для решения понадобятся:
- формализация задачи
- построение алгоритма
- проверка граничных случаев
Источник: ФИПИ — открытый банк заданий
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- ФИПИ — открытый банк заданий
- Организатор
- ФИПИ
- Материалы
- 0 файла
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Задание 1» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Информатика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
Давайте решим эту задачу шаг за шагом:
1) Сначала рассмотрим, какие ходы могут сделать Петя в начальный момент.
Он может убрать 2 или 4 камня, либо уменьшить количество камней в куче в 3 раза (округляя до меньшего).
2) Теперь рассмотрим, какие ходы могут сделать Ваня после каждого из этих вариантов:
- Если Петя убрал 2 камня: S -> S-2. Ваня может взять 2 или 4 камня (если S-2 >= 4), либо уменьшить количество камней в куче в 3 раза.
- Если Петя убрал 4 камня: S -> S-4. Ваня может взять 2 или 4 камня (если S-4 >= 4), либо уменьшить количество камней в куче в 3 раза.
- Если Петя уменьшил количество камней в куче в 3 раза: S -> floor(S/3). Ваня может взять 2 или 4 камня (если floor(S/3) >= 4), либо уменьшить количество камней в куче в 3 раза.
3) Для того чтобы Петя не мог выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом, нужно найти минимальное S, при котором:
- Петя не может сделать ход, который приведет к победе (т.е. к получению 17 или менее камней).
- При любом ходе Пети Ваня может сделать ход, который приведет к победе.
4) Проверим значения S от 18 до 20:
- S = 18: Петя не может выиграть за один ход (16 или 14 камней), но Ваня может сделать ход, который приведет к победе (17).
- S = 19: Петя не может выиграть за один ход (17 или 15 камней), но Ваня может сделать ход, который приведет к победе (16).
- S = 20: Петя не может выиграть за один ход (18 или 16 камней), но Ваня может сделать ход, который приведет к победе (17).
5) Таким образом, минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом, равно 18.
Используемые формулы
Ваня может взять 2 или 4 камня (если S-2 >= 4), либо уменьшить количество камней в куче в 3 раза.Ваня может взять 2 или 4 камня (если S-4 >= 4), либо уменьшить количество камней в куче в 3 раза.Ваня может взять 2 или 4 камня (если floor(S/3) >= 4), либо уменьшить количество камней в куче в 3 раза.- S = 18: Петя не может выиграть за один ход (16 или 14 камней), но Ваня может сделать ход, который приведет к победе (17).- S = 19: Петя не может выиграть за один ход (17 или 15 камней), но Ваня может сделать ход, который приведет к победе (16).- S = 20: Петя не может выиграть за один ход (18 или 16 камней), но Ваня может сделать ход, который приведет к победе (17).
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Перепутать основание системы счисления.
- Не учесть границы диапазона.
- Проверить алгоритм только на одном примере.