M1656. Оценка числа доминирующих вершин в вершинно-взвешенном графе

Условие

В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше.)

Ответ: 25.

Решение

Учеников, которые учатся лучше большинства своих друзей, назовем хорошими. Пусть [latex]x[/latex] — число хороших учеников, [latex]k[/latex] — число друзей у каждого ученика. Лучший ученик класса является лучшим в [latex]k[/latex] парах друзей, а любой другой хороший ученик — не менее, чем в [latex][k/2]+1 \geqslant (k+1)/2[/latex] парах (здесь квадратные скобки обозначают целую часть числа). Поэтому хорошие ученики являются лучшими не менее чем в [latex]k+(x-1)(k+1)/2[/latex] парах.
Это число не может превышать числа всех друзей в классе, равного [latex]30k/2=15k[/latex]. Отсюда [latex]k+(x-1)(k+1)/2 \leqslant 15k[/latex] или

[latex]x\leq28\frac{k}{k+1}+1[/latex] [latex](1)[/latex]

Заметим далее, что

[latex]\frac{k+1}{2}\leq30-x[/latex] [latex](2)[/latex]

поскольку число учеников, лучше которых учится наихудший из хороших, не превышает 30.

Правая часть неравенства [latex](1)[/latex] возрастает с ростом [latex]k[/latex], а неравенство [latex](2)[/latex] равносильно условию

[latex]k\leq59-2x[/latex] [latex](3)[/latex]

Из [latex](1)[/latex] и [latex](3)[/latex] следует, что [latex]x\leq28*\frac{59-2x}{60-2x}+1[/latex], или

[latex]x^{2}-59x+856\geq0[/latex] [latex](4)[/latex]

К задаче M1656

Наибольшим целым [latex]x[/latex], удовлетворяющим [latex](4)[/latex] и условию [latex]x \leq 30[/latex], является [latex]x=25[/latex]. Итак, число хороших учеников не превышает 25, что можно проиллюстрировать на графике.

Покажем, что оно может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице [latex]6\times 5[/latex] так, как показано на рисунке.

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30

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

  1. в соседних строках и в разных столбцах;
  2. в одном столбце и один из номеров при этом находится в нижней строке;
  3. в верхней строке.

При этом, как нетрудно проверить все требуемые условия выполнены.

С.Токарев

M1656. Оценка числа доминирующих вершин в вершинно-взвешенном графе: 1 комментарий

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *