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

Условие

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

Ответ: 25.

Решение

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

x\leq28\frac{k}{k+1}+1 (1)

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

\frac{k+1}{2}\leq30-x (2)

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

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

k\leq59-2x (3)

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

x^{2}-59x+856\geq0 (4)

К задаче M1656

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

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

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 комментарий

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

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