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

Легко видеть, что если то всякий многочлен с коэффициентами от 0 до является нулевым.

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

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

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

Поэтому достаточно доказать, что

Пусть — наименьшее из чисел. При имеем

Пусть то

Так как а значит, скобки из суммы неотрицательны. Следовательно,

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

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

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

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

______________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

Таким образом, выигрывает Илья.

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

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

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

что эквивалентно:

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

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

Пусть описанная окружность треугольника является единичной с центром в нуле. Поскольку имеем откуда С другой стороны Решая систему на и находим Аналогичное выражение получается для

Отметим на прямой точку так, что тогда откуда Вспомнив, что находим

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

Аналогично Наконец, можно посчитать двойное отношение

Последнее выражение действительно вещественное, что сразу следует из подстановки

Пусть — наибольший делитель числа меньший, чем Тогда где — наименьший простой делитель числа Имеем Число в правой части не делится на поэтому Отсюда следует, что нечётно, а тогда и нечётно. Поскольку делится на

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

Если то откуда и

Если же то и число делится на что невозможно.

Пусть — середина дуги окружности тогда

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

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

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

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

Выберем некоторое и положим

делится на и делится на

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

С другой стороны, по условию имеем

Складывая и получаем

откуда или

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

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