Олимпиадная задача по теории графов от Сергеева П. В. для 11 класса

  а) Пусть 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, удовлетворяющее равенству k² - k - 2(n-1) = 0 . Следовательно, у каждого из пришедших одно и то же число знакомых на этом собрании.   б) Расставим 16 человек в клетках таблицы 4×4 и будем считать знакомыми людей, стоящих в одной строке или одном столбце. Условия задачи, очевидно, выполнены.

Ответ задачи отсутствует