Школьники сдавали семь экзаменов, и все сдали их только на «4» и «5», причём каждый получил не более двух четвёрок. Известно, что нет двух учеников, один из которых по каждому предмету получил оценку не ниже, чем второй. Докажите, что учеников было не более 21.

Для каждого ученика запишем множество экзаменов, по которым он получил «4». В этом множестве не более двух элементов. Оценки остальных экзаменов — «5».

Если множество четвёрок одного ученика содержится в множестве четвёрок другого, то первый получил по каждому предмету оценку не ниже: на экзаменах из его множества оба получили «4», а на остальных у первого «5», то есть не меньше оценки второго. По условию такой пары учеников нет. Значит, множества четвёрок учеников не могут содержаться друг в друге.

Множества размера 0 или 1 не могут входить в такую семью вместе с другими множествами: пустое множество содержится в любом, а одноэлементное множество содержится в любом большем множестве, которое его включает. Чтобы получить наибольшее количество попарно несравнимых множеств при размере не более двух, можно взять все двухэлементные множества. Их \(\binom{7}{2}=21\). Следовательно, учеников не более 21.

Что и требовалось доказать.