|
|
 |
Условие
На собрание пришло n человек (n > 1). Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых.
а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.
б) Покажите, что n может быть больше 4.
Решение
а) Пусть A – один из пришедших на собрание людей, а {B, C} – какая-либо пара знакомых A. Так как у B и C есть ровно двое общих знакомых, то кроме A найдётся ещё ровно один их общий знакомый. Назовём его D и сопоставим его паре {B, C}. Два общих знакомых у A и D нам уже известны – это B и C. Значит, D не мог быть сопоставлен никакой другой паре знакомых A. С другой стороны, каждый из пришедших на собрание, кроме самого A, имеет с ним ровно двух общих знакомых и, значит, был сопоставлен какой-либо паре его знакомых. Так как таких пришедших было ровно n – 1, то и пар знакомых у A столько же, то есть ½ k(k + 1), где k – количество знакомых A. Для каждого n может существовать только одно натуральное k, удовлетворяющее этому равенству. Следовательно, у каждого из пришедших одно и то же число знакомых на этом собрании.
б) Расставим 16 человек в клетках таблицы 4×4 и будем считать знакомыми людей, стоящих в одной строке или одном столбце. Условия задачи, очевидно, выполнены.
