Школьная задача по математике

[passenger]

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

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

[worm2]

Задачка олимпиадная. Вам бы поместить её в соответствующий раздел (http://dxdy.ru/viewforum.php?f=26). Только потом отсюда удалите, а то от модераторов замечание получите.

[Jnrty]

Jnrty:

Перенёс.

[passenger]

В терминах теории графов что-то пока не очень получается решить.

[Руст]

А вы уверены в справедливости условия. Мне кажется, что уже при условии не более 2 (вместе 7) этого нельзя сделать.

[maxal]

Эта задача эквивалентна отысканию точной верхней грани хроматического числа графов, у которых степень вершин ограничена числом 7.

С одной стороны, каждому ребру в таком графе можно придать произвольное направление и трактовать направленные ребра как "недолюбливание" одном вершиной-человеком другого.

С другой стороны, для заданной компании, представленной графом с вершинами-людьми и направленными ребрами-недолюбливаниями, мы можем "развоить" каждого человека так, что он сам будет только недолюбливать других и его копия в свою очередь будет только недолюбливаема. Тогда каждому разбиению исходного графа соответствует разбиение "удвоенного" такое, что обе копии одного человека попадают в одну и ту же часть разбиение. При этом, если в исходном разбиение не было ребер, соединяющих вершины, принадлежащие одной части, то и в "удвоенном" разбиении таких ребер не будет. А "удвоенный" граф можно трактовать как ненаправленный, и минимальное число частей в требуемом разбиении равно его хроматическому числу.

Добавлено спустя 9 минут 3 секунды:

Если 7 заменить на 3, то ответ дается в этой статье: A Note on the Oriented Chromatic Number of Graphs with Maximum Degree Three.
А вот обзор всяких связанных результатов: Oriented Graph Coloring.

В общем, эта задача совсем не школьная, и даже не олимпиадная, а исследовательская. Или я чего-то не понял.

[passenger]

Хм, скажем так, эта задача предлагается школьниками в заочном туре одной из олимпиад.
Не думаю, что жюри решило сыграть злую шутку
Может быть можно попробовать угадать n, при котором это возможно, а затем доказать, что при меньших n это условие не выполняется (приведя пример)?
Только непонятно, как это сделать.

P.S. В условии присутствует некоторая двусмысленность: количество людей в компании никак не связано с числом n, хотя это итак понятно.

[Someone]

Это задача с олимпиады "Покори Воробьёвы горы!". Поскольку срок отправки решений (25 января) уже истёк, задачу, видимо, можно обсуждать.

У меня есть только оценка снизу: $n\geqslant 15$.
Получается так. Расположим $15$ человек в вершинах правильного $15$-угольника. Предположим, что каждый из людей недолюбливает $7$ человек, следующих за ним против часовой стрелки. Тогда получается, что $7$ остальных недолюбливают его, так что для любой пары один из людей недолюбливает другого, поэтому при разбиении на группы в каждой группе не может быть больше одного человека.

[worm2]

Может быть, начать с 3-х недолюбливаний? maxal указал, что, вроде бы, ответ для этого случая - 11, но мне никак не удаётся построить пример, доказывающий недостаточность даже семи групп...

[maxal]

Тут есть такая тонкость. В статье о Oriented Chromatic Number они запрещают в направленных графах противоположно направленные дуги, а в этой задаче, если представлять ее направленным графом, такие дуги могут присутствовать (когда недолюбливание у двух каких-то человек взаимное). Но с другой стороны, если у нас есть такая пара дуг, то одну из них мы можем просто выкинуть, не нарушая ни условий задачи, ни возможной раскраски вершин, которая будет работать для обоих графов (исходного и с выкинутыми "лишними" дугами).

Другими словами, в исходной задаче можно ограничиться случаем, когда недолюбливание всегда одностороннее (если Петя недолюбливает Васю, то Вася не имеет права недолюбливать Петю).