Задача 108403
|
|
 |
Условие
Выбежав после уроков на двор, каждый школьник кинул снежком ровно в одного другого школьника.
Докажите, что всех учащихся можно разбить на три команды так, что члены одной команды друг в друга снежками не кидали.
Решение
Рассмотрим соответствующий граф: школьников-вершины соединим стрелочкой, если один кидал во второго. Этот граф распадается на несколько циклов с "рожками" (путями, ведущими от точки в цикл). Каждую такую фигуру легко разбить на три группы: разрывая цикл, одного школьника относим в первую группу, а получившиеся деревья разбиваем на чётные и нечётные вершины.
