Регион 10 класс → .07 Регион 2020

Положим Предположим противное: для каждого из чисел существует разложение где Заметим, что каждое из чисел и строго больше а также что иначе Значит, каждое из чисел набора лежит в множестве из чисел Таким образом, в этом наборе найдутся два равных числа. Пусть каждое из этих двух чисел равно

Пусть эти равные числа имеют равные индексы в наборе, то есть при некотором Тогда поэтому число делится на простое Так как это может быть лишь при Тогда соответствующее значение равно что при больше, чем Противоречие (так как ).

В противном случае существуют индексы такие, что для которых числа и делятся на Тогда и также делится на Из взаимной простоты чисел и получаем, что делится на а это невозможно, так как

Таким образом, в каждом случае получено противоречие и, следовательно, указанное в условии задачи число всегда найдётся.

Пусть — один из данных прямоугольников, а — центр окружности, на которой лежат восемь вершин из условия задачи. Тогда лежит на серединном перпендикуляре к отрезку Но он совпадает с серединным перпендикуляром к отрезку Поскольку лежит на нём, имеем Аналогично доказываем, что и Тогда равноудалена от всех вершин четырехугольника значит, вписан в окружность с центром что и требовалось доказать.

Решение будет состоять из трёх шагов

Докажем следующую лемму. Лемма. Пусть при некоторых натуральных квадратный трёхчлен имеет целые корни. Тогда и делятся на

Доказательство. По теореме Виета и являются целыми числами. Лемма доказана.

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

Среди подряд идущих чисел менее чётных. С другой стороны, зная, что пробегают числа получим оценку снизу на количество чётных чисел среди всех коэффициентов. Заметим, что в каждой из троек хотя бы одно чётное число, иначе значение трёхчлена в любой целой точке будет нечётно, в частности, такой трёхчлен не может иметь целых корней. Если же чётно (количество соответствующих троек равно ), то и в силу леммы, тоже чётные, значит, в такой тройке все три коэффициента чётные. Итого Сравнивая верхнюю и нижнюю оценки, имеем откуда Противоречие.

Мы будем называть многочлен вида просто многочленом, а график такого многочлена — просто графиком. Мы будем пользоваться следующей известной леммой.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Через любые три точки с разными абсциссами проходит ровно один график.

Доказательство. Один график, проходящий через эти точки, найдётся всегда. С другой стороны, если через три точки проходят графики двух разных многочленов и то разность имеет три корня что невозможно.

_________________________________________________________________________________________________________________________________________________________________________________

Из леммы следует, что через любые две точки с разными абсциссами проходит бесконечно много графиков, и любые два из них пересекаются только по этим двум точкам. Перейдём к решению. Будем считать, что Петя задумал два графика, за ход Вася называет Пете число а Петя отмечает точку с абсциссой на одном из графиков. Можно считать, что на разных ходах Вася называет разные (иначе Петя повторит ответ).

Рассмотрим ситуацию после ходов. Назовём пару графиков подходящей, если объединение этих графиков содержит все отмеченные Петей точки.

Покажем, что Мы будем считать, что Петя изначально не рисует никаких графиков, а просто отмечает некоторые точки с данными абсциссами. Покажем, как ему действовать, чтобы после ходов нашлись две подходящих пары графиков такие, что все графика различны; это и будет означать, что Вася не смог добиться требуемого, ибо Петя мог нарисовать любую из этих пар.

Будем обозначать точку, появляющуюся после -го хода, через На первых двух ходах Петя выбирает На следующих ходах Петя отметит точки и на графике многочлена и точки и — на графике многочлена Седьмым ходом Петя выбирает точку , не лежащую ни на одном из графиков, проходящем через какие-то три точки из и Тогда существуют графики и проходящие через тройки точек и согласно нашему выбору, эти графики различны и отличаются от и Значит, пары и — подходящие, и все эти четыре графика различны, то есть Вася не сможет добиться требуемого.

Покажем, как Васе добиться требуемого за ходов. На первых ходах он называет произвольных различных чисел.

Назовём график подозрительным, если он проходит хотя бы через три точки, отмеченных Петей на этих ходах. Назовём число плохим, если два различных подозрительных графика имеют общую точку с абсциссой Существует лишь конечное количество подозрительных графиков и, следовательно, лишь конечное количество плохих чисел.

На восьмом ходу Вася называет любое неплохое число После того, как Петя отметит восьмую точку, возможны два случая.

Случай Существует график многочлена содержащий пять из восьми отмеченных точек. Три из этих точек лежат на одном из Петиных графиков; по лемме, этот график совпадает с Значит, Васе достаточно назвать многочлен

Случай Такого графика нет. Это значит, что на каждом из Петиных графиков лежит ровно по отмеченных точки; поэтому оба этих графика подозрительны. Докажем, что существует единственная пара подозрительных графиков, содержащих в совокупности все отмеченных точек; тогда Васе достаточно назвать любой из соответствующих многочленов. Пусть и — две таких пары, причём и содержат Согласно выбору числа это может произойти лишь при Но тогда каждый из графиков и проходит через отмеченных точки, не лежащих на и они совпадают согласно лемме. Значит, и наши пары совпадают.