Турнир Ломоносова - задания по годам → .02 ТурЛом 2020

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

Покажем, что ничего другого на бумажке написано быть не могло. Чтобы Коля всё сделал правильно с обеих сторон бумажки должны быть написаны числа и Значит, и — суть корни уравнения Подставляя в это уравнение получаем равенство которое можно сократить на так как все числа на бумажке ненулевые. Получаем Но по теореме Виета равно следовательно Откуда, подставляя его в полученное ранее равенство, находим

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

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

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

Но площади этих треугольников равны, так как медиана треугольника делит его на два равновеликих.

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

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

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

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

Тогда

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

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

Для этого разберём три случая: когда является простым, когда является простым, и когда ни , ни не являются простыми (в частности, если нечётно, то не является простым).

_________________________________________________________________________________________________________________________________________________________________________________

Первый случай. Если является простым. Рассмотрим выражение

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

Но перенеся в этом сравнении всё в левую часть, получаем

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

_________________________________________________________________________________________________________________________________________________________________________________

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

все слагаемые кроме будут кратны а это слагаемое — не будет. Значит, и вся сумма не будет кратна , а следовательно, и , то есть . Значит, в этом случае число магическим не является.

_________________________________________________________________________________________________________________________________________________________________________________

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

получаем слагаемые вида , где , и два слагаемых

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

_________________________________________________________________________________________________________________________________________________________________________________

Осталось заметить, что числами, для которых их половина является простым числом, являются те и только те, что перечислены как исключённые в ответе.

Приведём явный пример.

Рассмотрим числа вида

где

Тогда, очевидно, суммы вида

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

Разделим все суммы на три вида: первый вид второй вид третий вид

______________________________________________________________________________________________________________________________________________________

Для начала докажем, что суммы из двух разных видов не равны между собой.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Приведём доказательство для сумм третьего вида, для двух других видов доказательства будут аналогичны.

Пусть есть и такие, что пара чисел не совпадает с парой . Докажем, что не может быть равенства

Действительно, если так, то после подстановки получаем равенство

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

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

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