Выбор модуля для доказательства делимости / простоты / степени
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Изначально на доске написано 10 единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые 5 чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на 1. Если в течение 10 000 ходов на доске появится число, делящееся на 2023, то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша?
Источники:
Подсказка 1:
Для начала будет полезно изучить само число 2023, 2023 = 7*17². Теперь нужно попытаться угадать ответ, кто же победит?
Подсказка 2:
Пусть Глеб имеет выигрышную стратегию. Тогда он всегда за 10000 ходов успевает добиться делимости. Не кажется ли Вам, что 10000 просто для красоты?
Подсказка 3:
Действительно, это просто красивое число. Значит, побеждает Глеб, и он должен добиваться делимости за не более чем какое-то количество ходов, причём предварительно количество нужно будет угадать и только потом доказывать, что он это сможет сделать. Либо побеждает Гриша, и тогда нужно доказать, что он всегда может поддерживать НЕделимость чисел на 2023. Кажется, проще сначала попробовать доказать второй вариант, ибо достаточно просто придумать алгоритм.
Подсказка 4:
Итак, хотим доказать, что Гриша может всегда "сломать" делимость на 2023, но рассуждать именно про делимость 2023 сложновато, не зря же мы вначале разложили его на множители) Будем пробовать доказать, что Гриша может всегда "сломать" делимость на 7 (7 < 17 и они оба простые, поэтому логичнее начать с 7).
Подсказка 5:
Информации о конкретном числе в ключе "делится или не делится на 7" нам недостаточно. Что же может нам помочь, когда речь идёт о делимости?
Подсказка 6:
Конечно же, модульная арифметика! Рассмотрите, как операция Гриши влияет на остатки.
Подсказка 7:
Если число не делилось на 7 до хода Гриши, то после оно будет давать остаток 1 либо 2, либо 4 по модулю 7. В то же время Глеб может прибавить 1 к остатку своим ходом. На какие мысли об алгоритме Гриши это наталкивает?
Подсказка 8:
Подумаем вот о чём... Гриша возвёл в квадрат некоторое число а, получил a². На какое максимальное количество ходов он может забыть про него? То есть сколько раз подряд он может позволить Глебу изменить число a²?
Подсказка 9:
Если на ≥ 3 хода. То есть a² сравнимо с 4, то за 3 хода Глеб может победить. Значит, забывать про число Гриша может максимум на два хода Глеба. Что это значит?
Подсказка 10:
Если зафиксировать какое-то число, то минимум каждые два хода Гриша должен с ним взаимодействовать (осознайте, что этого достаточно). Осталось придумать такую стратегию... Вам может помочь идея разбиения на группы. Успехов!
Заметим, что 
Гриша разобьёт числа на доске на две группы по 5 и будет возводить в квадрат числа из
первой группы и из второй группы по очереди. Легко видеть, что квадраты целых чисел, не кратных 7, при делении на 7
могут давать лишь остатки 1, 2 и 4. Следовательно, после увеличения максимум на 2 числа на доске будут давать при
делении на 7 лишь остатки 1, 2, 3, 4, 5 и 6. Значит, ни одно из чисел не будет делиться на 7, а потому не будет делиться и на
2023.
побеждает Гриша
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
