Рукопожатия и графы.

Докажите, что число участников последнего конгресса биофизиков, обменявшихся рукопожатиями нечетное число раз, четно.

Ответ

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

О задаче

Категория: Графы, Четность,
Степень сложности: сложная.
Ключевые слова: рукопожатие, совещание,
Источник: Математические головоломки и развлечения, Сборник задач по математике на сообразительность,

Скачать задачу

Вы можете скачать изображение с текстом задачи, поделиться им с друзьями в социальных сетях либо использовать в презентациях. Для скачивания, нажмите на картинке.