Estoy tratando de resolver el siguiente problema :
En un grupo de $3n$ de personas que cada miembro sabe exactamente tres idiomas de cinco dada idiomas. Demostrar que siempre es posible dividir el grupo en tres grupos de n personas de tal manera que en cada grupo todo el mundo sabe que al menos uno de los idiomas de los cinco dados . He intentado utilizar el principio del palomar, pero que no llevan a ninguna parte . Una pequeña pista sería de una gran ayuda.
Parece que el siguiente.
Por inducción podemos llegar a ser más fuerte
La reclamación. Siempre es posible dividir el grupo en tres grupos $A, B,C$ $n$ de las personas de tal manera que no existe tres diferentes idiomas $a$, $b$, y $c$ de manera tal que en el grupo $A$ todo el mundo sabe que el lenguaje de $a$, en el grupo $B$ todo el mundo sabe que el lenguaje de $b$, y en el grupo $C$ todo el mundo sabe que el lenguaje de $c$.
La base de la inducción es trivial. Supongamos que ya hemos demostrado Reclamación por $n\ge 1$. Los siguientes casos son posibles.
1) No existe un subgrupo de las tres personas que en común saber todos los 5 idiomas que no existen dos personas del subgrupo conocer las mismas tres idiomas. En este caso, por la suposición inductiva podemos dividir el resto $3n$ de las personas en tres grupos satisfacción de Reclamación por $n$. Una breve revisión muestra que en este caso siempre podemos añadir exactamente una de las personas del subgrupo para cada uno de los grupos para satisfacer la Demanda de $n+1$.
Si el Caso 1 no tiene uno de los siguientes casos celebrar
2) Cada uno de los cinco dados idiomas es conocido por alguna persona del grupo, sino que para cada uno de los subgrupos de tres personas que en común saber todos los 5 idiomas hay dos personas del subgrupo que saber tres idiomas. En este caso no hay dos personas a las que en común saber exactamente 4 idiomas, porque si añadimos a ellos la persona que sabe el quinto idioma, a continuación, obtenemos un subgrupo de satisfacer la condición de Caso 1. Supongamos que una persona sabe idiomas 1, 2, 3. Cualquier otra persona puede conocer uno de los siguientes idiomas: $\{1,2,3\}$, $\{1,4,5\}$, $\{2,4,5\}$, y $\{3,4,5\}$. Por otra parte, no hay dos personas pueden conocer diferentes conjuntos de idiomas de los últimos tres juegos. Así que en este caso tenemos un $k$ personas que conocen los idiomas $\{1,2,3\}$ $3n+3-k$ personas que conocen los idiomas $\{a,4,5\}$ algunos $a\in\{1,2,3\}$. Para cada valor de $k$ es fácil obtener la partición del grupo de la satisfacción de la Reclamación (si $k<n+1$, a continuación, los idiomas son el $a$, 4, y 5; si $n+1\le k<2n+2$, a continuación, los idiomas son el $a$, 4, y $b\in \{1,2,3\}\setminus\{a\}$; si $k\ge 2n+2$, a continuación, los idiomas son el 1, 2 y 3).
Si los Casos 1 y 2 no se sostienen, entonces tenemos el Caso 3 Caso 4 Caso o 5.
3) Todas las personas del grupo de $3n+3$ personas conocéis en común exactamente 4 idiomas y existe un subgrupo de tres personas que no hay dos personas del subgrupo conocer las mismas tres idiomas. En este caso, por la suposición inductiva podemos dividir el resto $3n$ en tres grupos satisfacción de Reclamación por $n$. Una breve revisión muestra que en este caso siempre podemos añadir exactamente una de las personas del subgrupo para cada uno de los grupos para satisfacer la Demanda.
4) Todas las personas del grupo de $3n+3$ personas conocéis en común exactamente 4 idiomas y para cualquiera de las tres personas del grupo dos de ellos conocen a los mismos tres idiomas. En este caso obtenemos una partición de la satisfacción de Demanda de manera similar al Caso 2, pero aún más simple.
5) Todas las personas del grupo de $3n+3$ personas conocéis en común exactamente 3 idiomas. En este caso la partición necesaria es trivial.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
