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

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

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

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

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

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

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

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

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

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

Пусть — центр вписанной окружности и , тогда образуют прямую, поскольку — середина дуги , кроме того, тогда — середина дуги . Заметим, что , откуда вписан. Аналогично и вписан . Далее если , то картинка симметрична и образуют прямоугольник, иначе , запишем степень точки

Пользуемся вписанностью , и , в итоге вписан из равенства первого и последнего.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

Пусть Заметим, что при всех Значит, поскольку имеет ненулевой корень, он имеет и отрицательный корень, откуда

Далее, поскольку имеем

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

Итак, мы получили, что при всех Это означает, что последовательность — убывающая.

Нас просят доказать неравенство для всех натуральных По условию Перепишем корни в степени и приступим к доказательству:

Сократим на

Заметим, что:

Сократим на величину которая является положительной, поскольку

Осталось заметить, что и потому что и Следовательно, их сумма больше

Рассмотрим момент после третьего хода (когда выписаны три числа). Если к этому моменту никто еще не выиграл, то следующим ходом Вася выигрывает — ему достаточно найти два выписанных числа одной чётности и выписать своим ходом их среднее арифметическое (оно является целым числом).

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

Теперь опишем выигрышную стратегию Васи.

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

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

Разобьём доску на квадратов Покажем, что в каждом квадрате может стоять не более гепардов, не бьющих друг друга — отсюда будет следовать, что общее число гепардов не может превосходить

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

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

Пусть Тогда на доске присутствует дробь

что и требовалось

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

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

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

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

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

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

Заметим, что

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

Если все последовательности, количество букв в которых не меньше и не больше являются словами, то, очевидно, условие задачи соблюдается; при этом количество таких слов равно Осталось показать, что это количество — наибольшее возможное.

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

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

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