Комбинаторика на ЮМШ

Пункт а, подсказка 1

Нам нужно как-то оценить f. При этом в числителе мы видим сумму всех попарных произведений, а в знаменателе — сумму квадратов. Как можно связать квадраты и попарные произведения?

Пункт а, подсказка 2

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

Пункт а, подсказка 3

Внесём двойку под знак суммы. Получится, что числитель — это сумма всех возможных удвоенных произведений, каждое из которых не больше, чем сумма квадратов множителей. Оценим так каждое слагаемое. Сколько раз в итоговой сумме встретится квадрат каждого из чисел xᵢ?

Пункт а, подсказка 4

Столько же, сколько каждое из чисел xᵢ встречается во всевозможных попарных произведениях! Или столько же, сколько рёбер выходит из вершины xᵢ.

Пункт а, подсказка 5

Степень вершины равна количеству рёбер, выходящих из неё! Поэтому квадрат каждого числа в числителе встречается ровно d раз. Чему в таком случае равна вся дробь?

Пункт а, подсказка 6

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

Пункт b, подсказка 1

Подумаем, а что будет, если граф нельзя покрасить в [M]+1 цветов так, чтобы никакие две соседние вершины не были одноцветными?

Пункт b, подсказка 2

Это значит, что найдется такой подграф, степени всех вершин которого не меньше [M]+1. Например, это может быть полный подграф из [M]+1 вершине. Попробуйте как-нибудь использовать это при подсчёте f.

Пункт b, подсказка 3

Чему будет равно значение f, если в каждой вершине выбранного подграфа будет стоять единичка, а в остальных вершинах — ноль?

Пункт b, подсказка 4

Верно, значение функции будет равно [M]+1. Постойте, а не противоречит ли это условию?

Пункт c, подсказка 1

Нам нужно доказать, что максимальное значение суммы всех попарных произведений равно определенному выражению. Утверждение не самое очевидное, поэтому попробуйте проверить, выполняется ли это на каком-нибудь простом графе.

Пункт c, подсказка 2

В задаче фигурирует клика — подмножество вершин графа, в котором любые 2 вершины соединены ребром. Будем рассматривать максимальную клику, ведь в ней как раз w вершин. Кажется, отделив вершины этой клики от остальных, гораздо проще придумать пример!

Пункт c, подсказка 3

В вершины максимальной клики поставим 1/w, а в остальные вершины — 0. Тогда искомое значение Z действительно достигается! Ура, мы доказали, что есть такие расстановки (по крайней мере одна) при которых утверждение задачи верно! Теперь попробуем доказать, что при изменении такой расстановки утверждение остаётся верным! Не забудьте учесть, что сумма всех чисел на вершинах равна 1.

Пункт c, подсказка 4

Обратите внимание на вершины, в которых стоит 0. Можно ли их просто убрать?

Пункт c, подсказка 5

Да, можно, ведь они никак не влияют на сумму попарных произведений. Однако придётся учесть изменения в размере максимальной клики! После этого у нас получится граф с положительными числами в каждой вершине. Пусть S(v) — сумма чисел в вершинах, смежных с v. Остался последний рывок! Подумайте, что можно сказать об этой величине для несмежных вершин.