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

• Is this complete? You mention that each person knows fewer than $500$ others, but that is hard to interpret absent knowing how many people there are (if there are only $100$ people in total then the information is redundant, if there are $10^{9}$ people it is extremely important). Also...does the dictator know all the contacts? (i.e. given a person, does the dictator know whom that person knows?) – lulu Jul 19 '17 at 12:09
• Is the dictator honest? If so, he can ask himself and arrest the guy he fingers. – Henning Makholm Jul 19 '17 at 12:24
• If there is a cycle of odd length, you know there are more enemies than friends there, so you can arrest the whole cycle. – Arthur Jul 19 '17 at 12:28
• @ManuelLafond: Yes. For example, start by giving $n/100$ people one vote each, then give $n/200$ of them one vote more, and then $n/300$ of those one more vote, etc. The number of votes we spend is $\frac n{100}(1+\frac12+\frac13+\frac14+\cdots)$ and since this series diverges, we will eventually have spent $n$ votes, at least if $n$ is large enough to avoid rounding errors upsetting the result. So it's not enough to look at indegrees alone; we need to take into account how the graph fits together. – Henning Makholm Jul 20 '17 at 18:55
• I think the problem would be clearer if there were an explicit adversary. E.g., suppose there are $n$ people, honest except for $k$ enemies. The adversary selects whom each person points to, with the constraint that each honest person must point to an enemy. The dictator is given the digraph of pointing info as well as an upper bound $K \ge k$. For which pairs $(n,K)$ can the dictator guarantee a subset of more than half enemies for all $k \le K$? Note: the dictator doesn't know the ground-truth social network, so the adversary is free to choose it. Therefore it plays no role in the problem. – Jim Ferry Jul 27 '17 at 15:24

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,

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.

• Looks nice! But can you clarify why, in P5, $G$ receives $N - 2p$ votes? $G$ contains $F$, so shouldn't it receive all the votes? Or what do you mean by 'receive'? – Manuel Lafond Aug 1 '17 at 20:47
• Since $\# G=2p$, and we count only votes of $X\setminus G$, there are a total of $N-2p$ votes, which are the ones received by members of $F$ hence the same is true for $G$. – san Aug 1 '17 at 21:47
• Thanks, it's clearer with the edits. Nice answer. – Manuel Lafond Aug 1 '17 at 23:26

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.

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.

• That's in average. I think the question is actually (despite using words like "random") asking for a strategy whereby the dictator is guaranteed to reach is goal no matter how the populance conspire to point within the rules set out in the question. – Henning Makholm Jul 19 '17 at 14:12

Arrest everyone in any given cycle (which as you point out always exist)

Each honest man tells to the dictator about one enemy he knows

This means that in any cycle, there cannot be to consecutive honest persons.

In turn, this means that there can't be more than half honest persons in the cycle (the worse case being an alternance honest-ennemy)

• The question asks for a strategy that arrests strictly more than half criminals. – Manuel Lafond Jul 26 '17 at 11:23