Каждому остатку от деления на 19 сопоставим остаток такой, что

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

Обозначим теперь через множество чисел из условия, не содержащих цифр , а через — множество таких чисел, не содержащих . Каждому числу сопоставим число . Заметим, что — цифра (причём ), так что получилось 100 -значное число. Кроме того,

так что делится на 19 и . Поскольку разным числам из соответствуют разные числа из , количество чисел в не меньше, чем в .

Наконец, каждому числу соответствует число , которое по аналогичным причинам лежит в . Отсюда следует, что количества чисел в и равны.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значит,

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

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

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

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

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

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

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

Оценка. Заметим, что значит, Но и  – целые числа, поэтому Следовательно,

Стало быть, то есть

Пример. Оценка достигается при

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

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

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

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

и Следовательно, — касательная к окружности, описанной около треугольника

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

Перемножив равенство

и неравенство

получим неравенство

Возведем теперь в квадрат равенство

Получим

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

или

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

Но, если вычесть из квадрата равенства равенство получится равенство

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

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

Итак, то есть — ортоцентр треугольника

Докажем индукцией по

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

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

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

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

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

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

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

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

База. Для полного графа с тремя вершинами утверждение очевидно.

Шаг индукции. Рассмотрим полный граф с вершиной. Удалим из рассмотрения одну вершину с выходящими из неё ребрами. Для оставшегося графа с вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Возможны два случая.

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

2) Не все рёбра цикла окрашены в один цвет. Пусть в цикле есть две одноцветные части: (красная) и (синяя). Посмотрим на цвет ребра Если это ребро красное, то цикл — искомый, если же оно синее, то искомым будет цикл

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

Пусть у последних двух уравнений общий корень . Тогда и . Значит корень и . Отсюда . Если , то у уравнения нет корней ?! Значит . Подставим 1 во все уравнения, где корень и получим и . Значит .