Question

В классе учатся n⩾4 человек. Каждый из них дружит хотя бы с одним одноклассником, но не со всеми. Докажите, что можно выбрать четверых из них и посадить за круглый стол так, чтобы каждый знал ровно одного из двух своих соседей.

Answer 1

Предположим, что не существует таких двух пар друзей, что никто из первой пары друзей не дружит ни с кем из второй пары друзей.

Пусть какой-то 1-й дружит со 2-м, но тогда 3-й обязан дружить либо с первым, либо со вторым, иначе выйдет, что он дружит только с людьми отличными от первого и второго, а значит существовала бы вторая пара,  оговоренная вначале. Таким образом, каждый школьник дружит с 1-м или 2-м, при этом могут быть школьники, которые дружат с первым и вторым одновременно. Однако, никто из школьников не может дружить со всеми, а значит 1-й не знает хотя бы одного n-го школьника, cоответственно тот в свою очередь обязательно дружит со 2-м школьником. Аналогично, 2-й школьник не знает хотя бы одного m-го школьника, который соответственно обязательно дружит с 1-м школьником. Посадим: 1-го,2-го, n-го, m-го школьников за один стол так, что 1-й и 2-й не являются соседями, соответственно n-й и m-й тоже не соседи. Рядом с n-м сидит 1-й и 2-й, но n-й знает только 2-го. Рядом с m-м также сидят первый и второй, однако m-й дружит только с 1-м. Аналогично, рядом с 1-м и 2-м cидят m-й и n-й, но каждый из них знает только кого то одного из них. То есть условия задачи выполнены. Если же существуют две пары друзей, что никто из первой пары друзей не дружит ни с кем из второй пары друзей, то достаточно посадить эти две пары за один стол, так, что школьники из одной пары сидят рядом. Таким образом, каждый из них дружит только с тем из соседей с кем он в дружеской паре. Как видим, во всех случаях можно добиться условий требуемых в задаче.

Что и требовалось доказать.

Answer 2

Давайте докажем это утверждение по индукции.

Базовый шаг: Пусть n = 4. В этом случае у нас есть 4 человека. Поскольку каждый из них дружит хотя бы с одним одноклассником, но не со всеми, то существует хотя бы одна пара друзей. Выберем двух из них и посадим напротив друг друга за круглый стол. Теперь осталось два человека. Поскольку каждый из них дружит хотя бы с одним из первых двух, то они дружат друг с другом. Посадим их в оставшиеся два места. Теперь каждый человек знает ровно одного из двух своих соседей.

Индукционный переход: Предположим, что утверждение верно для всех n от 4 до k, где k > 4. Докажем, что оно верно и для n = k + 1.

У нас есть k + 1 человек, каждый из которых дружит хотя бы с одним одноклассником, но не со всеми. Рассмотрим одного из них, обозначим его как A. Он дружит хотя бы с одним человеком, обозначим этого друга как B.

Рассмотрим оставшиеся k человек. По предположению индукции, можно выбрать k из них и посадить за круглый стол так, чтобы каждый знал ровно одного из двух своих соседей. Обозначим этот круглый стол как "стол 1".

Теперь рассмотрим всех k + 1 человека вместе с A. Поскольку A дружит с B, то они могут быть посажены в соседние места за "столом 1". Теперь осталось рассмотреть оставшихся k - 1 человека, для которых у нас уже есть подходящие соседи по "столу 1". По предположению индукции, мы можем их посадить за второй круглый стол так, чтобы каждый из них знал ровно одного из двух своих соседей.

Таким образом, мы получили два круглых стола, на которых каждый человек знает ровно одного из двух своих соседей. Это завершает доказательство по индукции.

Следовательно, утверждение верно для всех n ⩾ 4.