Регион 11 класс → .08 Регион 2021

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

Положим Тогда и В частности, и, аналогично,

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

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

Обозначим через произведение всех числителей и знаменателей чисел и Тогда при некотором имеем

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

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

Первое решение. Обозначим то есть степени рассматриваемых многочленов равны

Лемма. Существует единственный многочлен степени (со старшим коэффициентам ) такой, что степень полученного многочлена будет меньше, чем

Доказательство. Запишем наш многочлен как

Обозначим и это — многочлены степени со старшим коэффициентом

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

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

имеет степень всего лишь Значит, наименьшая возможная степень и есть

______________________________________________________________________________________________________________________________________________________

Второе решение. Используем те же обозначение и что и в первом решении. Мы будем считать, что

(впоследствии мы увидим, что это возможно; поэтому для многочлена минимальной степени так считать можно).

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

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

то есть где

при этом а предположение означает, что

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

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

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

Пусть многочлен имеет ширину и ось тогда он записывается в виде

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

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

Заметим, что ширина многочлена может принимать значение от 1 до 100, при этом найдется не более одного многочлена с шириной Обозначим количество многочленов с шириной Оценим количество пар многочленов с одинаковой шириной:

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

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

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

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

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

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

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

что противоречит нашему предположению.

_________________________________________________________________________________________________________________________________________________________________________________

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

Пусть — данное число, — его остаток от деления на и от деления на Тогда число делится на и на то есть делится на

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

Первое решение. Сложив данные неравенства, мы получим: Преобразуем данные неравенства к виду:

и

и перемножим (это можно делать, так как их правые части положительны). Имеем:

Так как то то есть Поэтому

Значит, — положительно.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем, что Предположим противное:

( по условию). Не умоляя общности, Сложив данные неравенства, получим т.е. Следовательно, Но тогда — противоречие.

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

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

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

Если или — нечётно, то в этих столбцах нет ни одного коротышки, расстояния от которого до двух выделенных домов одинаковы.

Если а чётно, то в столбце находится один коротышка, расстояния от которого до двух домов одинаковы.

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

Если же то в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно Аналогично, в столбце места, от которых расстояния до и одинаковы, имеют вид где и таких мест ровно

Заметим, что

Значит, какое-то из чисел не больше

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