Бесконечные конструкции (игры, клетки, множества)
Ошибка.
Попробуйте повторить позже
Круг разделен на секторов, и в каждом написано целое число. В один из секторов ставится фишка. Каждым ходом прочитывается
число в секторе, где стоит фишка (пусть прочитано
), фишка сдвигается на
секторов по часовой стрелке, и там, куда она придет,
число увеличивается на
Докажите, что со временем все числа станут больше миллиона.
Предположим, что есть такой сектор в котором фишка побывает конечное количество раз (меньше миллиона). Рассмотрим
сектор
который стоит перед
Ясно, что в
лишь конечное количество раз может находиться число, дающее
остаток
при делении на
В противном случае мы бесконечное число раз попадём из
в
что невозможно по
предположению.
Заметим, что числа в секторах увеличиваются на единицу. Поэтому если сейчас в ячейке находится число с остатком при делении на
то перед появлением в ней следующего числа с остатком
при делении на
в ней появятся числа с остатками
при делении на
Следовательно, если в ячейке конечное количество раз возникает число с остатком
при делении
на
то в ней конечное количество раз возникнут числа со всеми другими остатками при делении на
Таким образом, число в
также всегда ограничено. Но тогда по аналогичным рассуждениям можно доказать, что число в секторе, находящемся перед
также
всегда ограничено. Так мы сможем постепенно доказать это утверждение про все секторы. Получается, что во всех секторах
числа ограничены, а значит фишка сделает конечное количество ходов, это противоречие. То есть такого сектора
не
существует.
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

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

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

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

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

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!