Una sociedad tiene que elegir una junta de gobernadores.

Question

Una sociedad tiene que elegir una junta de gobernadores. Cada uno de los miembros de la sociedad ha optado $10$ candidatos para la junta, pero él va a ser feliz si al menos uno de ellos será en la junta. Para cada uno de los seis miembros de la sociedad, existe una junta compuesta de dos personas haciendo todos estos seis miembros feliz. Demostrar que una junta compuesta de $10$ de las personas puede ser elegido para hacer de cada miembro de la sociedad feliz.

Comentario: me podría encontrar fácilmente una junta de $20$ gobernadores. Supongamos que la afirmación no se sostiene. Tomar cualquier conjunto $ \mathcal{G} =\{G_1,G_2,...G_{10}\}$ que hace feliz miembro de la $M_1$. Dado que la reclamación no se sostiene allí debe ser un miembro de la $M_2$ que es infeliz con la junta, pero no es de la junta de $\mathcal{G'} =\{G'_1,G'_2,...G'_{10}\}$ que no lo hace feliz. No es difícil ver que, a causa de la segunda hipótesis, que en la junta de $ \mathcal{G} \cup \mathcal{G'}$ hace que el conjunto de la sociedad feliz.

Eso es todo. Yo no puede ir más allá.

Answer 1

Deje $A = [a_1,a_2...a_{10}]$ el conjunto de personas que de $P_A$ feliz. A continuación, asumir que existe $P_B$ (con $B = [b_1,b_2...b_{10}])$ que no es feliz con $A$ como la junta directiva y, a continuación, como se ha mostrado $A\cup B$ hace felices a todos.

A continuación, supongamos $A\cup B$ es el tamaño mínimo de la junta de st todo el mundo es feliz. Por lo tanto, no existe $C$ st $C \cap (A\cup B) = a_1$ ya que de lo contrario $a_1$ podría ser eliminado y todo el mundo todavía sería feliz con la junta. Por lógica similar existe $D$ st $D \cap (A\cup B) = a_2$. Sin embargo, si ponemos $A,B,C$ $D$ en un grupo de $6$ no hay una junta de $2$ que hace que todos contentos. Por lo tanto, podemos eliminar cualquiera de las $a_1$ o $a_2$ y todo el mundo todavía sería feliz. Decir que hemos extraído $a_1$ existe $E$ st $E \cap (A\cup B) = a_3$ o $[a_1,a_3]$ y no existe $F$ st $F \cap (A\cup B) = a_4$ o $[a_1,a_4]$ así que por lo tanto nos puede quitar $a_3$ o $a_4$ (utilizando el mismo argumento de antes) o retire $a_3$ $a_4$ y poner $a_1$ nuevo, reducir el tamaño de la junta cualquiera que sea el caso.

Podemos continuar este proceso de eliminación de todos, pero uno de $[a_1,a_2...a_{10}]$ y todos, pero uno de $[b_1,b_2...b_{10}]$ dejando una junta de $2$. (Creo que todavía hay algunos problemas con este argumento). Por lo tanto, si hay $2$ personas cuyas decisiones no tienen a nadie en común una junta de $2$ es suficiente para hacer a todos felices, y si no, a continuación, $[a_1,a_2...a_{10}]$ hace felices a todos por lo que un consejo de $10$ de la gente es suficiente lo que sea.