На заседании Украинской Рады каждый парламентер дал пощечину ровно одному своему коллеге. Докажите, что парламент можно теперь разбить на 3 фракции, члены которой друг другу пощечин не давали.
Берём троих произвольных депутатов: D1, D2, D3. Выбираем первого из оставшихся p-3, депутатов. Назовём его D4. Если он получил одну пощёчину и дал одну, тогда с одним из этих депутатов он точно может образовать фракцию. Если же он получил пощёчину от двух или трёх из них, тогда хотя бы двое из них не конфликтовали между собой, так как количество пощёчин константно и конечно. Пусть это будут D1 и D3. Тогда D1 - переводим в группу D3 и создаём группу D4. Выходит, групп опять всего три. Берём депутата D5. D2 конфликтовал с D3(получил), и c D4(ударил). D4 получил от D2 и D1. D3 ударил D2. Получается, кого бы D5 не ударил, для него всегда найдётся группа(в данном случае - две), в которую он может войти. Данная логика применима и для остальных депутатов. Каждый из них либо может войти в группу, либо может образовать собственную, а остальных можно перераспределить.
Уважаемый админ, возможно я не совсем пониял условие... Допустим, все депутаты дали пощёчину одному. Тогда фракций, соответствующих условию задачи будет всего две - 1) - тот один, которому все дали пощёчину (он может называться фракцией?) и 2) - все остальные. Их, остальных, конечно можно разбить на 2 группы и будет три фракции. Это корректно? Если да, то получается , что достаточно иметь 2 фракции "друзей", одна из которых больше 2-х человек. Так я понимаю?
Админ: да, всё так. Докажите, что при любом раскладе это выполнимо.
Оптимизируем решение. Выбираем из дерущегося стада драчунов, которым больше всех досталось. Самый избитый (избитые) драчун (ДР1) имеет много много Врагов (ВВ1), которые дали ему пощечину, и одного Врага (В1), который получил пощечину от ДР1. Самый удачивый (удачливые) драчун (ДРк)не получил пощечин и имеет одного врага (Вк), кому дал пощечину. Начинаем с самого большого дрвчуна, 3 фракции: Др1 ВВ1 В1. Каждому человеку из групп ВВ1 и В1 будет соответсвовать разбивка драчунов по Др. Аккуратненько делим людей на 3 группы.
ЗЫ. В некоторых разбивках будет только 2 группы, в том случае, если удары были взаимными.
Админ: в последнем случае также ничто не мешает разбить одну из групп пополам, поэтому доказательство исчерпавающе
не представился 2011-04-17 16:49:07 пишет:
те кто не получил вообще, те кто получил одну и кто получил две и более.
Построим нерадивых депутатов в линеечку, заставим рассчитаться по порядку и начнем экзекуцию:
1-ый парень станет основой для группы номер раз. Дальше люди могут либо быть в контрах с первым, либо нет. В зависимости от этого определяем их либо в группу номер раз, либо создаем группу номер два. С этого момента каждый следующий распределяемый ищет группу, в которой с ним никто не дрался и если не находит - создает группу 3. С этого момента у нас есть 3 группы, в каждой из которых соратники, друг с другом не воевавшие (мин. кол-во распределенных к этому этапу людей 3, макс. - не ограничено). Теперь осталось доказать, что оставшихся можно будет раскидать по этим группам так, чтобы условие неконфликности выполнялось. Берем n-ного индивидуума. У него есть проблемы с 2 людьми (или даже с 1),- с тем, кому он дал по мордасам, и с тем от кого получил. Эти 2 человека могут быть в одной группе или в двух, но в трех они оказаться не могут, а занчит мы нашли куда пристроить этого индивидуума.
Админ: "У него есть проблемы с 2 людьми (или даже с 1),- с тем, кому он дал по мордасам, и с тем от кого получил" - он мог получить от нескольких человек
azon 2011-04-12 22:38:11 пишет:
можно разделить на 3 фракции-например те,кто дал 1 пощечину и получил 1,те кто дал пощечину и не получил и те кто дал и получил 2
У одного человека может быть до 2-х врагов. Первый враг-тот кто дал пощечину, второй-тот кому дал пощечину. т.о. если этих трех человек мы рассадим в разныые фракции, кол-во врагов в парламенте уменьшится. Поскольку рада состоит из конечного числа человек, то организуя этот процесс, мы рано или позно придем к его завершению.
Админ: близко.. докажите, что не зайдете таким образом в тупик, когда человека невозможно будет пристроить ни в одну фракцию.
Reds on tour 2011-04-05 16:01:22 пишет:
Ну тогда три фракции по одному человеку. Внутри фракций никто никому не надавал :-)
Reds on tour 2011-04-05 11:17:06 пишет:
фракция не может состоять из одного человека - это противоречит условиям: "фракции, члены которой друг другу пощечин не давали"
Админ: а что, разве условие нарушается? :)
Reds on tour 2011-04-04 22:44:36 пишет:
Как насчет варианта, если все (кроме одного) парламентарии отвесили пощечину одному единственному (последнему) парламентарию? В этом случае он не сможет войти ни в одну фракцию.
Админ: Ну почему же. Просто его фракция будет состоять из одного человека.
Imhok 2011-04-02 01:46:22 пишет:
на тех кто давал пощечину, кто не давал, но получил, и кто не давал и не получил
Админ: Так не пойдет. Каждый дал ровно одну пощечину своему коллеге.
количество кратно 3-м. возьмем троих, каждый дал пощечину каждому. варианты: 12,23,31 или 13,32,21. получилось 3 фракции, по человеку в каждой
Админ: каждый дает только одну пощечину. Двое могли отвесить пощечину одному и тому же парламентеру. Фракции могут быть неодинаковые по количеству. В Раде заседают много парламентеров.