Question

В каждом из трех университетов обучается по 300 студентов. У любого студента всего 301 знакомый из двух других университетов. Докажите, что вы можете выбрать по одному студенту от каждого университета, так что выбранные три студента знакомы друг с другом

Answer 1

Ответ:

Среди всех 3n учеников выберем такого ученика (точнее, одного из таких учеников), который имеет наибольшее число kk знакомых в одной из двух других школ. Пусть для определенности им оказался ученик А первой школы, который знает kk учеников, например, из второй школы. Тогда А знает n+1–kn+1–k учеников из третьей школы, причем n+1–k≥1n+1–k≥1, так как k≤nk≤n. Рассмотрим ученика В третьей школы, знакомого с А. Если В знает хотя бы одного ученика С из kk знакомых А во второй школе, то ученики A, В, С образуют искомую тройку. Если же В не знает никого из kk знакомых А во второй школе, то в этой школе он знаком не более чем с n–kn–k учениками, а значит, в первой школе он знаком не менее чем с n+1−(n−k)=k+1n+1−(n−k)=k+1 учениками, что противоречит выбору kk.

Answer 2

Давайте рассмотрим три университета, обозначим их как Университет A, Университет B и Университет C. У нас есть по 300 студентов в каждом университете, и у каждого студента есть 301 знакомый из двух других университетов. Мы хотим доказать, что мы можем выбрать по одному студенту из каждого университета так, чтобы все они знали друг друга.

Давайте представим это графически:

• Университет A: 300 студентов
• Университет B: 300 студентов
• Университет C: 300 студентов

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

Итак, у нас есть три полностью связанных подграфа для каждого университета:

• Университет A: 300 узлов, все соединены между собой.
• Университет B: 300 узлов, все соединены между собой.
• Университет C: 300 узлов, все соединены между собой.

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

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