Тема Региональный этап ВсОШ и олимпиада им. Эйлера

Регион 9 класс → .05 Регион 2018

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела региональный этап всош и олимпиада им. эйлера

Разделы подтемы Регион 9 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#75858Максимум баллов за задание: 7

Числа $x$ , $y$ и $z$ удовлетворяют условию $x2+ y2+ z2 =1.$ Докажите, что

1-- (x− y)(y− z)(x− z)≤ √2.

Источники: Всеросс., 2018, РЭ, 9.5(см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Показать доказательство

Поскольку при любой перестановке переменных левая часть неравенства либо не меняется, либо меняет знак, достаточно проверить неравенство для любой перестановки чисел $x,y$ и $z,$ для которой левая часть неотрицательна. Поэтому можно считать, что $x ≥y ≥z.$ Обозначим $a= x− y ≥ 0,b= y− z ≥ 0;$ тогда $y =x − a,z = y− b.$ Равенство из условия задачи преобразуется к виду

2 2 2 2 ( 2 2 ) 0= x + (x− a) + (x − a− b) − 1= =3x − 2(2a+ b)x+ 2a +2ab+ b− 1 (1)

а требуемое неравенство — к виду

1 ab(a+ b)≤ √2- (2)

Рассмотрим правую часть равенства $(1)$ как квадратный трёхчлен от $x.$ Поскольку он имеет корень, его дискриминант неотрицателен, то есть

0≤ (2a +b)2 − 3(2a2+2ab+ b2− 1)= 3− 2(a2 +ab+ b2)

откуда

a2 +ab+ b2 ≤ 3 (3) 2

Осталось показать, как из $(3)$ следует $(2)$ (при $a,b≥ 0$ ).

По неравенству о средних для двух чисел имеем $a2+ b2+ab≥ 2ab+ab= 3ab,$ откуда $ab≤ 12.$ Значит,

(a+b)2 = (a2+ ab+ b2)+ ab≤ 3+ 1= 2 2 2

то есть $a +b≤ √2.$ Итак,

ab(a+ b)≤ 1 ⋅√2 = √1- 2 2

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

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#79735Максимум баллов за задание: 7

Изначально по кругу расставлены $40$ синих, $30$ красных и $20$ зелёных фишек, причём фишки каждого цвета идут подряд. За ход можно поменять местами стоящие рядом синюю и красную фишки, или стоящие рядом синюю и зелёную фишки. Можно ли за несколько таких операций добиться того, чтобы любые две стоящие рядом фишки были разных цветов?

Источники: Всеросс., 2018, РЭ, 9.7(см. olympiads.mccme.ru)

Показать ответ и решение

Поскольку красные фишки не могут меняться местами с зелёными, их взаимный порядок всегда будет оставаться таким же, как исходный. Иначе говоря, если в любой момент убрать синие фишки, то останутся $30$ красных фишек, стоящих подряд, и $20$ зелёных, также стоящих подряд. Если требуемого удалось добиться, это означает, что мы удалили хотя бы по одной синей фишке с каждого из $29$ интервалов между соседним красными фишками и с каждого из $19$ интервалов между соседними зелёными фишками; но тогда синих фишек было бы не меньше, чем $29+ 19= 48> 40,$ что не так. Значит, требуемое невозможно.

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 3#88266Максимум баллов за задание: 7

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

Источники: Всеросс., 2018, РЭ, 9.10(см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Постройте пример на 198 вершин. Рассмотрите 2 случая: 1)если из каждой вершины выходит хотя бы по 4 ребра, 2)если есть вершина степени не больше трех.

Подсказка 3

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

Показать ответ и решение

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

Пример с $198$ рёбрами: Разобьём $99$ вершин, кроме вершины $A,$ на $33$ группы по $3$ вершины. Соединим попарно вершины в каждой тройке и соединим $A$ со всеми другими вершинами. Тогда условия задачи выполнены: при удалении $A$ разбиение на тройки уже приведено, а при удалении любой другой вершины $B$ в этом же разбиении достаточно заменить $B$ на $A.$ При этом в описанном графе всего $33 ⋅3 +99= 198$ рёбер.

Оценка: назовём граф на $3k+1$ вершинах хорошим, если при удалении любой вершины остальные $3k$ вершин разбиваются на $k$ треугольников. Докажем индукцией по $k,$ что в хорошем графе на $3k +1$ вершинах хотя бы $6k$ рёбер; при $k =33$ получим требуемую оценку. База при $k =1$ несложна: так как при удалении любой вершины три остальных попарно соединены, любые две вершины должны быть соединены, то есть число рёбер равно $C24 = 6.$

Переход: если из каждой вершины выходит хотя бы по $4$ ребра, общее количество рёбер не меньше, чем $(3k+1)⋅4 --2---= 2(3k+ 1),$ что даже больше, чем $6k.$

В противном случае найдётся вершина $A,$ соединённая не более, чем с тремя другими. Если удалить любую вершину, кроме $A,$ то $A$ попадёт в какую-то тройку, а значит, она соединена хотя бы с двумя вершинами. Если удалить одну из этих вершин, у $A$ останется не менее двух смежных, то есть было их не меньше трёх. Итак, $A$ соединена ровно с тремя вершинами $B,C$ и $D.$ Тогда при удалении, скажем, $B$ вершины $A,C$ и $D$ образуют тройку, то есть $C$ и $D$ соединены; аналогично получаем, что $B,C$ и $D$ попарно соединены.

Выбросим теперь из графа вершины $A,B,C$ и $D,$ взамен добавив одну вершину $X,$ соединённую со всеми, с кем была соединена хотя бы одна из вершин $B,C$ и $D.$ Заметим, что при этом количество рёбер уменьшилось хотя бы на $6$ (т. е. на количество рёбер между $A,B,C$ и $D ).$ Покажем, что полученный новый граф хороший; отсюда будет следовать переход индукции, ибо тогда в новом графе будет не менее $6(k − 1)$ рёбер, а значит, в исходном — не менее $6(k− 1)+ 6= 6k$ рёбер. Пусть из нового графа удалена некоторая вершина $Y ⁄= X.$ Если её удалить из исходного графа, остальные вершины разобьются на тройки; пусть при этом вершина $A$ окажется, для определённости, в тройке с $B$ и $C,$ а вершина $D$ — в другой тройке. Тогда можно разбить новый граф так же, поместив вершину $X$ в ту тройку, где была вершина $D.$ Наконец, если удалить из нового графа вершину $X,$ можно проделать ту же операцию, считая, что из исходного графа удалена вершина $D$ (тогда $A,B$ и $C$ автоматически окажутся в одной тройке). Таким образом, переход индукции доказан.

Ответ:

$198$

Предыдущая подтема

Следующая подтема