Гномы

[mr.tumkan2015]

В один прекрасный день каждый из 2015 гномов обиделся на какого-то другого гнома (одного), и на каждого гнома обиделся какой-то другой гном (один). Белоснежке требуется распределить гномов на три группы так, чтобы в каждой из групп не было гномов,
обиженных на кого-нибудь из данной группы. Всегда ли это возможно? Ответ обоснуйте.

Ясно, что если бы 2015 бы делилось на три, разделили бы на три равные группы, а тут как?

[AlexDem]

А зачем делимость на три? Раз у этих гномов такая сугубо адресная обида, то это неспроста. И потом, пусть 4 гнома обиделись так: $1 \to 2 \to 3 \to 4 \to 1$, тогда просто помещаем $1$ и $3$ в одну группу, а остальных - в другие, да и всё.

[Sicker]

mr.tumkan2015 в сообщении #1075667 писал(а):

Ясно, что если бы 2015 бы делилось на три, разделили бы на три равные группы

Почему?

[iancaple]

Sicker в сообщении #1075676 писал(а):

mr.tumkan2015 в сообщении #1075667 писал(а):

Ясно, что если бы 2015 бы делилось на три, разделили бы на три равные группы

Почему?

Чтоб в карантин не попасть
mr.tumkan2015, разложите перестановку в произведение независимых циклов. Каждый цикл посмотрите, четной или нечетной длины.

[mr.tumkan2015]

Спасибо, может вот так?

$1 \to 2 \to 3 \to 4 \to ...\to 2015\to 1$

Первая группа $1,3,5,...,2013$

Вторая группа $2,6,10, ....,2010, 2015$

Третья группа $4,8,12,....,2008,2012,2014$

Можно так?

-- 22.11.2015, 16:28 --

iancaple в сообщении #1075696 писал(а):

mr.tumkan2015, разложите перестановку в произведение независимых циклов. Каждый цикл посмотрите, четной или нечетной длины.

Пока что не понимаю -- что значит независимый цикл.

[arseniiv]

mr.tumkan2015 в сообщении #1075705 писал(а):

Можно так?

Нельзя, потому что обидеться гномы могут по-разному. Покажите, что «граф обиженности» (есть дуга $a\to b$, если $a$ обижен на $b$) будет состоять из непересекающихся простых циклов. Это другими словами предлагаемое iancaple разложение перестановки, которая получится, если каждого гнома заменить тем, на которого он обижен.

[mr.tumkan2015]

Может тогда рассмотрим тогда разбиение по модулю $3$. Пусть $1\to 2\to 3\to 1$ (простой цикл из остатков). Второй цикл $4\to 5\to 6\to 4$,

$n$-ый цикл $3n-2\to 3n-1\to 3n\to 3n-2$. Тогда нужные три группы будут образовывать классы вычетов по модулю три. Правильно ли понял идею?

[AlexDem]

У Вас в задаче был другой вопрос - не можно ли так, а всегда ли можно. И, если честно, я идею с циклами не понял. Вот есть такая обиженность: $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 8 \to 1$. Цикл один. Но легко делим на группы: $(1, 3, 5, 7)$, $(2, 4, 6)$ и $(8)$.

[arseniiv]

(mr.tumkan2015 не подглядывать.)

AlexDem в сообщении #1075708 писал(а):

И, если честно, я идею с циклами не понял.

Просто общее разбиение можно получить, комбинируя разбиения каждого цикла. Точнее, не разбиения, т. к. цикл из двух элементов нельзя разбить на три, но идея ясна. Хотя, зачем нужно разделение по чётности. я тоже не понял (а вот по модулю 3…).

[iancaple]

Гномов, принадлежащих циклу нечетной длины (больше 1), нельзя разделить на 2 группы. Но на три легко. И как показал AlexDem еще во 2-м посте, гномов, принадлежащих циклу четной длины, можно разделить на две группы.Но в предыдущем (не будем говорить последнем) своем посте он почему-то делит их на три группы. Кто-то запрещал пустые группы?

[AlexDem]

Это было сделано с определённой целью - чтобы ТС-а навести на доказательство. Потому что не может же он в ответе записать: "это сделать легко" (a.k.a "очевидно"). Возможно, я правку внёс неудачно: сперва у меня было 9 обиженных, а я оставил 8. Нужно было лучше вторую группу поправить.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Олимпиадные задачи (М)»
Причина переноса: задача с ранее проводившейся олимпиады для учащихся 6-7 классов.

Поскольку ТС прилично старше и уже на первом курсе, то в случае его пассивного участия тема будет перенаправлена в Карантин.

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

По-моему, в этой задаче трудность одна - понять, что значение 2015 совершенно ни при чём...

[TOTAL]

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

[azmt]

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