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

Обозначим через окружность с диаметром Поскольку и точки и лежат на

Обозначим через центр вписанной окружности треугольника Если точка лежит внутри угла то углы и тупые, поэтому:

Перемножив эти неравенства, получим:

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

Поскольку четырёхугольник вписан в окружность с диаметром имеем:

а также

Отсюда следует: а значит,

Кроме того, поскольку длина хорды окружности не превосходит длины диаметра:

откуда

Следовательно:

Если удалить полностью 51 кучку, то, очевидно, не останется много камней. Значит, искомое значение меньше 5100. (Альтернативно, можно удалить из всех кучек по 51 камню.)

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

Покажем, что при …, то есть кучки с номерами от 51 до 100 удовлетворяют требованию.

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

Противоречие.

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

Рассмотрим гомотетию с центром переводящую в При такой гомотетии точка переходит в а точка — в Отсюда и

Но и Значит,

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

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

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

______________________________________________________________________________________________________________________________________________________

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

Доказать это можно аналогично решению задачи: имеем (в направленных углах)

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

______________________________________________________________________________________________________________________________________________________

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

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

раз.

Иначе говоря, найдутся измерений таких, что (1) в них прибор показывает один и тот же вес и (2) во всех десятках, использованных в этих испытаниях, есть две общих гири и Мы покажем, что при выполнении условий (1) и (2) суммарный вес и обязательно равен то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовём десятки, использованные в этих измерениях, нужными.

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

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

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

Итого, получаем

Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

он узнает вес гири

Первое решение.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

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

По лемме о трезубце — середина отрезка . Поскольку и , то

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

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

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

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

Если то Поскольку меньший корень не меньше больший корень не меньше а тогда Если же то В обоих случаях требуемая оценка доказана.

Осталось заметить, что трёхчлен имеет корни и поэтому подходит.

_________________________________________________________________________________________________________________________________________________________________________________

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

Поскольку корни различны, дискриминант положителен. Следовательно, и, значит, Поэтому Пусть где — натуральное число.

Предположим, что Тогда и Стало быть,

и, значит, Следовательно, и

Это противоречие показывает, что

Если же то при и трёхчлен имеет корни и

Первое решение. Будем называть индекс плохим, если или Заметим, что если среди индексов нет плохих, то последовательность монотонна.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

Мы всегда считаем, что площадь торта равна

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

Осталось доказать, что детей всегда смогут получить желаемое. Пусть

— длины сторон кусков, которые хотят получить дети, то есть

Покажем, что из квадрата можно вырезать куски со сторонами

Для этого нам потребуются неравенства

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

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

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

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

рейсов. Если группа из всех 998 городов критическая, то в стране уже рейсов.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть и — критические группы. Тогда группа также критическая.

Доказательство. Положим

Пусть

тогда По условию, имеем

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Пусть касается и в точках и соответственно, а касается отрезков и в точках и соответственно. Заметим, что

Аналогично, если вписанная окружность треугольника касается в точке то

Однако

так что и потому

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

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

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

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

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

В оставшемся случае имеем при некоторых простом Если то при некотором положительном и натуральном Тогда число

делится на а частное от деления больше поскольку Поэтому можно положить

Наконец, если то причём по условию. Тогда где обе скобки больше в этом случае работает

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

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

Тогда число нечётно и является квадратом, поэтому оно даёт остаток при делении на

Перепишем равенство выше в виде

и рассмотрим его по модулю Нетрудно проверить, что четвёртые степени целых чисел дают лишь остатки и при делении на то есть правая часть равенства даёт остаток или Левая же часть сравнима с где — количество нечётных чисел среди Значит,

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

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

В силу симметрии, а также — поэтому точка лежит на прямой Из вписанности четырёхугольников и получаем, что Таким образом, Это означает, что трапеция — равнобокая, поэтому

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

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

По теореме Монжа из этого следует, что перпендикуляры из на из на и из на пересекаются в одной точке. Но первые два перпендикуляра пересекаются в точке значит,

Положим . Тогда а поскольку числа целые, имеем Если мы теперь покажем, что

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

Пусть для определенности Оценим подкоренное выражение в левой части доказываемого неравенства:

Квадрат правой части доказываемого неравенства равен

Сравнивая эти выражения, видим, что достаточно показать, что

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

Обозначим через карту значения

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

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

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

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

Пусть и — хорошие пара и тройка элементов последовательности. Тогда НОД НОД

Доказательство проведём индукцией по наибольшему индексу среди и Если утверждение тривиально. Для перехода предположим, что Число лежит либо только в паре либо только в тройке либо в обеих.

Случай Пусть — только элемент пары; скажем, Тогда, поскольку число делится на то есть НОД НОД НОД по предположению индукции.

Случай Пусть — только элемент тройки; скажем, Аналогично, делится на так что НОД НОД по предположению индукции.

Случай Пусть — элемент и пары, и тройки; скажем, Тогда делится на так что НОД НОД НОД НОД по предположению индукции. Переход индукции доказан.

Поскольку а прямая касается окружности имеем Следовательно, то есть четырёхугольник — вписанный.

Значит,

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