Comments 18
Значение целевой функции достигает 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 < d <= 1/4
0 < c < 1/3
0 < b < 1/2
1/4 <= a < 1.
Не очень понимаю, как и почему вы зафиксировали только 2 числа.
P.S. Промучался минут 40 с этой задачей, но так и не смог доказать. Возможно, нужно какое-то особое свойство вспомнить
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, то все выражение строго меньше единицы.
Рассмотрим 2 карточки и покажем что для них числа должны быть равны.
Действительно, либо (a+b)/2=sqrt(a) и это уравнение не имеет решения при a>1,
либо (a+b)/2=sqrt(a*b) и имеется единственное решение a=b.
А вот что делать дальше, я как то не пойму.
Нет. (a+b)/2=sqrt(x1x2...*xk) где xi — какие то карточки
Допустим у нас есть 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, все числа на карточках должны быть равны.
Докажите, что камушки можно разделить на две кучи равного суммарного веса так, чтобы в каждой куче было по два камушка каждого цвета.
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
Осилил №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 белых, и так как мы посетили каждую вершину ровно два раза, из каждой вершины будет исходить два черных и два белых ребра.
Совокупность всех черных (или белых) ребер имеет в каждой вершине ровно два ребра и включает в себя все вершины исходного графа. А значит, это и есть нужный нам остовный подграф.
Общая идея:
У нас есть 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]]
2-я и 5-я — как средние
3-я и 6-я — как тяжёлые
На ММО-2007 третью и шестую задачи решили по 5 человек из нескольких сотен лучших в своих странах молодых математиков.
Международная математическая олимпиада 2020 (решаем в комментах)