Задача 061 — Задачи на Графы

Дано нечетное число $k>1$ и натуральное $n>k . B$ компании из $n$ школьников среди любых $k$ школьников найдется школьник, знакомый с остальными $k-1$ школьниками. Найдите все значения $n$ и $k$ , при которых можно утверждать, что в такой компании всегда найдется школьник, знакомый со всеми. Знакомства взаимные.

Подсказка

Пусть $n$ четно. Покажем, что можно познакомить между собой $n$ школьников так, что никакой школьник не будет знаком со всеми остальными, но среди любых $k$ из них найдется школьник, знающий оставшихся $k-1$ школьников. Разобьем школьников на пары и познакомим их так, чтобы школьники из одной пары были незнакомы между собой, а из разных пар — знакомы.

Решение

Тогда и только тогда, когда $n$ нечетно. Решение. Пусть $n$ четно. Покажем, что можно познакомить между собой $n$ школьников так, что никакой школьник не будет знаком со всеми остальными, но среди любых $k$ из них найдется школьник, знающий оставшихся $k-1$ школьников. Разобьем школьников на пары и познакомим их так, чтобы школьники из одной пары были незнакомы между собой, а из разных пар — знакомы. Выберем любых $k$ школьников. Поскольку компанию из нечетного числа школьников нельзя разбить на пары, среди них найдется такой, у которого незнакомый ему школьник в эту группу из $k$ человек не вошел. Поэтому этот школьник знает всех остальных $k-1$ школьников. Таким образом, при четном $n$ искомый способ знакомства существует.

Пусть $n$ нечетно. Достаточно показать, что если нет школьника, который знает всех, то условие задачи не выполнено. В компании найдется школьник Вася, которому незнакомы хотя бы два других школьника (иначе компания должна разбиться на пары незнакомых школьников, что при нечетном $n$ невозможно). Покажем, что в этой компании не будет выполнено условие о группе из $k$ школьников. Будем набирать эту группу постепенно. Сначала поместим в нее Васю и каких-то двух незнакомых ему школьников. На каждом шаге будем добавлять в группу двух еще не добавленных в нее незнакомых друг с другом школьников. Поскольку в каждый момент времени количество школьников в группе будет нечетным, то либо на какомто шаге в группе окажется ровно $k$ школьников (и тогда по построению у каждого в группе будет незнакомый ему школьник из группы), либо в какой-то момент окажется, что среди оставшихся школьников все попарно знакомы. Во втором случае у любого оставшегося школьника есть незнакомый ему школьник из группы. Поэтому, если мы доберем группу до $k$ школьников как угодно, то у любого школьника в группе снова будет незнакомый школьник среди остальных школьников группы. Итак, снова найдена группа из $k$ школьников, среди которых нет такого, который знает всех остальных из группы.