Задача 103767
|
|
 |
Условие
В спортклубе тренируются 100 толстяков весом от 1 до 100 кг. На какое наименьшее число команд их можно разделить так, чтобы ни в одной команде не было двух толстяков, один из которых весит вдвое больше другого?
Подсказка
Рассмотрите все пары толстяков, которые не должны оказаться в одной команде. Кроме того, можно считать, что все 100 толстяков разного веса.
Решение
Заметим, что наличие толстяков одинакового веса только упрощает задачу. Действительно, с каждым толстяком можно поместить в команду всех толстяков того же веса. При этом условие задачи по-прежнему будет выполнено. Значит, можно считать, что все 100 толстяков разного веса.В частности, у каждого толстяка есть не более чем один товарищ, который вдвое легче него, и не более чем один, который вдвое тяжелее него.
Теперь заставим наших толстяков взяться за руки: каждый из них подаст левую руку тому, который вдвое тяжелее него (если такой есть), а правую — тому, который вдвое легче него (если такой есть).
Получится, что вся сотня разобьётся на непересекающиеся ''цепочки''. Причём в каждой цепочке самый правый — это самый лёгкий, а самый левый — это самый тяжёлый.
Раскрасим каждую цепочку в два цвета в шахматном порядке, начиная с самого лёгкого. Теперь сформируем две искомые команды по ''цветному'' признаку.
Ответ
На две команды.
