Having a graph of complaints with 10% of enemies, prove that you always may arrest more enemies than honest people

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 >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> \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.

My answer is partial, but it contains some ideas which may be useful.

I grew in Soviet Union, so the question looks natural for me. I even allowed myself to rename some its terms to feel the situation better. :-) Conversely to san’s answer, I have assumed that to know somebody is not the same as to be known by somebody, an example are celebrities. This interpretation makes the condition “each man knows less than 500 other people” useless, because given the denounce graph we can assume a posteriori that each man knows a man he denounced. But I hoped that in a solution process the meaning of a “magic number” will become more clear.

Indeed, I obtained a simple solution when the country is small. Assume that it consists of $N$ men among which at most $E$ are enemies. (To give a chance to The Great Leader I assumed that $E<N/2$, because otherwise given all denounce edges constitute a directed cycle, He cannot surely determine a set having more than a half of enemies. Also if $E>N/2$ then the enemies can unite and to throw down The Great Leader).

Let $d_1\ge\dots\ge d_N$ be a number of accusations against $i$-th man. If $d_1>E$ then the first man is an obvious enemy, so farther we’ll assume that $d_1\le E$. If $d_1+d_2+d_3>2E$ and there is at most one enemy among the first three men then the people who accused the remaining men are enemies, so there are at most $E$ of them. Since $d_1\ge d_2\ge d_3$ it implies that $d_2+d_3\le E$. Then $ d_1+d_2+d_3\le 2E$, a contradiction. So there is at least two enemies among first three men. So farther we’ll assume that $d_1+d_2+d_3\le 2E$. Continuing inductively, we obtain that for each $i$ with $2^i-1\le N$ either $d_1+\dots+d_{2^i-1}>iE$ and is this case among the first $2^i-1$ men are more then a half enemies or $d_1+\dots+d_{2^i-1}\le iE$. On the other hand, at most $2E$ men can be accused, so $d_1+\dots+d_{2E}=N$. So we obtain a contradiction provided $2E\le 2^i-1\le N$ but $iE<N$. In particular for $E=N/10$ we have $9E<N$ so if $2^9-1\ge N/5$ (that is if $N\le 2555$) then there exists such $i$ and The Great Leader can surely determine a set having more than a half of enemies.

Since a possibility to deal only with small countries is outrageous for true great leaders, I tried to drop the country size restriction. And I became to a suspicion that The Great Leader was disinformed (of course, by enemies) and His problem is not only enemies and hardly collaborating members, but even the system. I conjecture that for each $\varepsilon>0$ there exists $N$ and $E$ with $E/N<\varepsilon$ and a denounce graph for which The Great Leader cannot surely determine a set having more than a half of enemies.