Закл (финал) 11 класс

На -м шаге у каждого из человек было выписано одно из чисел множества

На -м шаге — одно из чисел множества

На -м шаге выписано одно из чисел множества

где — сумма всех чисел (а вычитается — число на оставшейся в конце карточке).

Видим, что так что Далее, но числа принадлежат значит,

Итак, мы показали, что чисел, выписанных на -м, -м и -м шагах, могут принимать не более различных значений. Следовательно, какие-то два из них равны.

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

Обозначим через центр описанной окружности треугольника Заметим, что Тогда

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

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

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

Аналогично Тогда

Последнее выражение очевидно вещественное, что и требовалось доказать.

Первое решение. Покажем, что при данных условиях на многочлен каждая следующая точка касания лежит по другую сторону от оси чем предыдущая.

Пусть — данный многочлен, — его производная. Пусть — это -я точка касания, а -я. Тогда касательная в точке имеет уравнение Значит, откуда Разделив это равенство на и перенеся все слагаемые в правую часть, получим при четной степени выражение:

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

______________________________________________________________________________________________________________________________________________________

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

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

Для есть пример:

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

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

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

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

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

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

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

(A) Монеты упорядочены по возрастанию масс и все весы (в том числе, испорченные) показывали правильные результаты во всех взвешиваниях.

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

Рассмотрим два случая:

В последнем, м взвешивании, не участвует монета с номером Предположим, что опять перевесила монета с большим номером. Тогда каждая из ситуаций (А) и (Б) по-прежнему возможна.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Обозначим через ответ в задаче; положим Докажем сначала, что

После отмечания исходных клеток можно отметить хотя бы одну клетку ; это значит, что либо в столбце, либо в строке этой клетки уже отмечено других клеток - пусть для определённости в строке

Мысленно отметим все клетки строки Ясно, что любую клетку по-прежнему можно отметить. Удалим из клетчатой плоскости строку и сдвинем вместе две получившиеся полуплоскости так, чтобы снова получилась клетчатая плоскость. Теперь мы можем отметить любую клетку этой новой плоскости, отмечая на каждом шагу клетку, в кресте которой уже есть не менее отмеченных клеток (поскольку из этого креста удалена одна клетка строки ). Следовательно, изначально на этой плоскости должно было быть отмечено не менее клеток. Значит, на исходной плоскости сначала должно быть хотя бы отмеченных клеток не из ; отсюда и следует

Поскольку из доказанного неравенства (*) следует, что

Осталось показать, как отметить клеток так, чтобы затем можно было отметить любую другую клетку плоскости. Покажем по индукции, что подходит пример, показанный на рисунке, состоящий из двух «лесенок» высот и ; нетрудно понять, что в нём как раз клеток. При утверждение очевидно: при одной отмеченной клетке можно отметить любую клетку в её кресте, а затем и любую клетку вообще.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Пусть тогда найдутся такие числа и что Так как старший коэффициент многочлена всегда положителен, то этот многочлен возрастает, поэтому

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

Обозначим Напомним, что частный случай неравенства Бернулли (при ) можно переписать в виде (при ).

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Для любого натурального п верны неравенства

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

откуда

______________________________________________________________________________________________________________________________________________________

Лемма 2. Для любого натурального п верны неравенства

Доказательство. Поскольку достаточно доказать, что или

Применяя лемму получаем

что доказывает левое неравенство. Аналогично, для правого имеем

______________________________________________________________________________________________________________________________________________________

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

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

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

Случай следует из симметрии; без ограничения общности будем считать, что

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

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

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

По неравенству о средних

В условии требуют доказать, что левая часть этого неравенства не меньше 1, поэтому достаточно доказать, что правая часть (оценка снизу) не меньше 1, то есть

В силу положительности чисел неравенство эквивалентно возведённому в квадрат

Здесь последовательная пара скобок слева не меньше соответствующей скобки справа. Например,

поскольку

Аналогично с остальными скобками.

Мы докажем, что существуют даже числа удовлетворяющие следующим (более сильным) условиям:

при всех

отношение любых двух из чисел является степенью двойки (с целым показателем).

Заметим, что доказываемое утверждение не изменится, если какое-то из чисел (а с ним и соответствующее умножить на некоторую степень двойки. Умножим каждое из чисел на степень двойки так, чтобы все полученные числа лежали в промежутке

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

Поскольку для любых и выполнено неравенство каждая из последовательностей удовлетворяет Кроме того, каждая из последовательностей, очевидно, удовлетворяет Осталось показать, что хотя бы одна из них удовлетворяет

Для этого заметим, что произведение всех чисел во всех последовательностях равно

Следовательно, произведение чисел хотя бы в одной из последовательностей не превосходит что и требовалось.

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

Пусть — серединный перпендикуляр к отрезку Тогда (поскольку на каждой такой сфере лежат обе точки Легко видеть, что поскольку обе перпендикулярны прямой Аналогично определим плоскости для и для Поскольку шесть выбранных плоскостей попарно параллельны, то они образуют параллелепипед, осталось заметить, что его вершинами будут точки Действительно, каждая точка лежит в плоскостях (например), откуда и следует нужное. Учитывая, что диагонали параллелепипеда пересекаются в одной точке, всё доказано.

Рассмотрим производные изначальных многочленов: Обе производные имеют нули в

Теперь докажем следующую лемму:

_________________________________________________________________________________________________________________________________________________________________________________

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

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

 1) Значит, — ноль функции

 2) Значит, — ноль функции

 3) Значит, — ноль функции

 4) Значит, — ноль функции 

______________________________________________________________________________________________________________________________________________________

Лемма доказана. Вернемся к исходной задаче. По лемме мы получаем, что каждая новая функция на доске будет иметь ноль производной в точке Но рассмотрим функцию, которую мы хотим получить: Заметим, что у ее производной не имеется нуля в точке Значит, по лемме мы не можем получить такую функцию.

Пусть — середина дуги окружности тогда

Получается, по условию и как вписанные углы, опирающиеся на одну дугу. Значит, треугольники и равны, и они совмещаются поворотом Ф с центром в точке на угол Отсюда, в частности, следует, что и А из последнего равенства углов следует, что четырёхугольник вписан в некоторую окружность .

Описанные окружности и треугольников и также совмещаются поворотом Ф. Пусть и – середины дуг и этих окружностей(не содержащих ). Тогда то есть точка лежит на серединном перпендикуляре к а так же

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

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

Первое решение. Утверждение задачи эквивалентно равенству

Значит, ввиду равенств и двух аналогичных, достаточно доказать, что

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

Равенство доказывается аналогично.

Второе решение. Обозначим через и центры сфер и соответственно. Как и в первом решении, введём прямую проходящую через и тогда

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

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

Осталось заметить, что в силу параллельности прямых И треугольнкии и подобны, следовательно,

что в силу свойств основания биссектрисы внешнего угла равно Таким образом,

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

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

Предположим противное, обозначим Тогда все простые делители чисел вида не превосходят

______________________________________________________________________________________________________________________________________________________

Лемма: Пусть при некотором Тогда при всех

Доказательство: Обозначим тогда Заметим, что если В этой сумме все слагаемые, кроме первого, делятся на а первое делится лишь на но не на Значит и делится на но не на

______________________________________________________________________________________________________________________________________________________

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

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

Рассмотрим теперь По доказанному, для любого большого простого Кроме того, поскольку то для любого маленького простого Поскольку все простые делители числа — либо большие, либо маленькие, отсюда следует, что что, очевидно, неверно. Противоречие.

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

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

Положение 1. Пусть точка такова, что является прямоугольником. Тогда является серединой стороны — Пусть — середина стороны Как известно, является ортоцентром треугольника а значит является ортоцентром треугольника и принадлежит

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

Заметим, что

что влечет принадлежность точек и одной окружности.

Наконец, точки и симметричны точке относительно одной из сторон треугольника , следовательно прямая является прямой Штейнера точки относительно треугольника и проходит через ее ортоцентр.

Пронумеруем строки числами сверху вниз, а столбцы — теми же числами слева направо. Клетку будем обозначать парой номеров её строки и столбца; при этом будем считать, что клетки диагонали из плюсов имеют координаты

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

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