Задача: В 8а, 8б, 8в классах по 30 учеников. Оказалось, что если взять по ученику из каждого класса, то среди этих трех учеников найдутся двое знакомых и двое незнакомых. Докажите, что най-дется ученик, который знает всех учеников в одном из двух других классов.
Решение: Для каждого ученика класса а определим его ранг, как наибольшее из четырех чисел: числа его знакомых в классе б, числа незнакомых ему в классе б, числа его знакомых в классе в, числа незнакомых ему в классе в. Аналогично определим ранги учеников двух других классов. Возьмем ученика, имеющего наибольший возможный ранг. Не умаляя общности можно считать, что это Петя из класса а.
Пусть ранг Пети равен 30. Если у него 30 знакомых в каком-то классе, все доказано. Если он не знаком ни с одним учеником, скажем, из класса б, то всякий ученик класса в, незнакомый с Петей, должен быть знаком со всеми учениками класса б, и все доказано, если же все в классе в знакомы с Петей, то тоже все доказано.
Пусть ранг Пети меньше 30 и равен числу его знакомых в классе б. Тогда всякий знакомый Пети из класса в незнаком со всеми знакомыми Пети из класса б и, кроме того, знаком со всеми остальными учениками класса б, так как иначе его ранг был бы больше ранга Пети. Но и всякий незнакомый Пете ученик класса в также должен быть знаком со всеми учениками класса б, не-знакомыми с Петей. Получается, что каждый ученик класса б, незнакомый с Петей (а такие есть, так как ранг Пети меньше 30), знаком со всеми учениками класса в, и ранг каждого такого уче-ника больше ранга Пети — противоречие.
Если ранг Пети меньше 30 и равен числу не знакомых ему учеников класса б, противоречие получается аналогично.
