ПитерГор - задачи по годам → .01 ПитерГор 2014 и ранее

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

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

Мы поняли, что меньше, чем прямыми, мы не покроем все узлы. Тогда вопрос, хватит ли нам вертикальной прямой(если забыли почему столько, посмотрите начало решения)? Давайте докажем лемму, что на самом деле если мы покрыли все узлы вертикальными прямыми, то мы можем покрыть все узлы и прямой. Но сделаем это немного по-хитрому.
Лемма. Если салфетку можно накрыть вертикальными прямыми, то самая левая и самая правая из них содержат ровно по одному узлу, накрытому салфеткой.
Доказательство. Предположим, что это не так. Рассмотрим проекции двух смежных сторон салфетки на горизонтальную прямую. Обозначим их за и Тогда на одной из крайних прямых оказалось два или более узла. В таком случае прямая отсекает от салфетки прямоугольный треугольник с гипотенузой, не меньшей Высота этого треугольника не превосходит (так как мы рассматриваем самую правую прямую). Рассмотрим треугольник, который будет образован вертикальной прямой, проходящей через самую правую верхнюю или нижнюю вершину. Образовался снова прямоугольный треугольник подобный нашему исходному. Его же гипотенуза не превосходит диагонали квадрата, а высота равна или и значит, не меньше Мы знаем, что Тогда

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

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

Пусть — почтенное число. Тогда сумма его делителей, отличных от равна У числа заведомо есть делители

Все они различны и отличны от а их сумма равна

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

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

Пусть и Тогда по условию

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

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

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

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

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

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

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

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

Здесь как раз применяем, что В итоге, противоречие.

Заметим, что по свойству касательной а по свойству вписанных углов

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

Последний переход сделан с помощью неравенства о средних, откуда получаем неравенство из задачи.

Решение 1.
Предположим, что множество состоит только из простых чисел. Тогда все числа из множества нечётные(так как любое число вида составное при ). Возьмём в множестве два произвольных числа Если даёт остаток при делении на то также даёт остаток Тогда делится на 3 и по нашему предположению не может принадлежать множеству Значит, в этом случае множеству принадлежит число Аналогично если даёт остаток при делении на то также даёт остаток составное и тогда в этом случае множество должно содержать число
Если множество содержит хотя бы одно простое число дающее остаток при делении на то в множестве как мы установили, содержится число вида дающее остаток Тогда число тоже принадлежит Заметим, что это число даёт при делении на тот же остаток, что и число Но это число делится на по малой теореме Ферма, значит, оно составное.
Аналогично, если простое число даёт остаток при делении на то в множестве содержится число которое по тем же причинам делится на
Решение 2.
Предположим противное. Как и в первом решении установим, что если (mod ) принадлежит то также принадлежит В частности, в есть числа, сравнимые как с так и с по модулю
Рассмотрим простые числа и из Тогда в содержится простое число

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

делится на поскольку по малой теореме Ферма и, значит,

Таким образом, число принадлежит и является составным. Противоречие.

Пример.

Два возможных примера показаны на рисунке.

Оценка.
Решение 1.
Рассмотрим произвольного ребёнка. Если он не видит уха, то он смотрит в чей-то затылок. Тогда стоящий перед ним либо видит чьё-то ухо, либо также смотрит в затылок. Таким образом, мы получаем цепочку из стоящих в ряд детей, в которой самый первый ребёнок видит чьё-то ухо. Заметим, что в этой цепочке не более ребёнка. Поскольку общее количество детей равно то цепочек не меньше чем Значит, их хотя бы Стало быть, как минимум ребёнка видят чьё-то ухо.
Решение 2.
Рассмотрим произвольного ребёнка. Пусть для определённости он смотрит "вправо"(см. рис). Если он не видит уха, то он смотрит в чей-то затылок. Тогда стоящий перед ним также смотрит вправо и т.д., но самый правый ребёнок в этой строке должен смотреть вверх или вниз. Поэтому в этой строке есть хотя бы один ребёнок, который видит чьё-то ухо. Таким образом, если в какой-то строке есть ребёнок, смотрящий “горизонтально”, то в этой строке есть ребёнок, который видит ухо.

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

Рассмотрим теперь случай, когда в какой-то строке нет детей, смотрящих "горизонтально". Следовательно, они все смотрят "вертикально"и поворотом доски на этот случай сводится к уже рассмотренному.

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

Решение 2.
Не умаляя общности, можно считать, что Обозначим через середину дуги Тогда

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

Первое решение

Без ограничений общности будем считать, что указанный отрезок соединяет середины сторон и Введем вектора таким образом, что

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

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

Поскольку имеем

следовательно, диагонали исходного четырехугольника так же равны.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение

Пусть и — середины сторон соответственно и четырёхугольника Из признака равенства треугольников по двум сторонам и медиане, проведённой к третьей следует равенство треугольников и поэтому а значит, Треугольники и равны по трём сторонам, поэтому Тогда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отметим середину стороны

Заметим, что по лемме 255 точки и лежат на прямых и соответственно. Следовательно, прямые и пересекают в точке лежащей на

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

На продолжении отрезка за точку отложим отрезок равный Тогда

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

Так как — внешний угол равнобедренного треугольника то

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

что равносильно

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

Пусть и нашлись два не взаимно простых элемента набора и пусть — некоторый общий простой делитель. Пусть — некоторые элементы набора. Тогда

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

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

следовательно, кроме этого

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

в силу получили противоречие.

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