Having a graph of complaints with 10% of enemies, prove that you always may arrest more enemies than honest people Not more than 10% of people of some country are enemies. Each man knows less than 500 other people. Each honest man tells to the dictator about one enemy he knows, and each enemy tells about a random man.

Prove that the dictator is able to arrest such a set of people that strictly more than 50% of them would be enemies.

The easy thing is to arrest exactly 50%. We know that the graph definitely has the cycle, and each cycle 50% consists of enemies. The graph consists of cycles and trees, that enters the cycles.

I've tried 2 strategies: to take 10% of people with the biggest amount of votes, and to take the smallest group with at least 10% of votes. None of this helps, but it seems that I need some compromise between these strategies, though I'm not sure about it.

UPD: There should be strict proof for any number of people in the country. But I guess the most important case is when there is very big amount of people.

UPD 2: If we know that every honest man tells about one enemy, we can deduce that every man knows at least one enemy.
The strategy is intricated, and it doesn't suffice to count how many times each person has been voted to be an enemy. 

First we fix some notations. 

Let $N$ be the number of people in the country $X$. The honest man can receive only fake votes
and so there are at most $N/10$ fake votes given. Let $F\subset X$ be the subset of people that receive at least one vote (fake or not).
We know that $f=\# F$ is at most $\frac{2N}{10}$, the sum of the fake votes and the number of enemies (who can receive "true" votes). 

The proposition P5 proves that the dictator can determine a set with (strictly) more enemies than honest man (Proposition P1 and P4 are needed to prove P5, but Propositions P2 and P3 are just for 
illustration). 

The number 500 is used under the assumption that "knowing someone" is symmetric and so each person can receive at most 500 votes (of all people that he knows). It is used in P2 and in 
P5.

${\bf P1:}$ If there is a subset $M$ of $m$ persons such that all the people in $M$ together receive $n$ votes from which at most $r$ are fake votes,
then one of the following holds (maybe the two are true):

1) there are more enemies than honest people in the set $M$, and the dictator is able to know it, or

2) there is a subset $M_1$ of $M$ with $\lfloor\frac m2 \rfloor$
people such that all the people together in $M_1$ receive at least $n-r$ votes and at most $r$ fake votes.

The same is true if we know that $M$ receives a set of $n$ votes from which at most $r$ are fake votes.

${\bf P2:}$ If $f\le N/10$, then the dictator has a strategy in order to determine a set with more enemies than honest man in it, by knowing only how many votes (fake or not) each person receives.

${\bf P3:}$ There is a distribution of votes in a country, such that for the dictator it is impossible to determine 
a set with more enemies than honest man in it, if he knows only the distribution of votes.

${\bf P4:}$ There exists a set $G$ of people (which can be known by the dictator), with $F\subset G\subset X$, such that the number of enemies in $G$ is greater than or equal to the number of honest man in $G$.

${\bf P5:}$ The dictator is able to determine a set with more enemies than honest man, by knowing how many votes of the set $X\setminus G$ each person receives.

${\bf Proof\ of\ P1:}$
Order the people in $M$ with increasing order of votes received: $x_1\le x_2\le \dots\le x_m$, where $x_i$ is the number of votes that the person $p_i$ receives.
If 
$$
\sum_{i=1}^{\lceil\frac m2 \rceil}x_i &gt;r,
$$
then there cannot be $\lceil\frac m2 \rceil$ honest man in $M$. Note that $\lceil\frac m2 \rceil=m/2$ if $m$ is even and $\lceil\frac m2 \rceil=(m+1)/2$ if $m$ is odd.
In this case the first alternative is true:  there are more enemies than honest people in the set $M$, and the dictator is able to know it.

Else
$$
\sum_{i=1}^{\lceil\frac m2 \rceil}x_i \le r,
$$
and then the complementary set $M_1=\{p_i\ |\ i&gt; \lceil\frac m2 \rceil\}$ has $\lfloor\frac m2 \rfloor$ elements and receives at least $n-r$ votes (and at most $r$ fake votes).
$$\tag*{$\Box$}$$

${\bf Proof\ of\ P2:}$
Set $F_0:=F$. Then $F_0$ receives $N$ votes, from which $N/10$ are fake votes. 

Hence, by P1, either $F_0$ has more enemies than honest man and the dictator knows it, or there is a subset $F_1$ with $f_1:=\lfloor \frac f2 \rfloor$ elements, which receives at least $N-N/10=9N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_1$ has more enemies than honest man and the dictator knows it, or there is a subset $F_2$ with $f_2:=\lfloor \frac {f_1}2 \rfloor$ elements, which receives at least $9N/10-N/10=8N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_2$ has more enemies than honest man and the dictator knows it, or there is a subset $F_3$ with $f_3:=\lfloor \frac {f_2}2 \rfloor$ elements, which receives at least $8N/10-N/10=7N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_3$ has more enemies than honest man and the dictator knows it, or there is a subset $F_4$ with $f_4:=\lfloor \frac {f_3}2 \rfloor$ elements, which receives at least $7N/10-N/10=6N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_4$ has more enemies than honest man and the dictator knows it, or there is a subset $F_5$ with $f_5:=\lfloor \frac {f_4}2 \rfloor$ elements, which receives at least $6N/10-N/10=5N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_5$ has more enemies than honest man and the dictator knows it, or there is a subset $F_6$ with $f_6:=\lfloor \frac {f_5}2 \rfloor$ elements, which receives at least $5N/10-N/10=4N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_6$ has more enemies than honest man and the dictator knows it, or there is a subset $F_7$ with $f_7:=\lfloor \frac {f_6}2 \rfloor$ elements, which receives at least $4N/10-N/10=3N/10$ votes, from which at most $N/10$ are fake votes.

By P1, either $F_7$ has more enemies than honest man and the dictator knows it, or there is a subset $F_8$ with $f_8:=\lfloor \frac {f_7}2 \rfloor$ elements, which receives at least $3N/10-N/10=2N/10$ votes. 

But $f_8\le f/2^8\le N/2560$ and $F_8$ receives $2N/10$ votes, so each person in $F_8$ receives on average $\frac{N/5}{N/2560}=512$ votes, which is impossible (HERE WE USE THE "KNOWS AT MOST 500 PEOPLE" ASSUMPTION). So, for some 
$i=0,\dots,7$, the set $F_i$ has more enemies than honest people and the dictator is able know it.
$$\tag*{$\Box$}$$
${\bf Proof\ of\ P3:}$

Assume that your country has $N=2560n$ people for some positive integer $n$. The distribution is the following:

128n people receive exactly one vote, 

64n people receive exactly 2 votes, 

32n people receive exactly 4 votes, 

16n people receive exactly 8 votes, 

8n people receive exactly 16 votes, 

4n people receive exactly 32 votes, 

2n people receive exactly 64 votes, 

n people receive exactly 128 votes, 

and n people receive exactly 256 votes.

It is left to the reader to prove that for every set $A\subset X$ there is a subset $B$ of $A$ with $\# B\ge \# A/2 $ such that all people in $B$ have together at most 256n votes. These votes could be all fake votes, so there is no way to determine with 100% certainty a subset with more enemies than honest man.
$$\tag*{$\Box$}$$

${\bf Proof\ of\ P4:}$

Consider the oriented graph, where the people are the vertices and the votes are the oriented edges.

We construct $G$ inductively:

First we take $G$ to be the set of vertices of cycles. Then take the largest path that is not in $G$ (all paths eventually end in a cycle). 
If the path has an even number of vertices not in $G$, include all the vertices in $G$. If it has an odd number of vertices not in $G$,
then include all but the first vertex in $G$. 

Clearly in each oriented path with an even number of vertices, there are at least the same number of enemies than honest people.
So, by construction, $G$ has at least the same number of enemies than honest man. Moreover, any voted man has a path that leads to a cycle (and he is not the first vertex of that path), so eventually he will be included in $G$. Hence $F\subset G$, as desired.
$$\tag*{$\Box$}$$

${\bf Proof\ of\ P5:}$
Finally we prove P5. We can assume that the number of people in $G$ is even: if there is an odd cycle this renders a set with more enemies than honest people and at each inductive step we add an even number of people to $G$.

So let $\#G=2p\le N/5$. Then $G_0:=G$ receives $N-2p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes. Clearly P1 still holds if we consider only votes in $X\setminus G$,
 so either $G_0$ has more enemies than honest man and the dictator knows it, or there is a subset $G_1$ with $g_1:=p$ elements, which receives at least 
$N-2p-(N/10-p)=9N/10-p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

Again by P1, either $G_1$ has more enemies than honest man and the dictator knows it, or there is a subset $G_2$ with $g_2:=\lfloor\frac p2\rfloor$ elements, which receives at least 
$9N/10-p-(N/10-p)=8N/10$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_2$ has more enemies than honest man and the dictator knows it, or there is a subset $G_3$ with $g_3:=\lfloor\frac {g_2}2\rfloor$ elements, which receives at least 
$8N/10-(N/10-p)=7N/10+p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_3$ has more enemies than honest man and the dictator knows it, or there is a subset $G_4$ with $g_4:=\lfloor\frac {g_3}2\rfloor$ elements, which receives at least 
$7N/10+p-(N/10-p)=6N/10+2p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_4$ has more enemies than honest man and the dictator knows it, or there is a subset $G_5$ with $g_5:=\lfloor\frac {g_4}2\rfloor$ elements, which receives at least 
$6N/10+2p-(N/10-p)=5N/10+3p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_5$ has more enemies than honest man and the dictator knows it, or there is a subset $G_6$ with $g_6:=\lfloor\frac {g_5}2\rfloor$ elements, which receives at least 
$5N/10+3p-(N/10-p)=4N/10+4p$ votes (from $X\setminus G$), from which at most $N/10-p$ are fake votes.

By P1, either $G_6$ has more enemies than honest man and the dictator knows it, or there is a subset $G_7$ with $g_7:=\lfloor\frac {g_6}2\rfloor$ elements, which receives at least 
$4N/10+4p-(N/10-p)=3N/10+5p$ votes (from $X\setminus G$).

But $g_7\le p/2^6$ and $G_7$ receives $3N/10+5p$ votes, so each person in $G_7$ receives on average at least $\frac{3N/10+5p}{p/2^6}=\frac{192}{10}\frac {N}{p}+320\ge 512$ votes, since $\frac{N}{p}\ge 10$. This is
impossible (HERE WE USE THE "KNOWS AT MOST 500 PEOPLE" ASSUMPTION), so for some 
$i=0,\dots,6$ the set $G_i$ has more enemies than honest people and the dictator is able to know it.
$$\tag*{$\Box$}$$

${\bf FINAL\ NOTES:}$

The proof of P5 is valid even if the bound of the number each person knows is increased from 500 to 4096; in that case people in $G_{10}$ would have on average 4096 votes.

If the bound is 250 instead of 500, or if only 9% (or less) of the people are enemies, then the distribution of votes is sufficient to determine the required set.

If $N$ is small, then at some moment $g_i=1$, and it will be necessarily an enemy.

In order to avoid the trivial solution "The dictator is honest and so he knows an enemy" we should require that the condition is true for all people but the dictator. This would be consistent with changing the dictator for some computer (which is also useful in order to process all the denouncing data).

Allowing the dictator to be an enemy would turn the situation less realistic.
I've made an assumption, that the number of people $N$ is way much higher than $500$.

Then I've considered the worst case, where every man knows $500$ other people.

In this case honest man have probability of not being shown as an enemy averagely $$p_h=1^{450}.998^{50}\approx .9047$$

Analogical probability for enemies is averagely $$p_h=.98^{450}.998^{50}\approx .0001$$

Thus we can compute the probabilities of being picked:
$$P_h=1-p_h\approx .0953 \\ P_e = 1-p_e\approx .9999$$

Now if we put all picked people to the jail, there will be $$K_e=P_e\cdot.1\cdot N\approx.09999\cdot N$$ enemies and $$K_h=P_h\cdot.9\cdot N\approx.08573 \cdot N$$ honest people. 

Thus there are more enemies than honest people in jail.

Edit

I also want to refer to your 'non-cycle' strategies (to long for a comment):

Consider case, where:


30 enemies voted for one honest man and this man voted against one of this enemies
in 26 groups 19 honest men voted against one enemy
in one group 18 honest men voted against one enemy
all enemies from these 27 groups voted against one man from one of these groups.


So we have then:


Population of 570 people with 57 enemies and 30 voted men
2 honest men voted by 30 and 27 votes
26 enemies voted by 19 men each 
1 enemy voted by 18 men
1 enemy voted by 1 man


Picking 10% with the highest ammount of votes will cause picking 2 honest men and 1 enemy - there are no more enemies than honest people in this group

Picking the smallest group with at least 10% may be problematic - this approach cause selection of 2 honest men and no enemy.