Согласие в думе

[fortpost]

Каждый депутат Думы поссорился ровно с тремя другими депутатами. Президент обязал спикера разбить депутатов на n фракций так, чтобы внутри одной фракции царило согласие. При каком наименьшем n это всегда возможно? (Это значит, что на n фракций депутатов можно было разбить всегда, а на (n — 1) фракцию — уже не всегда.)

[монЯрхъ]

Показать скрытый текст

не меньше 4-х?

[fortpost]

Показать скрытый текст

не меньше 4-х?

Маловато будет!

[Валерий]

Показать скрытый текст

6. Меньше не выходит

[монЯрхъ]

Показать скрытый текст

не меньше 4-х?

Маловато будет!

Доказательство: Показать скрытый текст

4 спорящих друг с другом депутата - будем считать их системой. Разделим на 3 фракции, при этом остается вероятность, что хотя бы в одной из фракций будет 2 спорящих депутата. Разделим на 4 фракции - и при распределении депутатов всегда будет фракция, в которой не будет спорящего депутата для разпределяемого.

[fortpost]

Показать скрытый текст

6. Меньше не выходит

Тоже мало!

[fortpost]

Показать скрытый текст

не меньше 4-х?

Маловато будет!

Доказательство: Показать скрытый текст

4 спорящих друг с другом депутата - будем считать их системой. Разделим на 3 фракции, при этом остается вероятность, что хотя бы в одной из фракций будет 2 спорящих депутата. Разделим на 4 фракции - и при распределении депутатов всегда будет фракция, в которой не будет спорящего депутата для разпределяемого.

Одолевают смутные сомнения... Как будто чтой-то в вашем доказательстве не так, но что именно... Чуть позже выдам авторское решение и сравним.

[Валерий]

Я правильно понимаю условие, что если №1 спорит с №2, то №2 не может спорить с №1? Или это вообще не важно.

[fortpost]

Я правильно понимаю условие, что если №1 спорит с №2, то №2 не может спорить с №1? Или это вообще не важно.

Наверное, неважно. Главное, чтобы №1 и №2 оказались в разных фракциях.

[Валерий]

Я правильно понимаю условие, что если №1 спорит с №2, то №2 не может спорить с №1? Или это вообще не важно.

Наверное, неважно. Главное, чтобы №1 и №2 оказались в разных фракциях.

Ну тогда монярх прав, т к число депутатов не задано.

[монЯрхъ]

Дело даже не в числе депутатов. Просто в условии не сказано, что те трое депутатов с кем спорить 4-й - спорят между собой. Поэтому процедура отбора такая.
 - берет депутата: помещаем его в Первую фракцию, тех троих с кем он спорит в Буфер.
 - и так пока депутаты не кончаться
 - потом рассматривает депутатов из Буфера, в нем, следовательно, любой депутат будет иметь одного спорящего в Первой фракции и еще двоих.
 - этого депутата помещаем во Вторую фракцию, его двоих спорящих во 2-ой буфер, и так всех
 - потом разбрасываем депутатов из 2-ого буфера между Третьей и Четвертой фракцией.

[fortpost]

Дело даже не в числе депутатов. Просто в условии не сказано, что те трое депутатов с кем спорить 4-й - спорят между собой. Поэтому процедура отбора такая.
 - берет депутата: помещаем его в Первую фракцию, тех троих с кем он спорит в Буфер.
 - и так пока депутаты не кончаться
 - потом рассматривает депутатов из Буфера, в нем, следовательно, любой депутат будет иметь одного спорящего в Первой фракции и еще двоих.
 - этого депутата помещаем во Вторую фракцию, его двоих спорящих во 2-ой буфер, и так всех
 - потом разбрасываем депутатов из 2-ого буфера между Третьей и Четвертой фракцией.

Вроде все логично. Но почему же авторский ответ не такой? Значит, выдам авторское решение, и посмотрим, в чем дело.

[пестерь]

Так, а число депутатов не обезательно должно быть равным во всех фракциях?

[fortpost]

Показать скрытый текст

Нетрудно построить пример, показывающий, что менее чем семью фракциями обойтись нельзя. Для этого можно нужным образом организовать ссоры между семью депутатами.

Докажем, что семи фракций всегда достаточно. Воспользуемся методом математической индукции. Пусть утверждение верно для n. Для n = 7 оно очевидно верно. Рассмотрим думу из n + 1 депутатов. Найдется депутат, с которым вступили в конфликт не более трех других депутатов (иначе число вовлеченных в ссоры депутатов окажется больше числа депутатов, которые сами затеяли ссору с коллегами). Выведем его временно из думы. Оставшихся n депутатов можно разбить на семь фракций по предположению индукции. В этой думе у указанного депутата не более 6 врагов, и его можно поместить в ту из семи фракций, где у него нет врагов.

[fortpost]

Так, а число депутатов не обезательно должно быть равным во всех фракциях?

Нет, конечно.