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

[moonlight]

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

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

Не понятно каким образом можно перессорить 7 депутатов так чтобы каждый имел ровно трёх врагов. Это возможно только для чётного числа.

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

Допустим что есть 4 депутата таких что каждый каждому враг. Таким образом минимум необходимо 4 фракции. Для каждого следующего депутата всегда из 4-х фракций можно выбрать одну где у него врагов нет т.к. их там может быть не более трёх(может быть меньше, потом ещё добавятся, но уже записанные в какую-либо фракцию депутаты никуда более не перемещаются).
Так что достаточно 4-х фракций.

[монЯрхъ]

Мне понятны причины использования метода индукции автором, но не ясно почему за n он принимает 7. Почему не 1,2 или 3 - понятно, при таком коилчестве фракций неизбежно в одной из фракций будет как минимум 2 спорящих между собой. Но почему отвергает 4...
Перефразирую любимый персонаж: "Это неправильный автор, он делает не правильный мёд!" (рука не поднялась искаверкать фразу целиком).

[Димыч]

Да вы на стрелки посмотрите на картинке. Отношение ссоры считается здесь несимметричным.

[moonlight]

То что ссоры могут быть несимметричными в условии не сказано. В таком случае проще было сказать что каждый депутат может иметь не менее 3 и не более 6 врагов.   

[Валерий]

 

Мне понятны причины использования метода индукции автором, но не ясно почему за n он принимает 7. Почему не 1,2 или 3 - понятно, при таком коилчестве фракций неизбежно в одной из фракций будет как минимум 2 спорящих между собой. Но почему отвергает 4...

Я задал себе вопрос: а если найдутся 5 паршивцев, когда каждый каждому враг, то 4 уже мало. А если 6 или 7.
 Видимо автор доказал, что максимально возможная система, когда каждый каждому враг состоит из 7 депутатов, тогда и 7 фракций хватает.

[Валерий]

На картинке не нарисованы стрелки спора №7 с №№2 и 3

[fortpost]

То что ссоры могут быть несимметричными в условии не сказано. В таком случае проще было сказать что каждый депутат может иметь не менее 3 и не более 6 врагов.  

Ваша правда, недоглядел.  Лучше, разумеется, "ссорящихся" заменить на "врагов". А то ссора автоматически воспринимается, как двунаправленная связь.