Регион 11 класс → .10 Регион 2023
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В городе 
прошли 
городских олимпиад по разным предметам. В каждой из этих олимпиад участвовало ровно 
школьников, но не
было двух олимпиад с одним и тем же составом участников. Известно, что для любых 
олимпиад найдется школьник,
который участвовал во всех этих 
олимпиадах. Докажите, что найдется школьник, который участвовал во всех 
олимпиадах.
Источники:
Подсказка 1
Попробуйте решить задачу от противного: предположите, что нет школьника, который участвовал во всех 50 олимпиадах.
Подсказка 2
Тогда полезно посмотреть на пересечения пар множеств участников. Какого минимального размера может быть пересечение двух олимпиад?
Подсказка 3
Если пересечение двух множеств слишком маленькое, то для каждого школьника из него можно найти третью олимпиаду, в которой этого школьника нет.
Подсказка 4
Теперь рассмотрите пересечение выбранных двух олимпиад и олимпиад, в которых не участвуют школьники из их пересечения.
Общее пересечение пусто. А сколько всего олимпиад мы рассмотрели?
Подсказка 5
Пересечение менее 30 олимпиад не может быть пустым, значит, пересечение любых двух олимпиад равно 29.
Подсказка 6
Если множества участников всех олимпиад отличаются
друг от друга максимум одним человеком, то как устроено множество всех олимпиадников?
Подсказка 7
Если есть множество из 31 школьника, то сколько различных 30-элементных подмножеств можно составить из него? Достаточно ли этого, чтобы покрыть все 50 олимпиад?
Предположим противное, и пусть в множестве всех школьников есть различные 
-элементные подмножества
— множества участников каждой олимпиады такие, что пересечение любых 30 из них непусто, а пересечение всех — пусто.
Пусть среди множеств
нашлись два множества 
и 
имеющие 
общих элементов
Для каждого элемента 
среди множеств
найдём подмножество 
не содержащее 
такое подмножество 
найдётся, иначе 
— общий элемент множеств
(Заметим, что среди подмножеств 
могут быть совпадающие.)
Тогда пересечение не более 
подмножеств
— пусто. Это противоречит нашему предположению (к данным подмножествам можно добавить еще несколько, чтобы стало 30 подмножеств, при таком добавлении пересечение остается пустым).
Значит, указанных двух множеств 
и 
не найдётся. Тогда пересечение любых двух из множеств
содержит в точности 
элементов. Пусть
так что
Найдём подмножество (пусть, для определённости, это подмножество — 
), не содержащее 
Так как
то 
обязано содержать все элементы
Этих элементов 
(все они различны), поэтому
Рассмотрим любое подмножество 
из подмножеств 
Предположим, что 
содержит элемент, лежащий вне
-элементного множества
Тогда 
должно пересекаться с каждым из подмножеств 
по одному и тому же 
-элементному подмножеству множества
Но
значит, такого 
-элементного подмножества не существует — противоречие. Отсюда делаем вывод, что все множества 
являются подмножествами множества 
Но в множестве 
количество 
-элементных подмножеств равно 
Получаем
противоречие, завершающее решение задачи.
Ошибка.
Попробуйте повторить позже
Можно ли число 
представить в виде суммы трёх натуральных чисел 
таких, что 
делится на 
и 
делится на
?
Источники:
Подсказка 1
Сравните чётность b + c и b − c + 1. Если они разной чётности, то может ли b + c быть нечётным?
Подсказка 2
Нет, не может, ведь тогда нечётные числа не делятся на чётные.
Подсказка 3
Если нужные a, b, c нашлись, то что тогда известно про делители 2023 = a + b + c?
Подсказка 4
Среди них есть b + c. Может ли тогда b + c быть чётным?
Предположим, такие три числа найдутся. Поскольку 
кратно 
сумма
также кратна 
из чего следует, что 
нечётно. Значит,
— чётное число, и нечётное число 
не может на него делиться.
нельзя
Ошибка.
Попробуйте повторить позже
Даны различные вещественные числа 
и 
Оказалось, что уравнение
имеет три различных вещественных корня 
Найдите корни уравнения
Источники:
Подсказка 1
При работе с многочленами есть несколько инструментов — рассмотреть многочлен (x − a₁)(x − a₂)(x − a₃) − b и записать его через корни c₁, c₂, c₃, или использовать соотношения Виета для корней c₁, c₂, c₃.
Подсказка 2
Если идти первым путём: запишите (x − a₁)(x − a₂)(x − a₃) − b = (x − c₁)(x − c₂)(x − c₃). Что произойдёт, если подставить вместо x число −x?
Подсказка 3
Если идти вторым путём: запишите теорему Виета — b появляется только в свободном члене. Вспомните, что теорему Виета можно использовать и в обратную сторону.
Преобразуйте полученные равенства так, чтобы в итоге получить требуемый многочлен.
Первое решение. Так как многочлен
имеет старший коэффициент 
и корни 
то
Подставим 
в последнее равенство вместо 
получим
что равносильно
Из полученного равенства получаем, что тремя корнями уравнения 
являются числа 
______________________________________________________________________________________________________________________________________________________
Второе решение. По теореме Виета выполняются следующие соотношения:
Эти же равенства можно переписать следующим образом:
из чего следует, что числа 
и 
являются корнями уравнения 
и 
Ошибка.
Попробуйте повторить позже
На доску записывают пары чисел. Сначала на доску записали пару чисел 
Если на доске написана пара чисел 
то на доску
можно дописать пару 
а также пару 
Кроме того, если на доске написаны пары чисел 
и 
то на доску
можно дописать пару 
Могла ли через некоторое время на доске оказаться пара 
Порядок чисел в паре
существенен, например, пары чисел (1, 2) и (2, 1) считаются различными.
Источники:
Подсказка 1:
Попробуйте найти какой-нибудь инвариант при таких операциях.
Подсказка 2:
Рассмотрите выражение 2a – b. Как оно меняется при применении операций к паре (a, b)?
Подсказка 3:
Обратите внимание на остаток от деления 2a – b на 7. Как он меняется?
Первое решение. Докажем, что для любой пары 
записанной на доске, число 
делится на 
Действительно, для пары 
число 
делится на 7.
Пусть для пары 
число 
делится на 
Тогда для пары 
число
делится на 
и для пары 
число
делится на 
Пусть для пар 
числа 
делятся на 7. Тогда для пары 
число
делится на 
Так как для пары 
число
не делится на 
эта пара на доске появиться не может.
_________________________________________________________________________________________________________________________________________________________________________________
Второе решение. Будем к каждой паре 
на доске добавлять третье число 
Тогда сумма чисел в каждой тройке будет
равна нулю, а правила дописывания новых пар будут такими: если на доске записана тройка 
то можно дописать тройки
и 
а если записаны тройки 
и 
то можно дописать тройку 
— назовём эту
тройку суммой троек 
и 
Также для тройки 
и целого числа 
обозначим через 
тройку
______________________________________________________________________________________________________________________________________________________
Утверждение. Докажем, что все тройки, появляющиеся на доске, имеют вид
с целыми 
и 
В начальный момент времени это верно:
Теперь достаточно показать, что из троек, имеющих вид 
также получаются лишь такие тройки. Для операции
взятия суммы троек это очевидно. Для остальных операций это тоже несложно проверить: если 
имеет вид 
то
Утверждение доказано.
_________________________________________________________________________________________________________________________________________________________________________________
Предположим теперь, что на доске появилась тройка (2022, 2023, -4045), то есть она имеет вид 
Тогда имеем
Выражая из первого равенства 
и подставляя во второе, получаем
то есть
Однако это невозможно, поскольку 
не делится на 
не могла
Ошибка.
Попробуйте повторить позже
В остроугольном неравнобедренном треугольнике 
проведена высота 
медиана 
а также отмечен центр 
его описанной
окружности 
Отрезки 
и 
пересекаются в точке 
прямые 
и 
— в точке 
прямые 
и 
— в точке 
Лучи 
и 
пересекают окружность 
в точках 
и 
Докажите, что прямые 
и 
пересекаются в одной
точке.
Источники:
Пусть 
— такая точка на луче 
что 
Докажем, что точки 
и 
лежат на одной прямой.
В самом деле, по теореме Менелая для треугольника 
и прямой 
имеем
Поскольку прямые 
и 
параллельны между собой (так как они все перпендикулярны прямой 
),
имеем
Значит,
из чего следует, что точки 
и 
лежат на одной прямой по теореме Менелая для треугольника 
Значит, точка 
диаметрально противоположна точке 
в окружности 
.png)
Аналогично, если 
— точка пересечения перпендикуляра к прямой 
проходящего через точку 
и прямой
то точка 
диаметрально противоположна точке 
Из этого следует, что 
и, аналогично,
Обозначим через 
и 
точки пересечения прямой 
соответственно с прямыми 
и 
Заметим, что
треугольники 
и 
подобны как прямоугольные с вертикальными острыми углами. Значит, 
или
Аналогично, 
Значит, прямые 
и 
пересекают прямую 
в одной и той же точке, что и требовалось
доказать.
.png)
Ошибка.
Попробуйте повторить позже
Назовём два числа почти равными, если они равны или отличаются друг от друга не более, чем на единицу. Верно ли, что из любого прямоугольника с натуральными сторонами можно вырезать какой-нибудь прямоугольник с натуральными сторонами, площадь которого почти равна половине площади исходного прямоугольника? Стороны вырезаемого прямоугольника не обязательно параллельны сторонам исходного прямоугольника.
Источники:
Подсказка 1
У вырезанного прямоугольника стороны натуральной длины. При каких площадях у прямоугольника гарантированно будет длинная сторона?
Подсказка 2
Рассмотрите прямоугольник размера 5 × 15. Чему равна его площадь? Какое число будет "почти половиной" этой площади?
Подсказка 3
Какие прямоугольники с натуральными сторонами имеют площадь 37 или 38?
Подсказка 4
Проанализируйте размеры этих прямоугольников. Какая минимальная длина стороны у каждого из них?
Подсказка 5
Теперь подумайте о геометрических ограничениях. Что является наибольшим возможным расстоянием между двумя точками внутри прямоугольника 5 × 15?
Подсказка 6
Чему равна длина диагонали прямоугольника 5 × 15? Если все кандидаты требуют сторону, строго большую диагонали исходного прямоугольника, что это означает для возможности их вырезания?
Возьмём прямоугольник размера 
половина площади которого равна 
Для того, чтобы условие выполнилось, из данного
прямоугольника необходимо вырезать прямоугольники площади 
или 
Таких прямоугольников всего три: 
и 
Заметим, что длина стороны каждого из таких прямоугольников не меньше 
С другой стороны, диагональ исходного прямоугольника
равна 
но
поэтому ни один из таких прямоугольников вырезать из прямоугольника 
нельзя.
не всегда
Ошибка.
Попробуйте повторить позже
Точка 
— центр описанной окружности остроугольного неравнобедренного треугольника 
На биссектрисе угла 
внутри
треугольника 
отмечена точка 
а на отрезке 
— точка 
так, что 
и 
Точки 
и 
— центры
окружностей, описанных около треугольников 
и 
соответственно. Докажите, что точки 
и 
лежат на одной
прямой или на одной окружности.
Источники:
Обозначим вторую точку пересечения биссектрисы угла 
с окружностью, описанной около треугольника 
через 
Тогда точка
— середина дуги 
поэтому 
— серединный перпендикуляр к хорде 
Поскольку вписанный угол вдвое меньше
центрального, опирающегося на ту же дугу, то 
С другой стороны, так как 
то 
а
тогда
как внешний к треугольнику 
Таким образом, 
поэтому точка 
лежит на окружности, описанной около
треугольника 
Рассуждая аналогично, мы получаем, что
и точка 
лежит на окружности, описанной около треугольника 
Значит, точки 
и 
— центры описанных окружностей
треугольников 
и 
а эти треугольники симметричны относительно 
Получается, что точки 
и 
также симметричны
относительно 
Следовательно, либо точки 
и 
лежат на прямой 
либо 
— вершины равнобедренной трапеции,
а потому лежат на одной окружности.
Ошибка.
Попробуйте повторить позже
Даны ненулевые числа 
. Докажите, что выполняется неравенство
Источники:
Подсказка 1
В левой части есть три модуля |b/a − b/c|, |c/a − c/b|, |bc + 1|. C последним работать удобнее. Можно ли провести замену так, чтобы первые два выражения имели вид, аналогичный |bc + 1|.
Подсказка 2
Пусть мы хотим из b/a − b/c = b(1/a − 1/c) получить bd + 1. Чему тогда должно равняться d?
Подсказка 3
Проведём замену: вместо a введём d = 1/a − 1/b − 1/c. Какой вид тогда имеет левая часть?
Подсказка 4
|bd + 1| + |cd + 1| + |bc + 1|. Что можно сказать о величинах этих модулей?
Подсказка 5
Правда ли, что среди произведений bd, cd, bc, хотя бы одно неотрицательно? Что это говорит о величине левой части неравенства?
Положим 
Теперь заметим, что
Если 
то два из этих слагаемых равны 1, и тем самым сумма не меньше, чем 2. В противном случае числа 
отличны от нуля.
Значит, какие-то два из них одного знака, а тогда их произведение положительно, и соответствующее слагаемое больше 1. Поскольку два
других слагаемых неотрицательны, то общая сумма больше 1.
Ошибка.
Попробуйте повторить позже
В стране 
городов (
— натуральное), некоторые из них соединены двусторонними беспосадочными авиалиниями. Из любого города
можно попасть в любой другой, возможно, с пересадками. Президент хочет разделить страну на две области и включить каждый город в
одну из двух областей. При этом авиалинии разделятся на 
межобластных и 
внутриобластных. Докажите, что президент может
добиться того, чтобы выполнялось неравенство 
Источники:
Подсказка 1
Попробуйте подойти индукцией по числу вершин: при 2n = 2 утверждение очевидно.
Как бы вы перешли от 2(n−1) вершин к 2n?
Подсказка 2
Для шага индукции удобно удалить две вершины так, чтобы граф остался связным.
Какую пару вершин стоит искать?
Подсказка 3
Подумайте об остовном дереве графа. В дереве всегда есть висячие вершины.
Можете ли вы выбрать из дерева такую пару вершин, удаление которых не разрушает связность исходного графа?
Подсказка 4
Удалите найденные две вершины u и v и все инцидентные им рёбра.
По предположению индукции можно покрасить оставшиеся 2n−2 вершин так, что
разность Δ = «число разноцветных рёбер» минус «число одноцветных рёбер» не меньше n−1.
Как теперь вернуть u и v, чтобы Δ стало ≥ n?
Подсказка 5
Рассмотрите одну вершину, скажем u, и уже покрашенных её соседей.
Какой цвет выгоднее дать u: тот, что совпадает с большинством соседей, или наоборот?
При выборе цвета «против большинства» число разноцветных рёбер инцидентных u не меньше, чем одноцветных.
Подсказка 6
Сначала выберите цвет u, который максимизирует прирост Δ.
Затем, уже после этого, аналогично выберите цвет v.
Почему такой поочерёдный выбор не уменьшает Δ?
Подсказка 7
Если между u и v есть ребро, как гарантировать, что при необходимости можно ещё прибавить 1 к Δ?
Если итоговая разность получилась ровно n−1, попробуйте перекрасить одну из вершин u или v.
Подсказка 8
Соберите рассуждение воедино:
— нашли пару u,v, чьё удаление сохраняет связность;
— по индукции покрасили остальные вершины с разностью ≥ n−1;
— вернули u и v, выбирая их цвета так, чтобы прирост Δ был хотя бы +1.
Получится ли Δ ≥ n, как требуется?
Докажем индукцией по 
что в любом связном графе, содержащем 
вершин, их можно покрасить в красный и синий цвета таким
образом, что число рёбер с разноцветными концами (будем называть такие рёбра разноцветными) будет превосходить число рёбер с
одноцветными концами (будем называть такие рёбра одноцветными) хотя бы на 
— из этого числа будет следовать утверждение задачи.
База 
тривиальна, докажем переход.
Предположим, в графе с 
вершинами найдётся пара вершин, соединённых рёбером, при удалении которых граф не теряет связность;
обозначим эти вершины через 
и 
Покрасим оставшиеся вершины таким образом, чтобы число разноцветных рёбер было
хотя бы на 
больше числа одноцветных рёбер — так можно сделать по предположению индукции. Заметим, что
вершины 
и 
теперь можно покрасить таким образом, что разность между количествами разноцветных и одноцветных
рёбер увеличится. В самом деле, без ограничения общности будем считать, что если вершины 
и 
не имеют обе чётные
степени, то вершина 
имеет нечётную степень. Тогда покрасим вершину 
в цвет, который имеет меньшее число её
соседей (в случае равенства покрасим в любой цвет), а затем покрасим таким же образом вершину 
Очевидно, при
каждой покраске требуемая разность не уменьшилась, и хотя бы при одной покраске у соответствующей вершины было
нечётное число покрашенных соседей, то есть разность при этой покраске увеличилась. Поскольку до покраски вершин
и 
разность рёбер и числом одноцветных рёбер была не меньше 
после этой покраски она стала не меньше
С другой стороны, если в графе найдётся пара висячих вершин, то, очевидно, при их удалении граф по-прежнему не теряет связность, и
тем же самым алгоритмом можно покрасить весь оставшийся граф, а затем и эти висячие вершины, таким образом, что разность между
количествами разноцветных и одноцветных рёбер будет меньше 
Докажем, что в любом связном графе хотя бы с тремя
вершинами или найдутся две смежные вершины, при удалении которых граф останется связным, или найдутся две висячие
вершины.
В самом деле, рассмотрим произвольное остовное дерево этого графа и подвесим его за любую не висячую вершину. Пусть 
— наиболее
удалённая от корня висячая вершина этого дерева, а 
— предок этой вершины. Обозначим потомков этого предка через
Заметим, что вершины 
являются висячими в рассматриваемом остовном дереве. Рассмотрим несколько
случаев.
Случай 1. Среди вершин 
есть пара вершин, соединённых ребром в исходном графе. Тогда при удалении этих двух вершин
остовное дерево(а значит, и сам исходный граф) сохраняет связность.
Случай 2. Среди вершин 
есть пара вершин, являющихся висячими в исходном графе. Значит, в исходном графе есть хотя бы
две висячие вершины.
Случай 3. Среди вершин 
есть не больше одной вершины, являющейся висячей в исходном графе. Без ограничения общности,
будем считать, что если такая вершина есть, то это вершина 
Тогда переподвесим каждую из вершин 
к любому из её соседей,
отличных от 
поскольку эти вершины не являются висячими в исходном графе, такой сосед всегда найдётся. После всех
переподвешиваний вершины 
и 
можно удалить из графа, и остовное дерево останется связанным — а значит, и сам
граф.
Поскольку хотя бы один из случаев имеет место, и в каждом из них в графе есть или пара смежных вершин, при удалении которых граф остаётся связным, или пара висячих вершин, переход индукции доказан.
