Форум умных людей

(http://i51.fastpic.ru/big/2012/1224/30/f8783b20860bfa24eabdfb3f6dfbb230.jpg)

Учеников, которые учатся лучше большинства своих друзей, назовем хорошими. Пусть n – число хороших учеников, k – число друзей у каждого ученика. Докажем, что  n ≤ 25.  Для этого разберем два случая.
   1)  k ≥ 8.  Тогда пять худших учеников класса не являются хорошими.
   2)  k ≤ 7.  Лучший ученик класса является лучшим в k парах друзей, а любой другой хороший ученик – не менее, чем в (k+1)/2 парах. Поэтому хорошие ученики являются лучшими не менее, чем в k+(n-1)(k+1)/2 парах. Это число не может превышать числа всех пар друзей в классе, равного 15k. Отсюда   2k + (n – 1)(k + 1) ≤ 30k,   то есть n-1 ≤ 28k/(k+1) = 28 - 28/(k+1) ≤ 28 - 28/8 = 24,5
Значит, и в этом случае  n ≤ 25.
   Покажем, что n может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице 6×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

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