В группе школьников некоторые знакомы между собой, а некоторые нет. Оказалось, что если какой-то школьник знаком хотя бы с 20 другими школьниками, то все его знакомые незнакомы между собой. Кроме того, если школьник незнаком хотя бы с 20 другими школьниками, то все его незнакомые знакомы между собой. Найдите максимальное возможное число школьников в такой группе.
Подсказка
Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.
Решение
Ответ: 40 школьников.
Решение. Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.
Оценка. Предположим, что у какого-то школьника 
есть хотя бы 21 знакомый 
. По условию, все его знакомые незнакомы. Но тогда у школьника 
есть 20 незнакомых 
и они незнакомы друг с другом. Противоречие. Следовательно, у каждого школьника не более 20 знакомых и, аналогично, не более 20 незнакомых. Тогда школьников всего не более 41. Осталось доказать, что невозможен случай, когда школьников ровно 41 . Пусть так. Тогда у школьника ровно 20 знакомых 
и ровно 20 незнакомых 
. Причем все 
попарно незнакомы, а все 
попарно знакомы. У также должно быть ровно 20 знакомых, которые незнакомы между собой. Он уже знает и не знает никого из . Следовательно, он знаком с хотя бы 19 школьниками из . Но попарно знакомы. Противоречие.