Тема 19. Задачи на теорию чисел
19.07 Остатки
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела задачи на теорию чисел
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#16125

Петя и Вася по очереди выписывают цифры шестисотзначного числа (каждый имеет право ставить цифры в любое место). Начинает Петя. Если полученное в итоге число не делится на семь, то выигрывает Петя, иначе выигрывает Вася. Кто из них может выиграть, как бы ни играл соперник?

Показать ответ и решение

Заметим, что последний ход сделает Вася. Покажем одну из возможных стратегий Васи.

Все ходы, кроме последнего, Вася делает произвольно, то есть ставит любые цифры на любые места (например, только единицы каждый раз на самое левое свободное поле). Последним ходом перед Васей осталось одно пустое поле). Последним ходом перед Васей осталось одно пустое поле. Пусть после этого поля еще k  цифр слева. Будем считать, что пока что на месте этого поля стоит цифра 0. Тогда, когда Вася пишет на месте поля цифру c  , он увеличивает шестисотзначное число на c ⋅10k.  Заметим, что числа 1⋅10k, 2 ⋅10k, 3⋅10k,..., 7⋅10k  дают различные остатки при делении на 7, так как разность любых двух из этих чисел не делится на 7. А так как этих чисел 7, то они дают все возможные остатки при делении на 7. Получается, что, написав одну из цифр от 1 до 7 на свободном поле, Вася может прибавить к данному числу любой остаток при делении на 7. В частности, Вася может выбрать такой остаток, чтобы результат делился на 7, тем самым победив.

Ответ:

Вася

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!