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

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

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

Видим, что прямоугольные треугольники и равны (симметричны относительно ), и поэтому

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

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

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

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

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

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

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

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

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

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

Предположим, что число чётно, и рассмотрим два случая.

1) Число нечётно. Тогда центральный переход в цепочке имеет второй тип. У правой нижней клетки диагонали нечётный номер, поскольку число нечётно, а чётно. Левая верхняя клетка диагонали тоже имеет нечётный номер, поэтому при переходе первого типа чётность числа меняется. Пусть с числа переход первого типа происходит на число Тогда по модулю переходы первого типа выглядят так: …, Суммы чисел в этих парах являются последовательными нечётными числами, поэтому при делении на они дают все нечётные остатки по два раза. В частности, есть переход, в котором сумма чисел равна по модулю Как показано выше, эта сумма равна Но тогда для этого перехода симметричный ему тоже имеет первый тип и содержит те же самые числа, то есть один из переходов повторился, чего быть не должно.

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

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

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

Но и Значит,

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

При имеем

Пусть теперь и пусть

делится на где …, Имеем

где Заметим, что число

должно делиться на Но

значит, не делится на Противоречие.

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

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

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

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

Первое решение. Назовём дискриминантом пары чисел величину

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

Далее, верны следующие соотношения:

и

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

______________________________________________________________________________________________________________________________________________________

Второе решение. Если на доске написана пара то с помощью первой операции можно добавить пары

Обе этим пары можно записать как

где в первом случае а во втором — С помощью второй операции можно добавить только пару

______________________________________________________________________________________________________________________________________________________

Лемма. На каждом шаге для любых целых таких, что для любой пары чисел написанной на доске, выполняется неравенство

Для пары утверждение задачи верно. Далее, рассмотрим два типа операций:

Тогда для новой пары верно

Здесь также получаем нужное неравенство:

______________________________________________________________________________________________________________________________________________________

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

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

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

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

Пример. Осталось доказать, что Василий может достичь указанных значений

______________________________________________________________________________________________________________________________________________________

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

Доказательство. Утверждение леммы не зависит от конкретного расположения точек, так что можно считать, что точек расположены в вершинах правильного -угольника, а оставшаяся точка — в его центре

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

Теперь Василий может сначала пометить все отрезки множества числом 1, затем все отрезки второго множества числом 2, и т. д.

_________________________________________________________________________________________________________________________________________________________________________________

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

то есть Василий получит пометку

Пусть теперь чётно. Выберем две отмеченных точки и пусть

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

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

соответственно. Далее Василий проводит отрезки

аналогично, он пометит их числами

соответственно.

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

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

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

(из упомянутых выше касания и параллельности). Значит, четырёхугольник вписанный. Имеем

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

откуда Значит, прямые и ограничивают параллелограмм, откуда Так как

то точка лежит на окружности Раз то окружность касается отрезка в точке что и требовалось.

Второе решение. Обозначим через центр окружности пусть — её радиус и — расстояние от точки до прямой Обозначим через центр окружности пусть — её радиус и — расстояние от точки до прямой Мы докажем более общий факт:

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

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

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

Обозначим через углы при вершинах и параллелограмма Разберём случай в других случаях рассуждение аналогично. Тогда

поэтому равнобедренные треугольники и подобны, откуда и

(последнее равенство следует из теоремы Фалеса). Следовательно, треугольники и подобны по углу и отношению заключающих сторон. Значит,

и Тогда следовательно,

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

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

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

Поскольку окружность касается отрезка в точке и Значит,

Мы позднее докажем, что отсюда следует равенство

сначала завершим решение задачи с его помощью: отметим на отрезке точку так, что

и

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

В случае, когда совпадает с одним из концов отрезка возможна лишь ситуация и тогда то есть а также Итого, окружность касается в точке

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

и

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

После возведения в квадрат и сокращения общих слагаемых, получается симметричное по и равенство:

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

а это в точности соотношение что и требовалось.

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

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

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

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

Отметим следующее:

1) следовательно при всех

2)

3) кратно

Из свойства 1) следует, что для различных номеров из имеет место оценка

Сопоставляя это со свойством 2), получаем, что Таким образом, все элементы кроме, быть может, одного, больше, чем Обозначим (удалили из наименьший элемент), тогда и

Пусть — два элемента множества Тогда по свойствам 1), 2) имеем

С другой стороны, по свойству 3) число

кратно

Положим (где обозначает верхнюю целую часть). Хотя бы одно из чисел кратно и хотя бы одно кратно Кроме того, если нечётно, то нечётны числа поэтому одно из чисел не кратно другое, соответственно, кратно Иначе не кратно 5, и аналогичным образом получаем, что одно из чисел кратно

Рассмотрим пятиэлементное подмножество наименьший элемент обозначим а наибольший Обозначим Если нечётно, положим иначе положим Из доказанного следует, что элементы множества дают не более двух различных остатков по модулю и не более двух различных остатков по модулю Значит, в найдутся два различных элемента такие, что кратно Тогда по (1) получаем

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

Первое решение. Рассмотрим граф, в котором вершины это города, ребра — авиалинии, причем ребра, соответствующие авиалиниям -ой компании, покрашены в -й цвет.

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

Оценка. Докажем индукцией по что в графе отсутствует хотя бы ребер; из этого следует, что ибо иначе ребер бы не было, и графе был бы связным. База при очевидна.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Будем обозначать окружность, описанную около треугольника

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

Лемма. делится на

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

Если не делится на то по теореме Эйлера откуда Если же делится на то делится на а значит, и тоже. В любом случае делится на что и требовалось.

_________________________________________________________________________________________________________________________________________________________________________________

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

при бесконечном количестве целых значений (где ).

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

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

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

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

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

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

При корней нет, так как на указанном интервале левая часть неотрицательна, а правая — отрицательна.

При все модули раскрываются со знаком “”, поэтому уравнение примет вид где Поскольку это квадратное уравнение имеет единственный корень на промежутке

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

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

Первое решение. Докажем, что при любом чётном одно из чисел и плохое; из этого, очевидно, следует требуемое. Предположим противное. Тогда и Иначе говоря, и Но отсюда следует, что это невозможно, ибо Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. При утверждение задачи очевидно, поэтому будем считать, что

______________________________________________________________________________________________________________________________________________________

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

Доказательство. Пусть — остаток от деления на Тогда

то есть одно из чисел делится на Но это невозможно при ибо

______________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Мы опять же исследуем лишь случай

Пусть — некоторый простой делитель числа Положим тогда при любом имеем то есть делится на

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

Итак, либо не делится на (и, значит, на ), либо не делится на (и, значит, на ). Поэтому среди чисел бесконечно много плохих.

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

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

(1) при всех

(2)

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

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

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

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

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