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

Заметим, что для подойдёт Для подойдёт

Предположим, что для нашлось требуемое число Тогда число

является точным квадратом. Поскольку

числа и взаимно просты. Раз число нечётно, числа и также взаимно просты. Следовательно, числа и — точные квадраты. В частности, число при делении на 3 может давать лишь остаток 0 или 1, а тогда число не делится на 3. Отсюда

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

Противоречие.

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

число

представляется в виде произведения и нескольких множителей вида где и

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

Поскольку и число не может делиться на Таким образом, — степень двойки, не превосходящая Следовательно, делится на НОД и а, значит, делится и на Поскольку чётно, числа и не имеют общих делителей, отличных от 1, значит, что и требовалось.

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

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

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

Опишем выигрышную стратегию Васи. Пусть Вася все время пишет букву «Ю» в клетку согласно следующим ниже условиям; а если указанная клетка не существует или уже занята, а также если Петя ставит любую букву отличную от «П», «Е», «Т», «Я», то пусть Вася ставит «Ю» в любую свободную клетку.

Если Петя в некоторой клетке пишет букву «П», то Вася пишет «Ю» в клетке, соседней с ней справа; если Петя пишет букву «Е», то Вася пишет «Ю» в клетке, соседней с ней слева; если Петя пишет букву «Т», то Вася пишет «Ю» в клетке, соседней с ней снизу; если Петя пишет букву «Я», то Вася пишет «Ю» в клетке, соседней с ней сверху.

Из первых двух условий следует, что в двух соседних по горизонтали клетках не могло появиться «ПЕ», читаемое слева направо. В самом деле, предположим, что горизонтальное «ПЕ» появилось; тогда после появления первой из этих двух букв Вася, согласно описанной стратегии, сразу займёт место второй из этих букв — противоречие. Аналогично, в двух соседних по вертикали клетках не могло появиться «ТЯ», читаемое сверху вниз.

Поскольку

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

для этого достаточно установить равенство направленных углов

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

Остаётся доказать равенство Из счёта углов получаем

Аналогично

Значит, эквивалентно равенству

или

Из касания окружностей и следует

что из суммы углов четырёхугольника равно

Тем самым, преобразуется к виду

что верно.

Рассмотрим граф, вершинами которого являются отмеченные точки, а рёбрами — проведённые отрезки.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Подграф с новыми числами на рёбрах удовлетворяет условию с той же константой

Доказательство леммы. Заметим, что для каждого -рёбра есть одно и то же количество -шестёрок, в которые входят оба его конца. И наоборот, для любой -шестёрки среди 15 рёбер между её вершинами есть одно и то же количество -рёбер. То же верно для -рёбер и для -рёбер. Значит, сумма чисел на рёбрах в -шестёрке в новой расстановке есть среднее сумм по всем -шестёркам в старой расстановке, то есть среднее нескольких чисел, не больших – значит, Аналогичное утверждение верно для сумм в -шестёрках. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Далее изучаем новую расстановку. Рассмотрим случаи.

Случай Иными словами, есть ровно одна -шестёрка, на которой пятнадцать -рёбер, и шесть -шестёрок, на каждой из которых десять -рёбер и пять -рёбер. Имеем систему неравенств:

Умножим первое на сложим со вторым, умноженным на 3, получим откуда

Случай Теперь у нас две -вершины и пять -вершин, то есть на -шестёрке есть десять -рёбер и пять -рёбер, а на -шестёрке – шесть -рёбер, восемь -рёбер и одно -ребро. Имеем

Исключая получаем

значит,

Случай Аналогично предыдущему, имеем

Избавляясь на этот раз от получаем откуда

Случаи сводятся к рассмотренным умножением всех чисел на что ведёт к замене Итак, оценка доказана.

Пример. Любое число вершин от двух до 999995 объявим вершинами типа остальные – вершинами типа На всех рёбрах между двумя вершинами типа напишем число на всех остальных – число 1. Тогда, если в шестёрке вершин хотя бы пять -вершин, то сумма в ней не больше а иначе – не меньше

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

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

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

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

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

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

Пусть то

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

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

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

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

______________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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