Полуинвариант
Ошибка.
Попробуйте повторить позже
Вася выписал в тетрадку несколько положительных чисел, меньших 
Каждую минуту он стирает из тетрадки 
числа 
и 
а затем
записывает вместо них два числа 
Может ли процесс продолжаться бесконечно долго, если на каждом шаге стираемые числа 
и
должны отличаться хотя бы на 
Подсказка 1
Сначала докажем, что все числа на доске ограничены. Предположим, что заменяется пара (a, b). Можно считать, что a > b, то есть b = a - t, где t ≥ 1/1000. Как при этом изменилось a?
Подсказка 2
Чтобы ответить на этот вопрос, рассмотрим функцию f(a) = a - (a(a - 1/1000)+1)/2. Ясно, что a - 1/1000 ≥ b. Тогда, зная знак f(a), можно будет оценить и изменение числа a. Как это сделать?
Подсказка 3
Верно! Сначала найдем знак f(a). Легко проверить, что на отрезке [0,1] у функции f(a) всего один ноль. Обозначим его x₀. Мы имеем дело с квадратичной функцией, причем старший коэффициент ее отрицателен. Тогда можно понять, что если a > x₀, то новое число стало меньше, чем a. А как проверить, что новое число получилось не больше какого-то наперед заданного?
Подсказка 4
Точно! Тогда новое число (ab+1)/2 ≤ (a²+1)/2 ≤ ((x₀)²+1)/2. Итак, наши числа ограничены. А как меняется сумма чисел после k-ой минуты?
Подсказка 5
Если стирается пара (a,b), то эта сумма равна (1-a)(1-b). Поскольку a, b < C, то (1-a)(1-b) > (1 - C)². В чем выходит противоречие, если операция применяется бесконечно долго?
Лемма. Докажем, что для любого начального набора чисел существует число 
такое, что на доске никогда не появится числа
больше, чем 
Доказательство. Рассмотрим произвольную пару 
которую стерли в некоторый момент времени. Без ограничений общности
можем считать, что 
тогда 
при некотором 
Рассмотрим функцию
Легко проверить, что на отрезке ![[0,1]](/api/latex-service/v1/GetSession/203018/index-f23162156a3cafe04cfb23bdf722ae83.svg)
решение уравнения 
единственно (для этого можно решить квадратное это уравнение).
Далее рассмотрим два случая:
Если 
то 
следовательно,
то есть большое из чисел пары не увеличилось.
Если 
то
Наконец, если 
— максимальное число начального набора, то на доске никогда не появится числа, которое было бы больше, чем
______________________________________________________________________________________________________________________________________________________
Перейдем к доказательству основной задачи. Пусть 
— сумма чисел после минуты 
Тогда для произвольного 
в силу
леммы,
Таким образом, после каждого шага сумма чисел на доске увеличивается не меньше, чем на 
Наконец, если данный процесс будет продолжаться бесконечно долго, то сумма чисел может быть сколько угодно большой, что невозможно.
Нет, не может
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
