Задача о рукопожатиях.) Во время встречи некоторые участники по- жали руки другим. Докажите, что количество участников, сделавших нечётное число рукопожатий, чётно
Задача о рукопожатиях – это интересная концепция, которая относится к теории графов. Давайте рассмотрим её подробнее.
Представьте, что каждый участник встречи – это вершина графа, а каждое рукопожатие – это ребро, соединяющее две вершины. Если участник пожал руки другим, это означает, что он имеет некое количество «соседей» в графе.
Теперь представим, что у нас есть \(n\) участников встречи, и каждое рукопожатие делает его участник. Если мы сосчитаем количество рукопожатий каждого участника, то мы получим количество рёбер, которые исходят из каждой вершины. Мы хотим доказать, что количество участников с нечётным числом рукопожатий чётно.
Когда участник пожимает руки, количество рукопожатий увеличивается на 1 для обоих участников. Это означает, что каждое рукопожатие влияет на чётность числа рукопожатий обоих участников – если у участника было чётное число рукопожатий, то после рукопожатия станет нечётным, и наоборот.
Теперь давайте рассмотрим всех участников:
- Пусть \(k\) – количество участников с нечётным числом рукопожатий.
- Поскольку каждое рукопожатие изменяет чётность числа рукопожатий участников, за каждое рукопожатие количество участников с нечётным числом рукопожатий меняется.
Таким образом, если один участник с нечётным числом рукопожатий получает ещё одно рукопожатие, он становится равным чётному числу, а другой участник с чётным числом рукопожатий становится нечётным. Каждый раз, когда происходит такое изменение, количество участников с нечётным числом рукопожатий либо увеличивается на 2, либо уменьшается на 2.
Из этого следует, что количество участников с нечётным числом рукопожатий всегда будет чётным, так как оно может изменяться только парами.
Таким образом, мы доказали, что количество участников, сделавших нечётное число рукопожатий, действительно чётно.
