Tener un gráfico de quejas con el 10% de los enemigos, demostrar que siempre pueden detener a más enemigos que personas honestas

Question

No más de 10% de la población de algunos países son enemigos. Cada hombre sabe menos de 500 personas. Cada hombre honesto le dice al dictador sobre un enemigo que sabe, y cada enemigo habla de un azar del hombre.

Demostrar que el dictador es la detención de un conjunto de personas que estrictamente más del 50% de ellas sería la de los enemigos.

Lo fácil es a la detención exactamente el 50%. Sabemos que la gráfica tiene definitivamente el ciclo, y cada ciclo de 50% se compone de los enemigos. El gráfico consta de ciclos y de los árboles, que entra en los ciclos.

Yo he probado 2 estrategias: tomar 10% de las personas con la mayor cantidad de votos, y tomar el más pequeño grupo con al menos el 10% de los votos. Nada de esto ayuda, pero parece que necesito un poco de compromiso entre estas estrategias, aunque no estoy seguro de ello.

UPD: No debe ser estricta prueba para el número de personas en el país. Pero creo que el caso más importante es cuando hay muy gran cantidad de gente.

UPD 2: Si sabemos que cada hombre honesto habla de un enemigo, podemos deducir que cada hombre sabe al menos a un enemigo.

Answer 1

He hecho una suposición, que el número de personas $N$ es mucho mayor que $500$.

Entonces he pensado en el peor de los casos, donde cada hombre se conoce a $500$ otras personas.

En este caso hombre honesto tienen probabilidad de que no se muestra como un enemigo medianamente $$p_h=1^{450}.998^{50}\approx .9047$$

Analógico probabilidad de que los enemigos es medianamente $$p_h=.98^{450}.998^{50}\approx .0001$$

Por lo tanto, podemos calcular las probabilidades de ser elegido: $$P_h=1-p_h\approx .0953 \\ P_e = 1-p_e\approx .9999$$

Ahora si ponemos todos recogidos de la gente a la cárcel, no será $$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$$ la gente honesta.

Por lo tanto, hay más enemigos de los que la gente honesta en la cárcel.

Editar

También quiero hacer referencia a su "no-ciclo' las estrategias de largo para un comentario):

Considere el caso, cuando:

• 30 enemigos votado a favor de un hombre honesto y este hombre votó en contra de uno de los enemigos
• en 26 grupos de 19 hombres honestos votó en contra de un enemigo
• en un grupo de 18 hombres honestos votó en contra de un enemigo
• todos los enemigos de estos 27 grupos votaron en contra de un hombre de uno de estos grupos.

Así que tenemos a continuación:

• La población de 570 personas con 57 enemigos y 30 votado hombres
• 2 hombres honestos votado por 30 y 27 votos
• 26 enemigos votado por 19 hombres cada
• 1 enemigo votado por 18 hombres
• 1 enemigo votado por 1 hombre

Recogiendo el 10%, con la mayor cantidad de votos serán causa de picking 2 hombres honestos y 1 enemigo - no hay más enemigos de los que la gente honesta en este grupo

Escogiendo el más pequeño del grupo, con al menos el 10% puede ser problemático - este enfoque causar selección de 2 hombres honestos y no enemigo.

Answer 2

Detención de todo el mundo en cualquier ciclo dado (que tal y como usted siempre existen)

Cada hombre honesto dice al dictador cerca de un enemigo que conoce

Esto significa que en cualquier ciclo, no puede haber personas honestas consecutivos.

A su vez, esto significa que no puede ser más de la mitad de las personas honestas en el ciclo (el peor caso es una alternancia de enemigo honesto)