Тема . Множества

Бесконечные конструкции (игры, клетки, множества)

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

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

Задача 1#73693

Круг разделен на 2018  секторов, и в каждом написано целое число. В один из секторов ставится фишка. Каждым ходом прочитывается число в секторе, где стоит фишка (пусть прочитано k  ), фишка сдвигается на |k| секторов по часовой стрелке, и там, куда она придет, число увеличивается на 1.  Докажите, что со временем все числа станут больше миллиона.

Подсказки к задаче

Подсказка

Стоит решать от противного. Пусть в секторе A фишка побывает меньше миллиона раз. Какое тогда количество раз она побывает в секторе, следующем за A? Конечное или бесконечное?

Показать доказательство

Предположим, что есть такой сектор A,  в котором фишка побывает конечное количество раз (меньше миллиона). Рассмотрим сектор B,  который стоит перед A.  Ясно, что в B  лишь конечное количество раз может находиться число, дающее остаток 1  при делении на 2018.  В противном случае мы бесконечное число раз попадём из B  в A,  что невозможно по предположению.

Заметим, что числа в секторах увеличиваются на единицу. Поэтому если сейчас в ячейке находится число с остатком 1  при делении на 2018,  то перед появлением в ней следующего числа с остатком 1  при делении на 2018  в ней появятся числа с остатками 2,3,4,...,2017,0  при делении на 2018.  Следовательно, если в ячейке конечное количество раз возникает число с остатком 1  при делении на 2018,  то в ней конечное количество раз возникнут числа со всеми другими остатками при делении на 2018.  Таким образом, число в    B  также всегда ограничено. Но тогда по аналогичным рассуждениям можно доказать, что число в секторе, находящемся перед B,  также всегда ограничено. Так мы сможем постепенно доказать это утверждение про все секторы. Получается, что во всех секторах числа ограничены, а значит фишка сделает конечное количество ходов, это противоречие. То есть такого сектора A  не существует.

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

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

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

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

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

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

Бесплатное онлайн-обучение

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

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

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

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

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

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

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

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