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

Получается, условием молчаливо предполагается, что:
1) у каждого честного гражданина среди его 500 знакомых есть по крайней мере один враг народа
2) каждому гражданину известно, какой из его знакомых честный, а какой - враг
?

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

Если 90% населения указывает на одного гражданина, то он гарантированно враг народа. Его и сажаем, и больше никого. Задача решена!

1) да, только знакомых у каждого <500
2) да

Вариант
Все доносы можно рассматривать как ориентированый граф, где узлы это граждане, а доносы это ребра.
В таком графе обязательно будет цикл (без доказательства). А в этом цикле не менее половины узлов - это враги. Т.к. честные граждане, находящиеся в цикле, обязательно укажут на врагов, кроме того некоторые враги так же могут указывать на врагов. Поэтому врагов в цикле не меньше чем граждан.
Так вот ДГБ просто посядит всех гражден попавших в этот цикл. Ну и конечно все другие цикл тоже следует посадить.
Правда, не понимаю при чем здесь 10% и 500 знакомых. Решение верно и без этих дополнений.

Осталось доказать существование цикла при любом раскладе :-)

Доказательство
Это не сложно. Предположим, что в стране проживает N человек, тогда возьмем какого-либо жителя и сделаем следующую процедуру N+1 раз. Пройдем по "указателям" на врагов народа. Т.е. если житель указал на кого-то как на врага народа, то продолжим процедуру с этого врага. Данный процесс на может прерваться, т.к. каждый житель обязательно указывает на кого-нибудь как на врага. Одного он может зачиклиться и обязательно это сделает. т.к. по меньшей мере 1 житель будет пройден дважды. Это означает что данный житель находится на этом самом цикле. Т.е. цикл существует.

Ага...
Наконец понял, что меня беспокоило в вашем решении. В условии требуется посадить группу, в которой врагов строго больше половины. У вас же нестрогое неравенство. Для устранения этой неприятности, видимо, как раз и нужны 10% и 500.

Куда мы катимся
Морозовых воспитываете среди одаренных

нифига
все враги указывают на 2х честных
а все честные на одного врага(ну вот такой он известный)
и всё.аналогично 4/1,5/2,6/2,7/3враги могут указывать и на врага коего выбрали честные

Посадить тех у кого<10%
а на остальных насрать

Если диктатор является честным, то он должен посадить того врага, которого он знает.

Я бы рассортировал всех граждан по числу доносов. Посадил бы первую верхушку, но не более 10%. И не сажал бы тех, на кого доносов меньше 50. Потом повторил бы процедуру с доносами, зная, что процент врагов изменился.