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