Solución del problema de septiembre, 2002

En un grupo de siete personas, cada una de ellas habla a lo más dos idiomas, mientras que entre cada tres de ellas hay por lo menos dos que se pueden comunicar entre sí. Pruebe que hay tres personas que hablan un idioma en común.

Recibímos soluciones de Pierre Bornsztein (Francia), Normand Laliberté (Ontario), Patrick J. LoPresti (Massachussets), Juan Mir Pieras (España) y Alexander Potapenko (Rusia). Según nuestros registros, Bornsztein and Liberté hablan Francés e Inglés, LoPresti habla Inglés, Mir habla Español e Inglés, y Potapenko habla Ruso e Inglés. Note que los cinco corresponsales pueden comunicarse en Inglés. Xiang Chiu (Ontario) indicó que si todos hablaran el Inglés como segundo idioma entonces todos podrían comunicarse entre sí!

Sin embargo, cuando no hay un idioma en común, muchas cosas son posibles. Considere tres amigos que se encuentran en un café en Madrid:

A habla Árabe y Vasco
B habla Vasco y Catalán, y
C habla Catalán y Árabe. Ciertamente que cualquier par de ellos puede conversar usando su idioma en común, pero no existe un idioma común entre los tres. Una situación similar se sucede entre tres amigos, D, E, y F, que se encuentran en un café en Praga. D habla Inglés y Alemán
E habla Alemán y Ruso, y
F habla Ruso e Inglés. Que pase cuando los seis A, B, C, D, E y F se encuentran? Note que para cualquiera tres de ellos, usted puede encontrar dos que hablan un idioma en común. Sin embargo no hay un idioma sea hablado por tres o más de ellos. El problema de septiembre pide que se pruebe que esta situación no puede ocurrir en ningún grupo de siete.

Todas las soluciones que recibimos están basadas en la observación simple de que

Si una persona puede comunicarse por lo menos con tres gentes,    (*)
entonces existen tres que hablan el mismo idioma En efecto, si Amandine, que habla solamente Francés y Español, puede comunicarse con Pierre, Leticia, y Juan, entonces por lo menos dos de estos tres pueden hablar Francés, o dos de ellos (digamos, Leticia y Juan) pueden hablar Español. Esto significa que Amandine, Leticia, y Juan pueden todos ellos hablar Español.

Con la ayuda de esta observación LoPresti, Mir y Potapenko resolvieron nuestro problema como sigue: escoja uno de los siete; llamémosla Eva. Si ella pudiera comunicarse por lo menos con tres gentes, entonces tres gentes hablan un idioma en común como consecuencia de (*). La única otra posibilidad es que Eva se comunique a lo más con dos. Esto dejaría por lo menos a cuatro que no pueden comunicarse con Eva. , porque si dos de ellos no tuvieran un idioma en común ellos formarían con Eva un trío con un idioma en común, contrario a la hipótesis inicial. Entonces cada uno de los que no pueden hablar con Eva pueden comunicarse por lo menos con los otros tres, y la conclusión que buscamos -- que hay un idioma en común en por lo menos tres gentes Ð se sigue de la observación (*).

La solución de Liberté usa el principio del palomar. Examinemos otra vez el caso en que Eva puede comunicarse con a lo más dos gentes. Escoja una de esas gentes, digamos Lilith, que no puede hablar con Eva. Entonces Eva y Lilith juntas hablan a lo más cuatro idiomas. Todas las otras cinco gentes deben hablar por lo menos uno de los otro cuatro idiomas -- de otra manera ellas formarían con Eva y Lilith un trío sin un idioma en común. Entonces, uno de los cuatro idiomas es hablado por lo menos por dos de las cuatro gentes, aparte de ser hablado por Eva o Lilith. Entonces, este idioma es hablado por lo menos tres, como se deseaba.

Finalmente, la solución de Bornsztein esta basada en el teorema de Turán. Considere la gráfica cuyos vértices representan a las siete gentes, y cuyas aristas unen dos gentes que no puede comunicarse. Según la hipótesis, esta gráfica no contiene triángulos Ð esto es, ningún trío (A, B, C) de vértices para los cuales cada par es unido por una arista. El teorema de Turán dice que una gráfica sin triángulos con n vértices tiene a lo más aristas. Aquí, con n = 7, puede haber a lo más 12 aristas (el entero más grande menor que  49/4)). Ya que siete vértices forman  7x6/2 = 21 pares, restan por lo menos 21 - 12 = 9 pares sin aristas que los conecten (correspondiendo a los parejas de gentes que tienen un idioma en común). Indique Con d(i) el número de gentes que tienen un idioma en común con la persona i. El promedio de estos números d(i) es

Cada par {i,j} con un idioma en común contribuye con dos en el numerador Ð una por d(i) y una por d(j). Entonces el promedio de arriba es igual a 2*(el número de parejas con un idioma en común)/7. Esto es por lo menos  2x9/7 2.57. En consecuencia, por lo menos uno de los d(i) 2.57; ya que d(i) es un entero, debe ser por lo menos 3. Se sigue que por lo menos uno de las personas i pueden comunicarse por lo menos con otras tres gentes, y por lo tanto, de la observación (*) otra vez vemos que debe de haber otro idioma común entre por lo menos tres gentes.

Comentario. Sea N(t,m,p) el número mas grande de gentes que (1) cada una habla a lo más t idiomas; (2) entre cualquier m, dos hablan un idioma en común; y (3) no p hablan un idioma en común. H.L. Abbot, D. Hanson, y A.C. Liu investigaron este número en "An Extremal Problem in Graph Theory." Quarterly Journal of Mathematics 31:121 (Marzo, 1980), páginas 1-7. Nuestro problema requiere que se demuestre que N(2,3,3) < 7.