В классе учатся n⩾4 человек. Каждый из них дружит хотя бы с одним одноклассником, но не со всеми. Докажите, что можно выбрать четверых из них и посадить за круглый стол так, чтобы каждый знал ровно одного из двух своих соседей.
Ответы
Предположим, что не существует таких двух пар друзей, что никто из первой пары друзей не дружит ни с кем из второй пары друзей.
Пусть какой-то 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-й, но каждый из них знает только кого то одного из них. То есть условия задачи выполнены. Если же существуют две пары друзей, что никто из первой пары друзей не дружит ни с кем из второй пары друзей, то достаточно посадить эти две пары за один стол, так, что школьники из одной пары сидят рядом. Таким образом, каждый из них дружит только с тем из соседей с кем он в дружеской паре. Как видим, во всех случаях можно добиться условий требуемых в задаче.
Что и требовалось доказать.