Закл (финал) 10 класс → .09 Закл 2022

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

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

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

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

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

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

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

и

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

______________________________________________________________________________________________________________________________________________________

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

и

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

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

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

и

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

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

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

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

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

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

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

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

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

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

2)

3) кратно

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

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

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

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

кратно

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

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

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