Una conferencia utiliza $4$ principales lenguas. Demostrar que existe una lengua que al menos $\dfrac{3}{5}$ de los delegados saben.

Question

Una conferencia utiliza $4$ idiomas principales. Dos delegados cualquiera tienen siempre una lengua común que ambos conocen. Demuestre que existe un lenguaje que al menos $\dfrac{3}{5}$ de los delegados saben.

Fuente: Rumanía TST 2002

---

Mi intento:

Supongamos que tenemos $n$ personas y que $l_i$ la gente habla el idioma $L_i$ . Queremos demostrar que $l_i$ es al menos $3n/5$ para algunos $i\in\{1,2,3,4\}$ .

Digamos que no es cierto. Entonces tenemos $l_i<3n/5=:m$ para todos $i$ . Debido a la condición que tenemos $$ {n\choose 2} \leq \sum_{i=1}^4{l_i\choose 2} < 4\times {m\choose 2}$$ De aquí obtenemos $11n>35$ y no hay contradicción si $n>3$ .

---

Actualización (1. 20. 2019) : Ahora estoy tratando de desarrollar la idea que mencionó Servaes en el comentario.

Lema: Entre cualquier $4$ los delegados son $3$ que habla el mismo idioma.

Prueba: Si alguien habla sólo un idioma, estamos acabados. Digamos que hay alguien que habla exactamente 2 idiomas $L_1$ y $L_2$ . Luego por palomita de 3 hay dos en el mismo "hueco" y ya estamos otra vez.

Supongamos que todo el mundo habla al menos 3 idiomas. Entonces, por doble conteo entre lenguas y 4 personas tenemos $$4\cdot 3\leq 4\cdot l\implies l\geq 3$$ donde $l$ es la cardinalidad máxima de $L_i$ en este doble recuento y hemos terminado. $\square $

¿Alguna idea de cómo terminar ahora?

Answer 1

Si alguien habla una sola lengua, entonces todo el mundo habla esa lengua, y ya está. Si alguien habla las cuatro lenguas, entonces la afirmación deseada se deduce por inducción tras eliminar a esa persona de la conferencia. Entonces WLOG supone que todo el mundo habla dos o tres idiomas.

Poner las cuatro lenguas en los vértices de un tetraedro. Si alguien habla dos lenguas, colócalo en la arista entre los dos vértices correspondientes, y del mismo modo si habla tres lenguas colócalo en la cara correspondiente. El requisito de que todos tengan una lengua común significa que dos aristas opuestas no pueden estar ocupadas simultáneamente. Esto deja sólo dos topologías posibles para las aristas ocupadas: O bien las aristas ocupadas comparten un vértice, o bien forman un triángulo. Las caras ocupadas no tienen ninguna restricción, ya que una cara siempre comparte un vértice con cualquier arista (u otra cara). El número de hablantes de una lengua es la suma del número de personas que hay en cada cara y arista incidente con el vértice de esa lengua.

El caso agudo es si todas las aristas ocupadas comparten un vértice (véase la figura siguiente; las aristas ocupadas se muestran en rojo). Entonces la única manera de que ese vértice no tenga al menos 3/5 de la conferencia es que alguna fracción $x>2/5$ para estar en la cara opuesta $F$ (mostrado en azul). Hay una fracción $1-x$ no en $F$ y al menos un tercio de ellos debe ser incidente con algún vértice de $F$ (por pidgeonhole). Por lo tanto, este vértice tiene al menos $x+(1-x)/3 = 1/3+2x/3$ de la conferencia, que es $>3/5$ porque $x>2/5$ .

El otro caso es cuando hay tres aristas ocupadas formando un triángulo, que encierra alguna cara $F$ (se muestra en azul a continuación). Para cada vértice del triángulo, hay una arista del triángulo y una cara del tetraedro que no son incidentes en él. Por pidgeonholing, uno de los tres vértices del triángulo debe tener menos de un tercio de la conferencia en la arista o cara no incidente. Por lo tanto, al menos $2/3>3/5$ de la conferencia habla el idioma de ese vértice. QED

Answer 2

He aquí un argumento alternativo. Supongamos que no es así, y que el número de personas es $n$ . Si todo el mundo hablara al menos tres idiomas, entonces, por doble cuenta, algún idioma sería hablado por al menos $3n/4$ . Así que hay alguien que habla exactamente dos idiomas, A y B, digamos. Hay un conjunto $X$ de más de $2n/5$ que no hablan $A$ y un conjunto $Y$ de más de $2n/5$ sin hablar $B$ ya que todos tienen que tener una lengua en común con la primera persona, $X$ y $Y$ son disjuntos.

A partir de ahora sólo comprobaremos si todos los pares uno de $X$ y uno de $Y$ tienen un lenguaje común. En $X\cup Y$ debe haber algunas personas que no hablen C, y otras que no hablen D. No podemos tener a alguien que no hable C en un conjunto y a alguien que no hable D en el otro, así que todas estas personas están en el mismo conjunto, digamos $X$ . Esto significa que todos en $Y$ habla tanto C como D, y todos en $X$ habla C o D (o ambos). Ahora uno de los C y D es hablado por al menos la mitad de $X$ y todos los $Y$ que suma más de $3n/5$ contradicción.

Answer 3

¿Qué me falta? Si sólo se utiliza una lengua, entonces hemos terminado $n > \frac{3}{5}n$ . Digamos que para dos idiomas $l_1, l_2$ tenemos un conjunto de personas que tienen que hablar entre sí, es decir, todos ellos tienen que hablar entre sí a partir de la condición de que dos asistentes cualesquiera puedan hablar entre sí. Por lo tanto, cada uno de ellos debe saber $l_1$ o " $l_1$ y $l_2$ ". Tenga en cuenta que no puede hacer que los asistentes hablen "sólo" $l_2$ ya que los que hablan "solo" $l_1$ no puede hablar con ellos. Por lo tanto, el conjunto de personas tiene que ser $l_1$ y " $l_1$ y $l_2$ ". Así que de todos modos tenemos $n$ la gente conoce una lengua que es $l_1$ $>\frac{3}{5}n$ . Ahora, añada $l_3$ . "sólo" $l_3$ no sería suficiente ya que no pueden hablar con $l_1$ y " $l_1$ y $l_2$ ". Así que, o bien añade $l_1$ a $l_3$ lo que significa que hay una lengua $l_1$ que todo el mundo habla. No se puede añadir $l_2$ a $l_3$ ya que de nuevo " $l_2$ y $l_3$ El grupo "no puede hablar con "sólo" $l_1$ . De nuevo, hay $n$ personas que hablan $l_1$ y entonces hemos terminado. La idea es que no puede haber dos grupos en todo el conjunto con cada grupo hablando una sola lengua, siendo las lenguas diferentes. Ya que no pueden hablar entre ellos. Ahora añada $l_4$ . El mismo trato. Hay que añadir $l_4$ a todo conjunto que no sea $l_4$ o añadir $l_1$ a $l_4$ . De cualquier manera, obtenemos $n$ asistentes que hablan un solo idioma $l_1$ o $l_4$ .