Китайская теорема об остатках
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Докажите, что числа натурального ряда можно переставить местами так, чтобы для всех 
сумма 
первых чисел делилась на
Подсказка 1
Не будем сразу строить всю перестановку. Будем поэтапно добавлять все числа 1, 2, 3, … в последовательность, при необходимости оставляя места для будущих вставок. Подумайте, как при таком подходе поддерживать требуемую делимость на каждом шаге.
Подсказка 2
Попробуем начать строить последовательность с самого начала и подумаем, как можно поддерживать условие делимости на каждом шаге. Что произойдёт, если рассмотреть добавление сразу двух чисел подряд?
Подсказка 3
Для аккуратных рассуждений введём обозначения: пусть после n шагов сумма равна S, и мы хотим добавить числа k и m. Как можно записать условия делимости на n+1 и n+2 в виде сравнения? Какие значения n обращают это сравнение в верное?
Подсказка 4
Система сравнений для k и m решается благодаря китайской теореме об остатках. Проверим, почему решение всегда можно найти, и как при этом можно гарантировать, что все натуральные числа в итоге будут использованы.
Начнём с числа 
Пусть после некоторого шага поставлено первые 
чисел, их сумма равна 
и среди непоставленных чисел
минимальное равно 
Добавим ещё два числа: сначала некоторое 
затем 
Хотим добиться
Это равносильно системе
Так как 
то по китайской теореме об остатках такая 
существует и задаётся единственным классом вычетов по
модулю 
Следовательно, подходящих 
бесконечно много, и мы можем выбрать представителя этого класса настолько
большим, чтобы он ещё не встречался в последовательности и не равнялся 
После добавления 
сумма первых 
членов делится на 
а после последующего добавления 
сумма первых 
членов
делится на 
Число 
по построению минимально отсутствующее, значит, в последовательности встретится каждое натуральное
число и никакое не встретится дважды.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
