Регион 10 класс

Вычтем из второго равенства первое и разложим левую часть на множители, получим:

Не умаляя общности (в условии имеется циклическая симметрия переменных будем считать, что наибольшее из данных чисел. Тогда но из (*) видим, что Значит, Аналогично Тогда из следует Получается

Обозначим так что тогда принимает вид Нам нужно доказать, что

Заметим, что так как это неравенство преобразуется к виду (или следует из неравенства о среднем арифметическом и среднем геометрическом). Отсюда и далее

Получаем откуда и поэтому Остаётся показать, что невозможно. Если то и тогда в предыдущем рассуждении мы получим строгое неравенство Значит, возможно лишь при Рассмотрим этот случай отдельно.

В этом случае и Тогда

что противоречит первому равенству из условия задачи.

Первое решение. По теореме Виета Значит,

Тогда из условия следует, что

______________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

Третье решение. Подставим в квадратный трехчлен:

Так как и —– корни, то а по теореме Виета получаем, что

Занумеруем города числами 0, 1, 2, …, 29 так, чтобы изначально у нас был цикл Добавим 9 авиалиний …, (а 10-ю авиалинию добавим какую угодно).

Покажем, что условие выполняется. Возьмем любые два города и От можно не более чем за 1 перелёт добраться до города с номером, кратным 3. Аналогично, от можно не более чем за 1 перелёт добраться до города с номером, кратным 3. А между городами и либо есть путь не более, чем из двух перелётов, так как все города с номерами, кратными 3, соединены с городом номер 0.

Вычтем из второго равенства первое и разложим левую часть на множители, получим:

Не умаляя общности (в условии имеется циклическая симметрия переменных ), будем считать, что —– наибольшее из данных чисел. Тогда но из (*) видим, что Значит, Аналогично Тогда из (*) следует Получается

Обозначим так что тогда (*) принимает вид Нам нужно доказать, что

Заметим, что так как это неравенство преобразуется к виду (или следует из неравенства о среднем арифметическом и среднем геометрическом). Отсюда и далее

Получаем откуда и поэтому

Остаётся показать, что невозможно. Если то и тогда в предыдущем рассуждении мы получим строгое неравенство Значит, возможно лишь при Рассмотрим этот случай отдельно.

В этом случае и Тогда

что противоречит первому равенству из условия задачи.

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

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

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

Отразим относительно получим точку лежащую на и такую, что — середина и Аналогично, точка симметричная относительно такова, что — середина и

Так как имеем Аналогично Значит, — параллелограмм. В треугольнике точки и — середины сторон. Отметим также середину стороны тогда — параллелограмм. Получается, что совпадает с т.е. — середина Так как и — середины и имеем векторное равенство

Тогда по неравенству треугольника () получаем что равно Этим доказано нужное неравенство.

Первое решение. Назовём числа 0, 1, …, 49 маленькими, а остальные числа, которые могут появиться на табло, т.е. числа 50, 51, …, 99 — большими. Заметим, что после нажатия из маленького числа обязательно получается большое, а из большого числа — маленькое. Значит, после нечётного количества операций на табло будет гореть большое число.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Выстроим все целые числа от 0 до 99 в цепочку

Заметим, что если какое-то число горит на табло, то следующим числом может быть только соседнее число в цепочке. Но так как числа 0 и 25 стоят в цепочке на местах одной чётности, получить из числа 0 число 25 за нечётное количество шагов невозможно.

По условию и , поэтому — основания трапеции. Пусть и — середины и так что — средняя линия трапеции

При этом параллельна основаниям, поэтому и значит, — серединный перпендикуляр к Значит, центр окружности лежит на прямой

Положим

Из параллельности следует, что , поэтому .

Видим, что треугольник — прямоугольный (), а значит, — центр окружности

Далее, в прямоугольном треугольнике имеем поэтому , а из равенства углов следует поэтому лежит на прямой

Итак, — общая точка окружностей и лежащая на их линии центров Значит, эти окружности касаются (в точке ).

Пусть прямоугольник разбит на доминошки. Двигаясь слева направо, понимаем, что горизонтальные доминошки объединяются в блоки Далее под блоком понимаем такой блок из двух горизонтальных доминошек.

Назовём хорошим разбиение на доминошки, в котором в каждой доминошке хотя бы одна клетка чёрная. Назовём раскраску хорошей, если при ней существует ровно одно хорошее разбиение.

1) Приведём пример хорошей раскраски, в которой 120 чёрных клеток. Красим первый столбец белым, следующие 3 столбца — черным, пятый столбец — белым, и далее продолжаем с периодом 5.

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

Покажем, что оно единственно. Посмотрим на границу между 5-м и 6-м столбцами. Эта граница не может находиться внутри блока, значит, эта граница обязательно должна присутствовать в разбиении и отрезать прямоугольник Далее продолжим аналогичные рассуждения с отрезанием прямоугольников Остаётся разобраться, как может быть устроено хорошее разбиение для прямоугольника В первом столбце не может быть вертикальная доминошка, поэтому в 1-м и 2-м столбцах точно находится блок. Аналогично в 4-м и 5-м столбцах находится вертикальный блок. Тем самым хорошее разбиение однозначно восстановлено. Обоснование того, что наша раскраска хорошая, завершено.

2) Оценка. Рассмотрим хорошее разбиение прямоугольника В каждом блоке не более двух чёрных клеток, иначе мы можем заменить две горизонтальные доминошки этого блока на вертикальные, и разбиение останется хорошим.

В вертикальной доминошке может быть одна чёрная клетка или две чёрных клетки. В первом случае вертикальную доминошку назовём светлой, а во втором — тёмной. Если у нас тёмных доминошек, то в них чёрных клеток, а остальная площадь разбита на блоки и светлые доминошки, т.е. в ней не более половины площади занимают чёрные клетки. Итого чёрных клеток не более

Остаётся понять, что тёмных доминошек не более 20. Вертикальная доминошка не может граничить с тёмной доминошкой, иначе эту пару можно заменить на блок (из двух горизонтальных доминошек), и разбиение останется хорошим. Значит, граничить с тёмной доминошкой может только блок. К одному и тому же блоку слева и справа не могут примыкать две тёмные доминошки, иначе в образованном ими прямоугольнике можно заменить все доминошки на горизонтальные, и разбиение останется хорошим. Рассмотрим две ближайшие друг к другу тёмные доминошки. Промежуток (по горизонтали) между ними не может составлять 0, 1, 2 или 3 клетки (в последнем случае два блока, соседних с этими тёмными доминошками, должны пересекаться, что невозможно). Суммируя длины промежутков для пар ближайших тёмных доминошек, получаем, что количество вертикалей не менее

Но оно равно 100. Отсюда и что невозможно при Неравенство установлено. Доказательство оценки завершено.

Докажем индукцией по что в хорошей раскраске нет четырёхугольника, в котором соседние вершины имеют противоположные цвета (будем называть такой четырёхугольник гадким).

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

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

Если же вершина соединена ребром не со своим соседом — белой вершиной (не умаляя общности, вершины идут так: ---- то в одном из многоугольников, на которые делит ребро исходный многоугольник, есть гадкий четырёхугольник но раскраска при этом должна остаться правильной. По предположению индукции получаем противоречие.

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

(выбрать начало чёрного блока — способов, а после этого белого — способ).

Заметим, что все такие раскраски подходят, а значит, всего существует хороших раскрасок.

Положим тогда Достаточно показать, что все числа  – целые. Заметим, что и то есть Значит, при

Так как одно из чисел делится на то при число  – целое.

Пусть — центр общей вписанной окружности треугольников и . Так как — середина дуги , точки лежат на одной прямой. Окружность вписана в угол поэтому — биссектриса угла а точка — середина дуги Сформулируем и докажем следующее утверждение.

_________________________________________________________________________________________________________________________________________________________________________________

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

Доказательство 1. Из равенства углов

следует искомая вписанность.

____________________________________________________________________________________________________

Доказательство 2. Заметим, что Тогда описанная окружность треугольника касается прямой поэтому Аналогично Следовательно, точке лежат на одной окружности.

____________________________________________________________________________________________________

Лемма доказала вписанность Аналогично, четырёхугольник — вписанный. Если то конструкция симметрична относительно прямой и утверждение задачи очевидно. Рассмотрим точку пересечения и Приравнивая произведения отрезков секущих для окружностей и (т.е. степень точки относительно окружностей), получаем равенства

Из следует, что точки лежат на одной окружности.

Достаточно доказать утверждение: многочлен делится на Действительно, после деления (например, столбиком), в частном получится многочлен с целыми коэффициентами, и тогда равенство многочленов влечет равенство из которого следует утверждение задачи, поскольку — целое число.

Для доказательства утверждения сделаем замену положим и докажем, что делится на т.е. что последние два коэффициента многочлена равны

Свободный член многочлена равен Поскольку в многочлене коэффициент при равен коэффициент при многочлена равен Из условий следует, что удвоенный коэффициент при равен Тем самым, задача решена.

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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