Условие
В компании 8 человек каждый может пожать руку каждому другому не более одного раза. а) Возможно ли, что каждый пожал руку ровно одному человеку? б) Возможно ли, что ровно один человек сделал нечётное число рукопожатий? в) Найдите наибольшее общее число рукопожатий.
Подсказка
Разобьём 8 человек на 4 непересекающихся пар. В каждой паре одно рукопожатие. Каждый участвует ровно в одном — возможно.
Сумма чисел рукопожатий у всех людей вдвое больше числа рукопожатий и потому чётна. Сумма ровно одного нечётного числа и остальных чётных нечётна. Противоречие.
Показать ответ
а) да; б) нет; в) 28
Пошаговое решение
- Строим пример для а
Разобьём 8 человек на 4 непересекающихся пар. В каждой паре одно рукопожатие. Каждый участвует ровно в одном — возможно.
- Доказываем невозможность для б
Сумма чисел рукопожатий у всех людей вдвое больше числа рукопожатий и потому чётна. Сумма ровно одного нечётного числа и остальных чётных нечётна. Противоречие.
- Оцениваем максимум
Каждое рукопожатие соответствует неупорядоченной паре людей. Пар 8·7/2=28, больше быть не может.
- Доказываем достижимость
Если каждый пожмёт руку каждому, все 28 пар реализуются по одному разу. Следовательно, верхняя граница достигается.
Ответ: а) да; б) нет; в) 28