Олимпиадная задача по отношениям порядка для 10 класса — ученики и друзья

  Учеников, которые учатся лучше большинства своих друзей, назовём хорошими. Пусть n – число хороших учеников, k – число друзей у каждого ученика. Докажем, что  n ≤ 25.  Для этого разберём два случая.

  1)  k ≥ 8.  Тогда пять худших учеников класса не являются хорошими.

  2)  k ≤ 7.  Лучший ученик класса является лучшим в k парах друзей, а любой другой хороший ученик – не менее, чем в  ^k+1/₂  парах. Поэтому хорошие ученики являются лучшими не менее, чем в  k + (n – 1)·^k+1/₂  парах. Это число не может превышать числа всех пар друзей в классе, равного 15k. Отсюда   2k + (n – 1)(k + 1) ≤ 30k,   то есть   n – 1 ≤ 28·^k/_k+1 = 28 – ²⁸/_k+1 ≤ 28 – ²⁸/₈ = 24,5.  Значит, и в этом случае  n ≤ 25.

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

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

25 учеников.