Гномы

[Евгений Машеров]

(Оффтоп)

TOTAL в сообщении #1075933 писал(а):

Делите на три группы произвольным образом. Затем перемещайте гномов между граппами так, чтобы число внутригрупповых обиженностей уменьшалось.

Я понимаю, что если перемещать гномов между граппами, что число обид может, и уменьшится. Лишь бы граппы хватило. Но из чего следует, что такое, уменьшающее число "обиженностей" перемещение между группами возможно?

-- 23 ноя 2015, 11:54 --

(поправляя фуражку прапорщика Ясненько, старшины роты к-на Очевидность, съехавшую набок во время строевых занятий):
Рисуем ориентированный граф обид. Он распадается на $n\ge 1$ циклов. Очевидно, вершины графа (гномов) из разных циклов можно помещать в одну и ту же группу без риска взаимных обид. Следовательно, каждый цикл можно разносить по группам независимо от других. Выстраиваем гномов из каждого цикла в одну шеренгу в порядке обид, начиная с произвольно выбранного гнома. В каждом цикле подаём команду "На первый-второй рассчитайсь! В две шеренги становись!". В циклах чётной длины первой шеренге командуем идти в первую группу, второй шеренге во вторую. В циклах нечётной длины один из гномов отрапортует: "Первый неполный!". Ему командуем идти в третью, остальным как в цикле чётной длины.
Шагом марш!

[provincialka]

Самое лучшее решение все-таки у azmt. С учетом того, что задача для 6-7 класса.
Но поговорить о циклах и их длинах, конечно, тоже не лишнее!

[TOTAL]

Евгений Машеров в сообщении #1075943 писал(а):

Я понимаю, что если перемещать гномов между граппами, что число обид может, и уменьшится. Лишь бы граппы хватило. Но из чего следует, что такое, уменьшающее число "обиженностей" перемещение между группами возможно?

Если я на кого-то обижен в своей группе, то перейду в одну из оставшихся групп (не в ту, где есть обиженный на меня)

[azmt]

(Оффтоп)

provincialka, просматривая решение некоторых олимпиадных задач порой удивляюсь как вообще школьник мог бы догадаться до такого. Это в то время когда вроде бы очевидное решение лежит на поверхности.

[TOTAL]

azmt в сообщении #1075936 писал(а):

Если окажется, что для данного гнома невозможно выбрать ни одну из групп, то это означает что на гнома обижены какие-то несколько элементов, что противоречит условию задачи.

Это не означает, что на гнома обижены какие-то несколько элементов.

[azmt]

Ну или он сам на кого-то обижен дважды.