Тема ОММО - задания по годам

ОММО 2023

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела оммо - задания по годам
Решаем задачи

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

Задача 1#63737

Точка R
  1  — середина отрезка ST  ; точка R
 2  — середина отрезка SR
  1  ; для каждого n ≥3  точка R
  n  — середина отрезка R   R
 n−2 n−1  . Пусть R  — предельное положение точки Rn  при n→ ∞ . Найдите длину отрезка RT  , если длина отрезка ST  равна 15.

Источники: ОММО-2023, номер 1 (см. olympiads.mccme.ru)

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

Подсказка 1

Порисуйте эти точки на отрезке. В каком порядке они будут располагаться?

Подсказка 2

Они будут идти как-то так: S, R_2, R_4..., R,...R_3, R_1, T. Еще осталось понять, чему равна длина отрезка вида R_{n+2}R_n и дело в шляпе!

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

Обозначим T =R  ,S =R
    − 1     0  , тогда R
 n  - середина отрезка R   R
 n−2 n−1  для каждого n≥ 1  . Легко видеть, что на отрезке точки будут расположены в следующем порядке:

S = R0,R2,R4,...,R,...,R3,R1,R−1 = T

Поэтому

RT =R− 1R1 +R1R3 +R3R5 +...

Далее, длина отрезка Rn+1Rn  в два раза меньше длины отрезка RnRn −1  , откуда длина отрезка Rn+2Rn+1  в четыре раза меньше длины отрезка RnRn−1  . Значит,

          (   1  -1    )   ST---1-   15 4
RT =R −1R1 1+ 4 + 42 + ... = 2 ⋅1 − 14 = 2 ⋅3 =10
Ответ:

 10

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

Задача 2#63738

При каком наименьшем n  можно покрасить каждое натуральное число в один из n  цветов так, чтобы любые два числа, отличающиеся на 5 , на 8 , на 10 , на 13 и на 18, были покрашены в разные цвета?

Источники: ОММО-2023, номер 2 (см. olympiads.mccme.ru)

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

Подсказка 1

Давайте попробуем как-то снизу оценить кол-во цветов. Вот что можно заметить в этих разностях: 18-13 = 5, 18-10 = 8, 13-5 = 8, 13-5 = 8....может быть можно найти какую-то группу чисел, в которой все числа должны быть разного цвета?

Подсказка 2

Например, подойдет четверка чисел вида n, n+5, n+10, n+18! А еще подойдет четверка n, n+5, n+13, n+18...теперь проверьте, может ли быть ровно 4 цвета?

Подсказка 3

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

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

Докажем для начала, что четырьмя и меньше цветами обойтись не удастся. Посмотрим на числа n,n +5,n+ 10,n+ 18  . Разности между ними равны

      (n+ 5)− n =5, (n+ 10)− n =10, (n+ 18)− n =18

(n +10)− (n+ 5)= 5, (n +18)− (n +5)= 13,  (n +18)− (n +10)= 8

т.е. любые два из этих чисел покрашены в различные цвета. Значит, цветов хотя бы четыре. Предположим, что цветов ровно четыре. Тогда числа n,n+ 5,n+ 10,n +18  покрашены во все возможные цвета. Аналогично можно получить, что во все возможные цвета покрашены числа n,n+ 5,n+ 13  , n+ 18  . Значит, для каждого натурального n  числа n +10  и n+ 13  должны быть покрашены в один и тот же цвет.

Применим полученное утверждение для n= 1,4,7,...,16  . Тогда числа 11,14,17,...,29  покрашены в один и тот же цвет. Противоречие, ведь 29− 11 =18  и числа 11 и 29 должны быть покрашены в разные цвета.

Докажем теперь, что пять цветов достаточно. Для этого разобьём все натуральные числа на группы по 5 подряд идущих чисел, а группы покрасим так: первую - в первый, вторую - во второй, ..., пятую - в пятый, шестую - в первый, седьмую - во второй, .... При такой раскраске числа одного цвета будут или отличаться не более чем на 4, если лежат в одной пятёрке, или хотя бы на 21 - если в разных. Значит, числа, отличающиеся на 5,8,10,13  и 18, будут покрашены в разные цвета.

Ответ: 5

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

Задача 3#63739

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

1 2 3
Молибден 8%  3%  8%
Титан 36%  21%  6%
Алюминий 55%  76%  15%

Из этих сплавов необходимо приготовить новый сплав, в котором алюминия должно быть не больше 38%  , а молибдена - не меньше   5%  . Какое наибольшее и какое наименьшее содержание титана (в процентах) может быть в этом сплаве?

Источники: ОММО-2023, номер 3 (см. olympiads.mccme.ru)

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

Подсказка 1

Давайте сначала просто посчитаем. Пусть мы взяли x,y и 1-x-y первого, второго и третьего сплавов соответственно. Тогда как выглядят наши условия на нужный сплав и что мы хотим максимизировать/минимизировать?

Подсказка 2

Вы получили условия в виде неравенства для x и y, и выражение, которое надо максимизировать/минимизировать. Может быть, на плоскости эти неравенства будут нагляднее?)

Подсказка 3

Нам по факту надо найти макс/мин выражения 6+30x+15y. Понятно, что минимум будет в точке (0, 0). А чтобы найти максимум, можно заметить, что коэф при x больше, чем коэф при y....)

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

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

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

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

Сразу отметим, что тогда в таком сплаве будет 8%  молибдена, т.е. он подходит под условие на молибден. В сплаве 1 титана больше, чем в сплаве 3 , но сплав 1 не подходит под условие на алюминий. Понятно, что чем меньше мы возьмём сплава 3, тем больше будет титана в изготовленном сплаве. Возьмём ровно столько, чтобы выполнилось условие на алюминий: 55x+15y = 38(x +y)(x  и y− масса сплава 1 и 3 соответственно), откуда 17x =23y  , т.е. можно взять 23 части сплава 1 и 17 частей сплава 3. Тогда содержание титана в процентах будет

36⋅23+-6⋅17= 23,25
   23+17

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

Пусть взято x,y  и 1− x − y  первого, второго и третьего сплава соответственно, причём x ≥0,y ≥ 0,1− x− y ≥ 0  . Тогда условия задачи можно записать так:

55x+ 76y+ 15(1− x− y)= 40x+ 61y+ 15 ≤38
    8x+ 3y+8(1− x− y) =−5y +8≥ 5

Изобразим на координатной плоскости область (см. рисунок), удовлетворяющую системе неравенств

(|{ 40x+ 61y− 23≤ 0
  −5y+ 3≥ 0
|( x≥ 0, y ≥ 0, x +y− 1≤ 0.

PIC

Процентное содержание титана 36x+ 21y+ 6(1− x− y) =6+ 30x+ 15y(∗)  . Легко видеть, что минимум этого числа достигается в точке A  и равен 6 . Чтобы найти максимум, заметим, что абсцисса точки B  равна 23  1
40 > 2  , а ордината точки    23  1
C− 61 < 2  . При этом коэффициент при x  в (∗)  больше. Значит, значение в точке B  точно больше (мы большее число умножаем на большее число), и равно       23
6+ 30⋅40 = 23,25.

Ответ:

наименьшее 6%

наибольшее 23,25%

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

Задача 4#63740

Дана трапеция ABCD  с основаниями AD = 9,BC = 2  и боковыми сторонами AB =5,CD = 3√2-  . Точка P  на прямой BC  такова, что периметр треугольника AP D  наименьший из возможных. Найдите этот периметр.

Источники: ОММО-2023, номер 4 (см. olympiads.mccme.ru)

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

Подсказка 1

Заметим, что основание у нашего треугольника зафиксировано. То есть на самом деле нам нужно найти минимальную сумму расстояний до точки P от A и B. Давайте попробуем понять, почему расстояние будет минимальным, когда лучи PA и PB будут падать под одним углом на BC. Обычно когда речь идёт о минимуме или максимуме, то нужно неравенство, а в геометрии чаще всего — это неравенство треугольника. Как можно попробовать сделать из отрезков PA и PB треугольник, в котором мы явно будем видеть их сумму?

Подсказка 2

Верно, хоть до этого и не просто догадаться, давайте попробуем отразить точку D симметрично относительно BC. Что тогда у нас получается? Пусть симметричная точка X. Получается треугольник APX, где сумма наших расстояний это AP+PX. Но тогда записав неравенство треугольника, когда достигается минимум?

Подсказка 3

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

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

PIC

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

Воспользуемся следующим утверждением, которое наиболее известно как «принцип наименьшего времени Ферма» в физике:

Для данных точек A,B  и данной прямой ℓ  из всех точек L ∈ ℓ  сумма AL +BL  будет минимальной, когда углы между прямыми AL  и ℓ  и BL  и ℓ  будут равны.

Тогда для искомой точки P  на прямой BC  должно выполняться равенство ∠XP A = ∠YPD  (точки X  и Y  - где-то «далеко» на прямой BC )  . Поскольку BC ∥AD  , то

∠P AD =∠XP A = ∠YPD = ∠PDA

т.е. треугольник PAD  - равнобедренный. Значит, нам достаточно найти периметр равнобедренного треугольника PAD  , где P  - точка на прямой BC  .

По теореме Пифагора этот периметр равен

     ∘---------
9+ 2⋅ ( 9)2+ h2 = 9+∘81-+-4h2
        2

где h  - расстояние между прямыми AD  и BC  , т.е. высота трапеции.

Найти высоту трапеции можно разными способами. Например, проведём через точку B  , прямую, параллельную CD  , до пересечения с основанием AD  в точке K  . Тогда искомая высота - это высота из вершины B  в треугольнике ABK  . Поскольку BCDK − параллелограмм, то           √ -
BK = CD =3  2  , AK  =AD − DK = AD − BC = 9− 2= 7  .

Итого, нам достаточно найти длину высоты на сторону длины 7 в треугольнике со сторонами 5 ,   √-
7,3 2  . По формуле площади и формуле Герона имеем

 2  2     2         √-        √-       √ -        √ -
4h  ⋅7 = 16S = (5 +7+ 3 2)(5+ 7− 3 2)(5− 7+ 3 2)(−5+ 7+ 3 2)

откуда

          √-      √-      √ -    √ -   (122− (3√2-)2)((3√2)2 − 22)
4h2 = (12+3-2)(12-− 3-2)7(−2-2+3-2)(2+3-2) = ----------72----------= 36

и окончательный ответ    √-------     √---
9 + 81+ 4h2 = 9+ 117  .

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

Также, как и в первом решении, найдём высоту трапеции. Покажем здесь, как можно это было сделать по-другому. Опустим высоты BE  и CF  трапеции. Обозначим их длины через h  , длину отрезка AE  обозначим через ℓ  . Поскольку EF =BC  =2  , для F D  получим FD = 7− ℓ  . Из прямоугольных треугольников ABE  и CDF  по теореме Пифагора получим AB2 = BE2 +AE2  и CD2 = CF2 +DF 2

Подставив в эти равенства известные длины, получим систему уравнений

{  52 =h2+ ℓ2
   18 =h2+ (7− ℓ)2

Вычитая из первого равенства второе, получим (ℓ+ (7 − ℓ))(ℓ− (7− ℓ))= 7  , откуда ℓ =4  . Тогда h= 3,FD = 3  .

Рассмотрим треугольник APD  . Обозначим BP = x  , тогда PC =2− x  (здесь и далее все расстояния со знаком, т.е. могут быть отрицательные). Опустим высоту PQ  . Тогда треугольник AP Q  прямоугольный и по теореме Пифагора

                 ∘ ----------
AP = ∘AQ2-+-QP2-=  (4+x)2+ 32.

Аналогично, из прямоугольного треугольника DPQ

    ∘ ----------
DP =  (5− x)2+ 32

Тогда периметр треугольника APD  равен

         ∘----------  ∘----------
P (x)= 9+  (4+ x)2+ 32+  (5− x)2+ 32

Найдём производную этой функции:

P′(x)= ∘---4+-x----− ∘--5−-x----.
        (4 +x)2+32    (5− x)2+ 32

Из уравнения   ′
P (x)=0  получаем

      (         )        (         )
(4+ x)2(5− x)2+ 32 = (5− x)2(4+ x)2+ 32

откуда      2       2    1
(5− x) = (4+x) ,x= 2  . Несложно видеть, что    1
x= 2  именно точка минимума, откуда минимальный периметр равен   (1)    √ ---
P  2 = 9+  117  .

Ответ:

 9+ √117

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

Задача 5#63741

Решите систему уравнений

{ x10+ x10+ ...+ x10=310
  x133+ x233+ ...+ x9323=333
   1    2       92

Источники: ОММО-2023, номер 5 (см. olympiads.mccme.ru)

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

Подсказка 1

Сразу понимаем, что, скорее всего, эта система "нормально" не решается. У нас два уравнения с кучей неизвестных. Но одно из решений мы сразу угадываем — это один из x равен 3, а остальные 0. Давайте поделим обе части первого уравнения на 3¹⁰. Как тогда можно оценить каждое из слагаемых?

Подсказка 2

Ага, тогда понятно, что каждое из слагаемых не превосходит единицы, так как степень у них чётная. Значит, для любого 1≤k≤92 получаем, что |x_k/3|≤1. Не забываем про модуль, так как извлекаем корень из чётной степени. Но раз у нас число меньше 1 то, что можно сказать о нём при возведении в степень?

Подсказка 3

Верно, тогда это число в 33 степени меньше, чем в 10. Теперь, учитывая это, попробуйте записать неравенство для второго и первого уравнения, используя неравенство с модулем. Выходит, что возможен только случай равенства |x_k/3|³³ = |x_k/3|¹⁰ для данных k.

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

Заметим, что

( x1)10  (x2)10     ( x92)10
  3   +   3   +...+  3    = 1

Тогда для каждого 1≤k ≤92  имеем |xk|
|3-|≤1,  откуда

|x |33  |x |10
||k3||  ≤ ||k3||

Окончательно получим

   |(   )   (  )        (  )  |
1= ||| x1 33+  x2 33+ ...+  x92-33|||≤
     3       3          3

≤ |||x1|||33+ |||x2|||33+ ...+|||x92|||33 ≤
   3      3          3

  |  |   | |       |   |
≤ ||x1||10+ ||x2||10+ ...+||x92||10 =
   3      3          3

= (x1)10+ (x2)10+ ...+ (x92)10 =1.
    3      3           3

Значит, для каждого k  выполнено

||xk||33  ||xk||10
|3|  = |3|

откуда

xk ∈ {−3,0,3}

Отсюда несложно получаем, что тогда один из x
 k  равен 3,  а все остальные равны 0.

Ответ: одна из переменных равна 3, все остальные равны 0

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

Задача 6#63742

Укажите все значения параметра a,|a|<1  , при которых множество решений неравенства

|cost−-a|−-sint
  ||cost− 34||   >0

для t∈(0;π)  представимо в виде двух непересекающихся интервалов.

Источники: ОММО-2023, номер 6 (см. olympiads.mccme.ru)

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

Подсказка 1

Давайте сделаем естественную вещь в таком не очень хорошем параметре. У нас есть синус и косинус с одинаковым аргументом. Тогда попробуем сделать замену sin(t)=y и cos(t)=x. Какие условия тогда у нас будут?

Подсказка 2

Верно, тогда у нас получается система из 4 условий: основное тригонометрическое тождество, ограничение на t, ОДЗ знаменателя и само исходное неравенство. Тогда как теперь можно сформулировать вопрос задачи и найти а?

Подсказка 3

Ага, получается, что нам удовлетворяют все решения системы, где точки лежат на полуокружности и ниже, чем график y = |x− a|, который двигается вдоль оси х в зависимости от а. Осталось только определить, когда получается два непересекающихся отрезка в решении и найти из графика граничные точки для а.

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

Пусть x =cost,y = sint  . Тогда, с учётом допустимых значений t  , неравенство равносильно системе

(| x2+ y2 =1
|||{ y > 0
|    3
|||( x⁄= 4
  y < |x − a|

Решения этой системы - точки на полуокружности x2+ y2 = 1,y > 0  , лежащие ниже графика функции y = |x− a| .

PIC

При изменении параметра a  график функции y =|x− a| перемещается вдоль оси x  . При значениях a  , близких к − 1,  в качестве множества решений имеем 3  непересекающихся интервала. При значениях a  , близких к 1,  получается 2  интервала.

Крайнее положение графика, при котором получается два интервала, изображено на рисунке:

PIC

Координаты точки M  пересечения окружности и прямой y = x− a  равны

     3     ∘ -------- √7-
xM = 4,yM =   1− (3∕4)2 =-4-

Так как 34 − a =yM  , то      √-
a= 3−47  .

Таким образом, ответом является множество [  √-  )
 3−47,1 .

Ответ:

[3−√7,1)
  4

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

Задача 7#63743

Дано действительное число t  , отличное от 0,1,− 1,1
      2  и 2.

Решите уравнение

(x2 − x +1)3 (t2 − t+ 1)3
-x2(x-− 1)2-=-t2(t−-1)2--

Ответ может зависеть от t.

Источники: ОММО-2023, номер 7 (см. olympiads.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Мы получим уравнение 6-й степени! А значит, у него точно не больше 6 корней. Тогда есть соблазн попробовать угадать эти 6 корней...

Подсказка 3

Легко видеть, что t - корень. Какие замены можно попробовать сделать, чтобы найти ещё немного корней?

Подсказка 4

Левая дробь не меняется при замене x на 1-x и на 1/x, поэтому получаем новые корни, какие? Попробуйте набрать как можно больше.

Подсказка 5

Теперь лишь остаётся доказать, что при данных ограничениях на t шесть корней, которые вы нашли, всегда различные.

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

Докажем два утверждения:

  • если x
 0  - решение уравнения, то и 1 − x
    0  также решение; действительно,

(                 )
 (1− x0)2− (1− x0)+1 3 (x20− x0+ 1)3
-(1−-x0)2((1−-x0)− 1)2 =-x2(x0−-1)2-
                        0

поэтому если второе равняется   2   3
(tt−2(tt−+11))2  , то и первое - тоже.

  • если x0  - решение уравнения, то и 1x-
0  также решение; действительно,

(               )3
 (1∕x0)2− (1∕x0)+ 1    (x20− x0+1)3
-(1∕x0)2((1∕x0)− 1)2-=-x20(x0−-1)2-

поэтому если второе равняется   2   3
(tt−2(tt−+11))2  , то и первое - тоже.

Заметим теперь, что t  - точно корень исходного уравнения. Тогда, корнями являются также числа 1∕t,1− t  , а тогда и 11−t,1− 1−1t = t−t1,1− 1t = t−t1  .

Можно показать, что при данных ограничениях на t  получившиеся 6 чисел - различны. Кроме того, исходное уравнение при x ⁄=0,x⁄= 1  равносильно уравнению 6 -й степени, которое не может иметь больше 6 корней. Значит, найденные числа и есть все корни.

Ответ:

 t,1,1 − t,-1,-t-,t−1
  t     1− tt−1  t

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

Задача 8#63744

В треугольнике ABC  точки A ,B ,C
 0  0 0  — середины сторон BC,CA,AB,  а A
 1  , B ,C
  1 1  — точки касания этих сторон со вписанной окружностью соответственно. Прямые A1C1,B1C1  пересекают A0B0  в точках X  и Y.  Докажите, что прямая CC1  делит отрезок   XY  пополам.

Источники: ОММО - 2023, задача 8 (см. olympiads.mccme.ru)

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

Подсказка 1

Один отрезок делит другой пополам, часто это происходит потому что они являются диагоналями некоторого параллелограмма.

Подсказка 2

В данном случае окажется, CXC1Y - параллелограмм, но нужно как-то подобраться к точкам X и Y...

Подсказка 3

В этом нам поможет лемма 255, согласно ней точки X и Y лежат на биссектрисах углов A и B соответственно.

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

Докажем, что точки X,Y  лежат на биссектрисах углов A,B  соответственно (это утверждение известно как задача 255  и может быть использовано на олимпиаде без доказательства). Так как AB1 = AC1  и B0Y ∥AC1,  то             |AB−BC-|
B0Y =B0B1 =   2   ,  следовательно, A0Y = A0B  и ∠YBA0 = ∠BY A0 = ∠YBA.  Аналогично ∠XAC  =∠XAB.

PIC

Итак, AX ⊥ XC  по лемме 255  и AX ⊥ B1C1,  потому что треугольник AB1C1  равнобедренный и AX  в нём биссектриса, проведённая к основанию. Следовательно, XC  ∥C1Y.  Аналогично CY ∥ C1X.  Таким образом, четырёхугольник XCY C1  — параллелограмм. В таком случае его диагонали точкой пересечения делятся пополам, это даёт нам требуемое.

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

Задача 9#63745

Найдите все функции f :ℝ → ℝ  , для которых существует такое вещественное число a  , что при всех вещественных x,y  выполнено равенство

2f(xy+ 3)=f(x)f(y)− f(x)− 2y+a

Источники: ОММО-2023, номер 9 (см. olympiads.mccme.ru)

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

Подсказка 1

Заметим, что правая часть несимметрична относительно x и y, а левая - симметрична) Как тогда можно связать x и y?

Подсказка 2

f(x)f(y) - f(x) - 2y + a = 2f(xy+3)=f(y)f(x) - f(y) - 2x + a ⇒ f(x) - 2x = f(y) - 2y. Значит, разность f(x) - 2x постоянна! Как тогда записать f(x) и что с этим можно сделать?

Подсказка 3

f(x) = 2x + C, для некоторого действительного C и любого x) Остается лишь подставить это в равенство из условия, найти C и a)

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

Заметим, что

f(x)f(y)− f(x)− 2y+ a= 2f(xy+ 3)=2f(yx+3)= f(y)f(x)− f(y)− 2x+ a.

Значит, при всех x,y ∈ ℝ  выполнено f(x)− 2x= f(y)− 2y  . Значит, разность f(x)− 2x  постоянна и f(x)= 2x+ C  , для некоторого C ∈ℝ  . Подставляя в исходное равенство, получаем, что при всех x,y ∈ℝ  выполнено равенство:

                            2
2(2xy+ 6+ C)= 4xy +2Cx +2Cy +C  − 2x− C− 2y+ a.

Оно тождественно выполнено только при C = 1  ; при этом a= 14.

Ответ:

 f(x)= 2x +1

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

Задача 10#63746

В группе из 80 человек некоторые знакомы друг с другом (знакомства взаимны). Известно, что в группе есть человек, который знает ровно 1 из оставшихся, человек, который знает ровно 2 из оставшихся, ..., человек, который знает ровно 54 из оставшихся. Докажите, что в группе есть три человека, каждые два из которых знакомы.

Источники: ОММО-2023, номер 10 (см. olympiads.mccme.ru)

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

Подсказка 1

Зачастую в задачах на знакомства, на какие-то дороги, где нам даны количества "соединений", удобнее всего начинать с объекта, у которого их больше всех) Попробуем рассмотреть всех знакомых человека А, у которого их 54, что можно о них сказать?

Подсказка 2

Чего же мы хотим добиться от такого множества? Найти человека B в нём, у которого с A точно есть общий знакомый. Но чтобы найти такого B, нужно хотя бы понимать, сколько у него знакомых. Но далеко не обо всех людях мы знаем количество их друзей :( Значит, попробуем сократить множество, в котором будем искать такого B. О скольких людях в множестве друзей A мы точно знаем количество знакомых?

Подсказка 3

В множестве знакомых A максимум 26 человек, у которых мы не знаем количество друзей, значит, есть как минимум 28 человек, про которых мы можем что-то сказать. Какого тогда человека мы можем "выцепить" оттуда, чтобы, наконец, найти B из подсказки 2?

Подсказка 4

Среди них есть человек B, у которого хотя бы 28 знакомых! Осталось лишь доказать, почему же у B и A обязательно есть общий знакомый из всех, при условии, что они знакомы между собой?)

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

Посмотрим на человека A  , который знает ровно 54  из оставшихся. Из них максимум 26  людей, про количество знакомых у которых в условии ничего не сказано. Осталось как минимум 28 человек, про количество знакомых которых сказано в условии. Среди них тогда найдётся человек B  , количество знакомых которого хотя бы 28.

У A,  кроме B,  есть ещё 53  знакомых, а у B  , кроме A− ещё 27.  Поскольку 53+ 27= 80> 78,  то у A  и B  есть хотя бы один общий знакомый C.  Тройка A,B,C  и есть искомая тройка человек.

Рулетка
Вы можете получить скидку в рулетке!