Международная математическая олимпиада 2020 (решаем в комментах)

    image

    На этой неделе (16-26 сентября) в Санкт-Петербурге (виртуально) стартовала 61-я международная математическая олимпиада, в ней принимают участие 622 школьника из 114 стран.

    Первая такая олимпиада прошла в 1959 году в Румынии, и тогда в ней принимали участие представители всего семи стран.

    Россию представляет команда из шести старшеклассников.

    На решение 6 задач школьникам отводится 2 дня по 4,5 часа. Пока идет оценка результатов, предлагаю вам попробовать решить задачи и обсудить в комментах.

    image

    Результаты прошлых лет.





    Задача 1


    Внутри выпуклого четырёхугольника ABCD нашлась точка P, такая что выполняются равенства

    ∠PAD: ∠PBA: ∠DPA = 1: 2: 3 = ∠CBP: ∠BAP: ∠BPC.

    Докажите, что следующие три прямые пересекаются в одной точке: внутренние биссектрисы углов ∠ADP и ∠PCB и серединный перпендикуляр к отрезку AB.

    Задача 2


    Даны вещественные числа a, b, c, d, такие что a > b > c > d > 0 и a + b + c + d = 1.

    Докажите, что

    (a + 2b + 3c + 4d) aabbccdd < 1.

    Задача 3


    Имеется 4n камушков массами 1, 2, 3,..., 4n. Каждый из камушков покрашен в один из n цветов, причём имеется по 4 камушка каждого цвета.

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

    Задача 4


    Дано целое число n > 1. На горном склоне расположено n2 фуникулёрных станций на разных высотах. Каждая из двух фуникулёрных компаний A и B владеет k подъёмниками. Каждый подъёмник осуществляет регулярный беспересадочный трансфер с одной из станций на другую, более высоко расположенную станцию. k трансферов компании A начинаются на k различных станциях; также они заканчиваются на k различных станциях; при этом трансфер, который начинается выше, и заканчивается выше. Те же условия выполнены для компании B. Будем говорить, что две станции связаны фуникулёрной компанией, если можно добраться из нижней станции в верхнюю, используя один или несколько трансферов данной компании (другие перемещения между станциями запрещены). Найдите наименьшее k, при котором заведомо найдутся две станции, связанные обеими компаниями.

    Задача 5


    Имеется n > 1 карточек, на каждой из которых написано целое положительное число.
    Оказалось, что для любых двух карточек среднее арифметическое написанных на них чисел равно среднему геометрическому чисел, написанных на карточках некоторого набора, состоящего из одной или более карточек. При каких n из этого следует, что все числа, написанные на карточках, равны?

    Задача 6


    Докажите, что существует положительная константа c, для которой выполняется следующее утверждение:
    Пусть S — множество из n > 1 точек плоскости, в котором расстояние между любыми двумя точками не меньше 1. Тогда существует прямая ℓ, разделяющая множество S, такая что расстояние от любой точки S до ℓ не меньше чем cn−1/3.
    (Прямая ℓ разделяет множество точек S, если она пересекает некоторый отрезок, концы которого принадлежат S.)

    Замечание. Более слабые результаты с заменой cn−1/3 на cn−α могут оцениваться в зависимости от значения константы α > 1/3.



    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 18

      –1
      Задача 2.
      Значение целевой функции достигает 1 при a=1 и b=c=d=0. Зафиксируем b и с и начнем увеличивать d на x, тогда целевая функция приобретает вид:
      (1-x+4*x)*x^(x)*1*1*(1-x)^(1-x)
      Из графика этой функции видно, что на интервале от 0 до 1/4 значение функции падает (я понимаю, что указывать на график неприлично, но можно рассчитать значения на краях интервала и указать на поведение производной на этом интервале).
      Поскольку значение d никоим образом не может превзойти 1/4, считаем доказательство завершенным.
        0
        Мы не можем, зафиксировав b=с=0, увеличивать d. Условие b>c>d нарушится.
          +2
          Ни a, ни b, ни c, ни d не могут быть равны нулю по условию. Из этого следует, что ни одно число также не может быть равно единице. Более того, как минимальная оценка справедливо:
          0 < d <= 1/4
          0 < c < 1/3
          0 < b < 1/2
          1/4 <= a < 1.

          Не очень понимаю, как и почему вы зафиксировали только 2 числа.

          P.S. Промучался минут 40 с этой задачей, но так и не смог доказать. Возможно, нужно какое-то особое свойство вспомнить
            0
            В вашем решении вы возводите 0 в степень 0, а это неопределенность. Кроме того, по условию b > c > d > 0 — обратите внимание на строгие неравенства. Нельзя принимать c и d за 0.
              +5
              Оценим максимальное значение каждого параметра
              a < 1
              b < 1/2
              c < 1/3
              d < 1/4
              

              Откроем скобки в выражении (a + 2b + 3c + 4d) a^a * b^b * c^c * d^d и получим 4 слагаемых:
              a^(a+1) * b^b       * c^c       * d^d
              a^a     * 2*b^(b+1) * c^c       * d^d
              a^a     * b^b       * 3*c^(c+1) * d^d
              a^a     * b^b       * c^c       * 4*d^(d+1)
              

              Функция x^x < 1 на интервале (0, 1), с максимумом в точках 0.0(0) и 0.9(9) и минимумом в точке 1/e.
              Для максимизации произведения приравняем b^b, c^c и d^d к единице и получим:
              a^(a+1)
              a^a     * 2*b^(b+1)
              a^a     * b^b       * 3*c^(c+1)
              a^a     * b^b       * c^c       * 4*d^(d+1)
              

              Докажем что каждое слагаемое меньше числа по диагонали:
              a^(a+1)                                     <= a
              a^a     * 2*b^(b+1)                         <= b
              a^a     * b^b       * 3*c^(c+1)             <= c
              a^a     * b^b       * c^c       * 4*d^(d+1) <= d
              

              Функция x^(x+1) строго возрастающая на интервале (0,1), при этом ее точки лежат ниже точек линейной функции, а значит в каждой точке x^(x+1) < x. Приведем все выражения к общему виду:
              a^(a+1)                                           <= a (доказано)
              a^(a+1) * b^(b+1)                     * 2/a       <= b
              a^(a+1) * b^(b+1) * c^(c+1)           * 3/(a*b)   <= c
              a^(a+1) * b^(b+1) * c^(c+1) * d^(d+1) * 4/(a*b*c) <= d
              

              Вспомним что для прямоугольников с одинаковым периметром максимум площади достигается при равенстве сторон, аналогично для трехмерного и четырехмерного куба.
              a^(a+1)                                   <= a (доказано)
              b^(b+1) * b^(b+1)                     * 2 <= b^2
              c^(c+1) * c^(c+1) * c^(c+1)           * 3 <= c^3
              d^(d+1) * d^(d+1) * d^(d+1) * d^(d+1) * 4 <= d^4
              

              Подставим максимумы переменных из самого первого абзаца
              1^(1+1)                                                               = 1     (доказано)
              1/2^(1/2+1) * 1/2^(1/2+1)                             * 2 = 1/2^3 * 2 = 1/2^2 (доказано)
              1/3^(1/3+1) * 1/3^(1/3+1) * 1/3^(1/3+1)               * 3 = 1/3^4 * 3 = 1/3^3 (доказано)
              1/4^(1/4+1) * 1/4^(1/4+1) * 1/4^(1/4+1) * 1/4^(1/4+1) * 4 = 1/4^5 * 4 = 1/4^4 (доказано)
              

              Так как a + b + c + d = 1, то все выражение строго меньше единицы.
                0

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


                Всё, вопрос снимается. Поняла: цепочка неравенств из условия.

              –1
              Задача 5.
              Рассмотрим 2 карточки и покажем что для них числа должны быть равны.
              Действительно, либо (a+b)/2=sqrt(a) и это уравнение не имеет решения при a>1,
              либо (a+b)/2=sqrt(a*b) и имеется единственное решение a=b.
              А вот что делать дальше, я как то не пойму.
                0

                Нет. (a+b)/2=sqrt(x1x2...*xk) где xi — какие то карточки

                  0
                  Ну да, Вы правы, первый вариант (a+b)/2=a, откуда a=b. То есть для n=2 доказано, но что делать дальше?
                    0
                    Вы неверно поняли условие, давайте на примере.
                    Допустим у нас есть n=5 чисел: x1, x2, x3, x4, x5
                    Возьмем две карточки x1 и x2, тогда по условию должно выполняться хотя бы одно равенство:
                    (x1+x2)/2 = x1 или = x2 или = x3 и т.д.
                    (x1+x2)/2 = sqrt(x1*x2) или = sqrt(x2*x3) или = sqrt(x3*x5) ...
                    (x1+x2)/2 = cbrt(x1*x2*x3) или = cbrt(x1*x3*x5) или = cbrt(x3*x4*x5) ...
                    (x1+x2)/2 = 4thrt(x1*x2*x3*x4) или = 4thrt(x1*x2*x3*x5) или = 4thrt(x2*x3*x4*x5) ...
                    (x1+x2)/2 = 5thrt(x1*x2*x3*x4*x5)
                    

                    Где cbrt — это кубический корень, 4thrt и 5thrt — корень 4 и 5 степени соответственно.
                    И так для каждой пары x1 и x3, x1 и x4, x1 и x5, x2 и x3,…

                    Кстати все числа на карточках должны быть либо только четными, либо только нечетными, но не одновременно.

                    Можно вспомнить про AM–GM inequality и использовать неравенство (x1+x2)/2 >= sqrt(x1*x2)
                    Преобразуем все выражения к виду
                    (x1+x2)/2 = cbrt(x1*x2*x3)
                    ->
                    cbrt(x1*x2*x3) >= sqrt(x1*x2)
                    ->
                    x1^2/3 * x2^2/3 * x3^2/3 >= x1*x2
                    


                    В итоге получим такие выражения
                    x3^2                                        >= x1*x2
                    x3 * x4                                     >= x1*x2
                    x3^2/3 * x4^2/3 * x5^2/3                    >= x1*x2
                    x3^2/4 * x4^2/4 * x5^2/4  * x6^2/4          >= x1*x2
                    x3^2/5 * x4^2/5 * x5^2/5  * x6^2/5 * x7^2/5 >= x1*x2
                    

                    Рассмотрим 1 выражение, есло оно строго больше (x3^2 > x1*x2) то x3 > min(x1,x2)
                    Заменим x1 на x3 в паре чисел, теперь для выполнения похожего неравенства нам нужно x4 > min(x3,x2), найдя максимальное x7 мы придем к выводу что такое неравенство выполняется только при x7^2 = x5*x6, а это значит что все числа равны.

                    Аналогично доказывается 2 выражение x3 * x4 >= x1*x2 (доказательство я пропущу).

                    3 выражение использует ту же аналогию с нахождением пары максимальных чисел, например для x3^2/3 * x4^2/3 * x5^2/3 >= x1*x2 представим что x3 и x4 максимальные числа из всего набора, а x5 следующее после них. Попробуем найти числа которые бы удовлетворяли этому выражению
                    x3^2/3 * x4^2/3 * x5^2/3 >= x3*x4
                    сократив x3^2/3 и x4^2/3 получим
                    x5^2/3 >= x3^1/3 * x4^1/3
                    что равносильно
                    x5^2 >= x3 * x4
                    которое мы уже доказывали
                    

                    По аналогии 4, 5, 6 и n выражения сводятся из неравенства к равенству (т.к. сумма степеней слева и справа равны).

                    Рискну предположить что для любого n>=2, все числа на карточках должны быть равны.
                      0

                      Хитрость задачи в том, что она про целые числа. С вещественными, уже при n >= 3 можно получить набор, где не все равны: x1 = x2 = А, остальные числа В, так что А>В, и (А + В)/2 = cbrt(AAB)

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


                1 1 1 1
                2 2 2 2
                3 3 3 3
                4 4 4 4

                1+4 1+4 2+3 2+3 = 1+4 1+4 2+3 2+3
                2х1 2х2 2х3 2х4

                  +1

                  Осилил №3


                  Разобьем все камни попарно: (1, 4N), (2, 4N-1),… (2N, 2N+1). У нас получилось 2N одинаковых пар, которые нужно разделить на две кучки по N пар так, что бы для любого цвета в каждую кучку попало 2 камушка.


                  Построим граф следующего вида:


                  Построим N вершин, раскрасив их в N заданных цветов. Проведем по ребру для каждой пары камней. Например, если у нас есть красно-зеленая пара, мы проводим для неё ребро от красной до зеленой вершины.


                  Получился 4-регулярный граф (граф, из каждой вершины которого исходит 4 ребра).


                  На таком графе наша задача сводится к построению остовного 2-регулярного подграфа (подграфа, содержащего каждую вершину исходного графа). Если мы построим такой подграф и сложим все пары камешков, соответствующих его ребрам, в одну кучку, а все остальные — в другую, задача будет решена.


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


                  Время переформулировать задачу более математично:


                  Задача:


                  Дан односвязанный 4-регулярный граф. Докажите, что можно выделить внутри него остовный 2-регулярный подграф.


                  Решение (взято из статьи Petersen, J.; Die Theorie der regularen Graphs):


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


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


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

                    +1
                    Можно еще попробовать доказать через замощение плитками, но тяжело показать в коментарии

                    Общая идея:
                    У нас есть N цветов, обозначим их через буквы
                    a, b, c, d, e, ...

                    Для каждого цвета есть 4 камня, обозначим их соответственно
                    a1, a2, a3, a4

                    При разбиении на 2 кучи в каждую должны попасть по 2 камня, обозначим это как
                    a1, a2 | a3, a4

                    Как уже указано выше существуют пары: (1, 4N), (2, 4N-1),… (2N, 2N+1)
                    Вот тут как раз сложность, я бы обводил пары и рисовал между ними связь
                    Будем использовать для этого разные скобки (a) [b] {c}
                    Существует всего 2 возможных вида связей: пара со своим цветом (a-a), пара с чужим цветом (a-b)
                    
                     a1   a2  | [a3]  a4
                    (b1) (b2) | [b3] {b4}
                     с1   с2  |  с3  {с4}
                    

                    В примере у нас пары: b1-b2, b3-a3, b4-c4
                    Причем комбинации b4-c1, b4-c2, b4-c3 сводятся к комбинации b4-c4 при перестановки камня c1 на место с4 и т.д.
                    Дальше нужно показать что при конечном полотне всегда можно сделать такую перестановку которая будет покрываться этими 2 правилами a-a и a-b
                    Я бы показал сначала на примере с 3 цветами, а потом нарисовал цепочки, чтобы показать что они в конечном итоге замыкается в такие же шаблоны.

                    Пример для 3 цветов (пары a2-a4 и c1-c3 нужно переставить)
                    
                     (a1)   {a2}  |  [a3]   {a4}                (a1)   [a3]  |  {a2}   {a4}
                     (b1)  ((b2)) |  [b3]  [[b4]]      ->       (b1)   [b3]  | ((b2)) [[b4]]
                    {{с1}} ((с2)) | {{с3}} [[с4]]              {{с1}} {{с3}} | ((с2)) [[с4]] 
                    

                    и второй пример (пары a2-c3 и a4-c1 нужно переставить)
                    
                     (a1)   {a2}  | [a3] {{a4}}      ->      (a1)  {a2}  |  [a3]  {{a4}}
                     (b1)  ((b2)) | [b3] [[b4]]      ->      (b1) ((b2)) |  [b3]  [[b4]]
                    {{с1}} ((с2)) | {с3} [[с4]]      ->      {с3} ((с2)) | {{с1}} [[с4]]
                    

                    +1
                    1-я и 4-я задачи классифицируются как лёгкие
                    2-я и 5-я — как средние
                    3-я и 6-я — как тяжёлые
                    На ММО-2007 третью и шестую задачи решили по 5 человек из нескольких сотен лучших в своих странах молодых математиков.
                      0
                      А кто-то знает как решить 6ю задачу? Очень интересно посмотреть на ход рассуждений.
                        0
                        Написал Савватееву, возможно он или его падаваны сделают стрим.
                          +1
                          Да там все интересны :)
                          А с 6 там надо скорее всего начинать с размещения кругов на плоскости
                          image

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

                        Самое читаемое