Домашние задания: Математика
Кошкин и Мышкис играют в следующую игру.
Имеется 2022! камней. За один ход можно взять не более 1/2022 доли оставшихся камней. Проигрывает тот, кто не может сделать ход. Первым ходит Кошкин. Кто выиграет при правильной игре?
Похоже на головоломку с обратной индукцией, так что вполне разумно начать с конца. Проигрышное количество камней (позиция p) равно 2021, потому что нельзя взять меньше одного камня (предположительно). Предыдущий ход (выигрышная или позиция n) должен был тогда быть с 2022, потому что единственным допустимым ходом между 2022 и 4043 является взятие одного камня. Таким образом, 2022 - это позиция n, 2023 - позиция p и т.д., что дает 4042 - позицию n, 4043 - позицию p. Наименьшая куча из которой можно выбрать это 4044. Переходим в 4043, что является позицией p, поэтому 4044 также является выигрышной позицией. 4045 тоже должен переместиться в 4043. Но это означает, что 4046 является позицией p, поскольку оба хода относятся к позиции n. 4047 это n, 4048 это n, 4049 это p и т. д. Этот метод приводит к точке, где у нас есть 3 доступных хода, к 6066. Один из трех возможных ходов является позицией p (какой именно я не прорабатывал), так что это позиция n. Получается, у нас здесь вот такая схемка: каждое число, кратное 2022, является позицией n. Это связано с тем, что позиции между 2022k и 2022(k+1)-1 являются циклическими с периодом k+1. Следовательно, можно найти позицию p где-то из k+1 возможных ходов из позиции 2022(k+1). (можно было бы формализовать это на основе индукции по k, но, надеюсь, должно быть ясно, как обобщаются случаи k=2 и k=3.) Короче, отвечая на исходную задачу. 2022!, поскольку оно кратно 2022, является позицией n, и Кошкин выигрывает.
Алёнка Zw
Опять откуда то слизанное решение)))
Дарья Виноградова
Задачу можно решить проще с помощью рекурсии.
Похожие вопросы
- У Коли есть кубики двух цветов. Он строит из них башню, ставя каждый следующий кубик на предыдуший.
- В период вступительных экзаменов были сформированы три отношения R1 R2 и R3 со следующими схемами:
- Применяя равносильные преобразования приведите следующие формулы к предваренной (префексной) форме
- Помогите решить. Являются ли парами следующие отрицания или нет (объясните почему)
- Что делать если в атомик харт хочется играть а надо матешу делать?
- Почему некоторым детям родители ВООБЩЕ не разрешают играть в компьютерные игры? Это ведь неправильно
- Почему некоторым детям родители ВООБЩЕ не разрешают играть в компьютерные игры?
- Почему некоторым детям родители ВООБЩЕ не разрешают играть в компьютерные игры?
- Почему некоторые люди так любят оскорблять игроков которые играют в другие игры?
- Помогите, родители не разрешают играть в компьютерные игры... Это может сломать мне жизнь! Правда.