Solution au problème de Septembre 2002

Dans un groupe de sept personnes, chaque personne parle au plus deux langues. De plus, dès que trois d'entre eux se retrouvent ensemble, il y en a au moins deux des trois qui peuvent communiquer (parce qu'ils parlent une langue commune). Démontrez qu'il existe une langue qui est parlée par au moins trois de ces sept personnes.

Solution:
Cinq personnes nous ont envoyé une solution: Pierre Bornsztein (de France), Normand Laliberté (d'Ontario), Patrick J. LoPresti (du Massachusetts), Juan Mir Pieras (d'Espagne) et Alexander Potapenko (de Russie). Selon nos informations, Bornsztein et Laliberté parlent le fran¨ais et l'anglais, LoPresti parle l'anglais, Mir parle l'espagnol et l'anglais et Potapenko parle le russe et l'anglais. On note donc que nos cinq répondants peuvent communiquer entre eux en anglais. Xing Chiu (d'Ontario) nous fait remarquer que si tous ont l'anglais comme langue seconde, alors tous peuvent communiquer entre eux.

Cependant, lorsqu'il n'existe pas de langue seconde commune a tous, alors la situation peut être étrange: Considérons trois amis qui se rencontrent dans un café de Madrid:

A parle l'arabe et le basque,
B parle le basque et le catalan,
C parle le catalan et l'arabe. Alors ils peuvent bavarder deux à deux, en se servant d'une langue commune, mais il n'existe aucune langue qu'ils peuvent utiliser pour bavarder tous les trois! La même situation se répète avec trois autres amis, D, E et F, qui se retrouvent dans un café de Prague: D parle l'anglais et l'allemand,
E parle l'allemand et le russe,
F parle le russe et l'anglais. Maintenant, considérons le groupe formé des six personnes A, B, C, D, E et F. On remarque que parmi n'importe quel sous groupe de trois de ces personnes, on en trouve au moins deux qui parlent une langue commune. Pourtant, il n'existe aucune langue parlée par au moins trois de ces personnes. Le problème du mois est de démontrer que cette situation ne peut pas se produire dans un groupe de sept personnes.

Toutes nos solutions sont basées sur l'observation suivante:

Si une personne peut communiquer avec au moins trois autres personnes, alors il existe trois personnes parlant la même langue. En effet, si Amandine, qui ne parle que le fran¨ais et l'espagnol, peut communiquer avec Pierre, Leticia et Juan, alors elle communique avec au moins deux personnes (disons Leticia et Juan) avec la même langue (disons l'espagnol), donc Amandine, Leticia et Juan parlent la même langue.

A partir de cette observation, LoPresti, Mir et Potapenko résolvent notre problème ainsi: Considérons une personne du groupe (disons Eve). Si elle peut communiquer avec au moins trois personnes, alors trois personnes parlent une langue commune d'après l'observation précédente. Par contre, si Eve communique avec au plus deux personnes, alors il existe au moins quatre personnes qui ne peuvent pas communiquer avec Eve. Ces quatres personnes communiquent toutes entre elles, parce que si deux d'entre elles ne pouvaient communiquer, alors ces deux personnes formeraient avec Eve un trio ne contenant aucune paire pouvant communiquer. Ainsi, chacune des personnes ne pouvant communiquer avec Eve peut communiquer avec au moins trois personnes, donc trois personnes parlent une langue commune d'après l'observation ci-haut.

La solution de Laliberté repose plutôt sur le principe des tiroirs de Dirichlet: Considérons Eve encore une fois, et supposons qu'elle ne communique qu'avec au plus deux personnes. Choisissons une personne (disons Lilith) qui ne communique pas avec Eve. Alors Eve et Lilith parlent en tout au plus quatre langues (disons l'arabe, le basque, le catalan et le danois). Chacune des cinq autres personnes doit parler au moins une de ces quatre langues, autrement elle constitue avec Eve et Lilith un trio dont aucune paire ne communique. Ainsi, une des quatres langues est parlée par au moins deux des cinq autres personnes en plus d'être parlée par Eve ou Lilith, donc trois personnes parlent une langue commune.

La solution de Bornsztein est basée sur le théorème de Turan: Considérons le graphe dont les sommets sont les sept personnes, et les arêtes sont les paires de personnes ne pouvant pas communiquer. Selon nos hypothèses, ce graphe ne contient pas de triangles, c'est à dire de triplets {A, B, C} dont toutes les paires forment une arête. Selon le théorème de Turan, un graphe à n sommets ne contenant pas de triangles a au plus ( n/2)2 arêtes. Ici, on a n = 7, donc le nombre d'arêtes est au plus 12.25. En fait, puisqu'il s'agit d'un nombre entier, le nombre d'arêtes est au plus 12. Puisque les sept personnes forment en tout  7*6/2 = 21 paires, il reste au moins 21 - 12 = 9 paires de personnes pouvant communiquer. Notons d(i) le nombre de personnes avec qui la i-ième personne peut communiquer. La moyenne des d(i) est

Chaque paire de personnes pouvant communiquer contribue deux unités au numérateur: la paire {i-ième personne, j-ième personne} contribue une unité à d(i) et une unité à d(j). Ainsi la moyenne ci-haut peut s'écrire 2*(le nombre de paires pouvant communiquer)/7, Ce qui est au moins  2*9/7, soit approximativement 2.57. Par suite, au moins un des d(i) est supérieur ou égal à cette moyenne; et puisque d(i) est un nombre entier, il doit valoir au moins 3. Ainsi, la i-ième personne peut communiquer avec au moins trois autres personnes, donc trois personnes parlent une langue commune d'après l'observation ci-haut.

Notes: Soit N(t,m,p), le nombre maximal de personnes satisfaisant aux propriétés suivantes:

1) Chaque personne parle au plus t langues,
2) Dans chaque groupe de m personnes on trouve au moins une paire pouvant communiquer,
3) Aucune langue n'est parlée par au moins p personnes. Ce paramêtre est étudié dans H.L. Abbott, D. Hanson, et A.C. Liu, "An Extremal Problem in Graph Theory." Quarterly Journal of Mathematics 31:121 (mars 1980), pages 1-7. Notre problème du mois était de démontrer que N(2,3,3) est inférieur à 7.

Problèmes et solutions précédents
 
Centrale des Maths