Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

82. Враги народа

Не более 10% жителей некоторой страны — враги народа. Известно, что у каждого гражданина этой страны менее 500 знакомых. На день рождения президента каждый гражданин страны сделал ему подарок: написал в Департамент Госбезопасности письмо с разоблачением одного из знакомых ему врагов народа. При этом известно, что честные граждане разоблачали только истинных врагов, а враги могли как разоблачить других врагов, так и оклеветать честных граждан.

Необходимо доказать, что на основании полученных данных ДГБ может посадить некоторое количество граждан так, чтобы больше половины посаженных были врагами народа.
© Математический турнир старшеклассников «Кубок памяти А.Н. Колмогорова» (2004)
2008-08-28

Обсуждение


Задачи :: Про врагов народа
↓↓ 0 ↑↑   Zero (38 / 335)   29 авг 2008 17:10   »»


Получается, условием молчаливо предполагается, что:
1) у каждого честного гражданина среди его 500 знакомых есть по крайней мере один враг народа
2) каждому гражданину известно, какой из его знакомых честный, а какой - враг
?
↓↓ 0 ↑↑   eruditor (133 / 441)   19 мар 2008 12:47   «« #2 »»   Ответить


С первым условием согласен. Со вторым нет, оно не вытекает из формулировки задачи. Честный гр-н в принципе может знать только часть врагов из всех врагов среди его знакомых, и указывать, по условию задачи, только на ОДНОГО из знакомых врагов. Теоретически возможна ситуация, что один враг — общий знакомый всех честных и он известен им как враг. И все честные могут донести только на этого одного врага. Условиям задачи не противоречим. Все нечестные(10%) могут донести на только различных честных, честных на это хватит (90%), как на врагов; врать, так врать. В результате будут посажены 10% населения — все честные и один! враг!
По-моему этот вариант не противоречит условию задачи. Хотя, конечно, мрачновато.
Вопрос в правилах игры дкб. Вот варианты:
1. вариант: Сажаем по факту каждого доноса. — Тогда может получиться выше указанный вариант.
2. вариант(пример): Сажаем, только если на человека — как на врага народа указали >10% населения.
Тогда если кого и посадят, то только врагов.
Но нужно исходное сакральное знание, что врагов не более 10%.
↓↓ 0 ↑↑   dervish09 (0 / 1)   30 авг 2013 05:48   «« #11 »»   Ответить


Если 90% населения указывает на одного гражданина, то он гарантированно враг народа. Его и сажаем, и больше никого. Задача решена!
↓↓ 0 ↑↑   Денис (25 / 13)   30 янв 2017 16:36   «« #13 »»   Ответить


1) да, только знакомых у каждого <500
2) да
↓↓ 0 ↑↑   Zero (38 / 335)   19 мар 2008 18:29   «« #3 »»   Ответить


Вариант
Все доносы можно рассматривать как ориентированый граф, где узлы это граждане, а доносы это ребра.
В таком графе обязательно будет цикл (без доказательства). А в этом цикле не менее половины узлов - это враги. Т.к. честные граждане, находящиеся в цикле, обязательно укажут на врагов, кроме того некоторые враги так же могут указывать на врагов. Поэтому врагов в цикле не меньше чем граждан.
Так вот ДГБ просто посядит всех гражден попавших в этот цикл. Ну и конечно все другие цикл тоже следует посадить.
Правда, не понимаю при чем здесь 10% и 500 знакомых. Решение верно и без этих дополнений.
↓↓ 0 ↑↑   zimin2000 (0 / 4)   01 окт 2008 09:25   «« #4 »»   Ответить


Осталось доказать существование цикла при любом раскладе :-)
↓↓ 0 ↑↑   eruditor (133 / 441)   01 окт 2008 14:54   «« #5 »»   Ответить


Доказательство
Это не сложно. Предположим, что в стране проживает N человек, тогда возьмем какого-либо жителя и сделаем следующую процедуру N+1 раз. Пройдем по "указателям" на врагов народа. Т.е. если житель указал на кого-то как на врага народа, то продолжим процедуру с этого врага. Данный процесс на может прерваться, т.к. каждый житель обязательно указывает на кого-нибудь как на врага. Одного он может зачиклиться и обязательно это сделает. т.к. по меньшей мере 1 житель будет пройден дважды. Это означает что данный житель находится на этом самом цикле. Т.е. цикл существует.
↓↓ 0 ↑↑   zimin2000 (0 / 4)   13 окт 2008 18:17   «« #6 »»   Ответить


Ага...
Наконец понял, что меня беспокоило в вашем решении. В условии требуется посадить группу, в которой врагов строго больше половины. У вас же нестрогое неравенство. Для устранения этой неприятности, видимо, как раз и нужны 10% и 500.
↓↓ 0 ↑↑   eruditor (133 / 441)   14 окт 2008 18:36   «« #7 »»   Ответить


Куда мы катимся
Морозовых воспитываете среди одаренных
↓↓ 0 ↑↑   Jayq (0 / 4)   01 дек 2008 19:58   «« #8 »»   Ответить


нифига
все враги указывают на 2х честных
а все честные на одного врага(ну вот такой он известный)
и всё.аналогично 4/1,5/2,6/2,7/3враги могут указывать и на врага коего выбрали честные
↓↓ 0 ↑↑   дум (0 / 6)   23 дек 2008 22:30   «« #9 »»   Ответить


"чтобы больше половины посаженных были врагами народа." садите всех на кого указали, максимум 10% посаженых будет честными.
Тупая задача!!!!
↓↓ −10 ↑↑   Ярослав (-14 / 4)   03 июл 2013 16:45   «« #10 »»   Ответить


Посадить тех у кого<10%
а на остальных насрать
↓↓ −9 ↑↑   виктор (-14 / 3)   08 ноя 2013 12:02   «« #12 »»   Ответить


Если диктатор является честным, то он должен посадить того врага, которого он знает.
↓↓ 0 ↑↑   Dimitrius (0 / 1)   19 июл 2017 15:58   «« #14   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы