Всесиб 2023, 9 класс, задача 5

Ответ. Все , не равные и .

Доказательство. . Примеры. При в любом случае оба участника имеют одинаковое число знакомых или , но отсутствуют кандидаты на роль общего знакомого или незнакомого. При единственным примером, когда нельзя найти или , является компания, где первый знаком со вторым, второй с третьим, а третий - с четвёртым, и других знакомств нет.

. Приведём хорошо известное доказательство того, что в любой компании найдутся хотя бы два человека, имеющих в ней одинаковое число знакомых. Количество знакомых у члена компании из человек может равняться любому натуральному числу от до . При этом в компании не могут одновременно быть люди, число знакомых у одного из которых равно , а у другого , потому что первый из них не знает в компании никого, включая второго, а второй знает всех, включая первого. Такая ситуация противоречит условию, что, если знаком с , то и знаком с . Следовательно, количество знакомых для любого из членов компании является числом либо из интервала от до , либо из интервала от до . В обоих интервалах всего по числу, поэтому из принципа Дирихле следует, что, как минимум, у каких-то двух членов компании числа знакомых совпадают.

. До этого момента шёл стандартный текст, далее начинается специфика именно этой задачи. Если предположить, что у людей и , имеющих одинаковое количество знакомых, нет общих знакомых и незнакомых в этой компании, то вся компания состоит из , , знакомых и знакомых , которых поровну. Следовательно, любые два человека и , имеющие одинаковое количество знакомых, и не имеющие общих знакомых и незнакомых в этой компании, имеют ровно по знакомых в случае, когда они не знакомы между собой, или ровно по знакомых в случае, когда они знакомы. Поэтому, если в компании есть пары людей с другими равными количествами знакомых, то у них есть либо общие знакомые, либо общие незнакомые и задача решена. В частности, отсюда следует, что при всех нечётных , больших одного, требуемые в условии и найдутся.

. Далее считаем, что больше двух, и в этой компании у любой пары людей с одинаковым числом знакомых нет общих знакомых и незнакомых. Тогда в компании не может быть людей с или знакомыми, так как они и были бы соответственно общими знакомыми или незнакомыми. Совпадать с или эти люди не могут, так как при больше двух у них не меньше одного и не больше знакомых. Следовательно, количество знакомых для любого из членов этой компании является числом из интервала от до , где всего числа, причём повторяться могут только два значения, и .

Случай . В компании найдутся как минимум три члена , и , каждый из которых знает ровно из остальных членов компании, причём является знакомым либо , либо . Можно считать, что он знает , тогда он не может знать ни одного знакомого , иначе тот был бы общим знакомым и . Следовательно, все его знакомые - это и знакомые , отличные от самого . В таком случае является общим незнакомым для и и требуемая в условии пара найдена.

Случай . В компании найдутся как минимум три члена , и , каждый из которых знает ровно из остальных членов компании. Но при этом , и должны знать друг друга, поэтому будет общим знакомым и .

Случай . В компании найдутся ровно два знакомых между собой и , каждый из которых знает в точности других членов компании, и ровно два других, незнакомых между собой и , каждый из которых знает в точности из остальных членов компании. При это как раз и даёт единственный контрпример, далее . Все знакомые должны иметь разное количества знакомых, иначе был бы общим знакомым для двух из них, аналогично и для знакомых , поэтому можно считать, что знает , а знает . Назовём -участниками членов компании, знакомых с и отличных от , и -участниками членов компании, знакомых с и отличных от . Участники и не могут иметь общих знакомых, поэтому знает столько же -участников компании, сколько знает -участников, и знает столько же -участников компании, сколько знает -участников. Важно отметить, что каждый член компании, кроме , , и знает ровно двух из , , и . Рассмотрим новую компанию, образованную всеми членами первоначальной компании, отличными от , , и , среди них снова найдётся хотя бы пара членов и с одинаковым количеством знакомых в новой компании. При переходе к новой компании мы удалили у каждого по два знакомства, значит, и в прежней компании у и было одинаковое количество знакомых, что противоречит рассматриваемому случаю. Следовательно, при чётных рассматриваемый случай невозможен, что завершает доказательство.