На заседании Украинской Рады каждый парламентер дал пощечину ровно одному своему коллеге. Докажите, что парламент можно теперь разбить на 3 фракции, члены которой друг другу пощечин не давали.
Построим нерадивых депутатов в линеечку, заставим рассчитаться по порядку и начнем экзекуцию:
1-ый парень станет основой для группы номер раз. Дальше люди могут либо быть в контрах с первым, либо нет. В зависимости от этого определяем их либо в группу номер раз, либо создаем группу номер два. С этого момента каждый следующий распределяемый ищет группу, в которой с ним никто не дрался и если не находит - создает группу 3. С этого момента у нас есть 3 группы, в каждой из которых соратники, друг с другом не воевавшие (мин. кол-во распределенных к этому этапу людей 3, макс. - не ограничено). Теперь осталось доказать, что оставшихся можно будет раскидать по этим группам так, чтобы условие неконфликности выполнялось. Берем n-ного индивидуума. У него есть проблемы с 2 людьми (или даже с 1),- с тем, кому он дал по мордасам, и с тем от кого получил. Эти 2 человека могут быть в одной группе или в двух, но в трех они оказаться не могут, а занчит мы нашли куда пристроить этого индивидуума.
Админ: "У него есть проблемы с 2 людьми (или даже с 1),- с тем, кому он дал по мордасам, и с тем от кого получил" - он мог получить от нескольких человек
azon 2011-04-12 22:38:11 пишет:
можно разделить на 3 фракции-например те,кто дал 1 пощечину и получил 1,те кто дал пощечину и не получил и те кто дал и получил 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 фракции, по человеку в каждой
Админ: каждый дает только одну пощечину. Двое могли отвесить пощечину одному и тому же парламентеру. Фракции могут быть неодинаковые по количеству. В Раде заседают много парламентеров.