a) На конференцию собрались учёные. Могло ли оказаться так, что каждый из них знаком с четырьмя другими учёными, кроме троих, которые знакомы ровно с пятью другими? б) В поход…

Решение задачи

Задача (a):

Условие: На конференцию собрались учёные. Могло ли оказаться так, что каждый из них знаком с четырьмя другими учеными, кроме троих, которые знакомы ровно с пятью другими?

Решение:

1. Понимание задачи: Нам нужно понять, возможно ли такое знакомство среди учёных. Учёные, о которых идет речь, могут быть связаны в графе, где узлы — это учёные, а ребра — это знакомство между ними.

2. Предположения:

   • Пусть всего n учёных на конференции.
   • Каждый из n - 3 учёных знаком с 4 другими, а 3 учёных знакомы с 5 другими.

3. Степени вершин:

   • Учёные, кроме троих, имеют степень 4.
   • А трое учёных имеют степень 5.

4. Сумма степеней:

   • Суммируем степени всех учёных: \[ (n - 3) \cdot 4 + 3 \cdot 5 \]
   • Упрощаем: \[ 4n - 12 + 15 = 4n + 3 \]

5. Четность суммы степеней:

   • В графе сумма степеней всех вершин всегда чётная (поскольку каждое звено соединяет две вершины, и мы считаем его дважды).
   • Следовательно, \( 4n + 3 \) должно быть чётным, что возможно только в том случае, если \( n \) — нечётное число.

6. Заключение:

   • Сумма \( 4n + 3 \) всегда нечётна, следовательно, такая конфигурация учёных невозможна.

Задача (б):

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

Решение:

1. Графовое представление: Обозначим туристов как вершины графа, а знакомства между ними как ребра.

2. Степени вершин: Степень вершины показывает число знакомых с данным туристом.

3. Определение нечётных степеней: У нас есть некоторый набор вершин (туристов) с нечётными степенями.

4. Сумма всех степеней: Как и ранее, сумма степеней всех вершин характера (всех туристов) равна удвоенному количеству рёбер, и поэтому она всегда четная.

5. Сумма всех степеней, включая нечётные:

   • Пусть \( k \) — количество туристов с нечётным количеством знакомых, и пусть \( s \) — сумма их степеней. Так как каждый турист с нечётной степенью добавляет 1 к общей четности суммы, количество нечетных степеней должно быть чётным — иначе всего бы не удалось сделать четным.

6. Заключение:

   • Таким образом, количество туристов, знакомых с нечётным количеством других туристов, должно быть чётным.

Итог

• В задаче (а) показано, что такая конфигурация знакомств невозможна.
• В задаче (б) доказано, что туристов с нечётным количеством знакомств всегда будет чётное число.