Théorème des amis et des étrangers

Les 78 graphes possibles amis-étrangers avec 6 nœuds. Pour chaque graphe, les nœuds rouge/bleu montrent un exemple de triplet d'amis ou d'inconnus mutuels.

Le théorème des amis et des étrangers ou théorème des amis et des inconnus est un théorème dans le domaine des mathématiques appelé théorie de Ramsey et est un cas particulier du théorème de Ramsey.

Énoncé[modifier | modifier le code]

Supposons qu'une fête comporte six invités. Considérons deux d'entre eux. Ils pourraient se rencontrer pour la première fois—dans ce cas, nous allons les appeler des étrangers ou inconnus ; ou ils pourraient s'être rencontrés auparavant—dans ce cas, nous allons les appeler des connaissances mutuelles ou amis. Le théorème dit :

Dans toute fête de six personnes, soit au moins trois d'entre eux sont (par paires) mutuellement des étrangers, soit au moins trois d'entre eux sont (par paires) mutuellement des amis.

Conversion à une situation de théorie des graphes[modifier | modifier le code]

Une démonstration du théorème exige seulement un raisonnement logique en trois étapes. Il est commode de formuler le problème dans le langage de la théorie des graphes.

Supposons qu'un graphe simple a 6 sommets et que chaque paire de sommets (distincts) est jointe par une arête. Un tel graphe est appelé graphe complet (car il ne peut y avoir plus d'arêtes). Un graphe complet sur $n$ sommets est notée par le symbole $K_{n}$ .

Maintenant, prenez le graphe $K_{6}$ . Il a 15 arêtes en tout. Les 6 sommets correspondent aux 6 personnes de la fête. On choisit que les arêtes seront de couleur rouge ou bleu selon que les deux personnes représentées par les sommets reliés par l'arête commune, sont des étrangers ou des connaissances, respectivement. Le théorème affirme :

Peu importe comment vous coloriez les 15 arêtes d'un

K_{6}

en rouge et bleu, vous ne pouvez pas éviter d'avoir soit un triangle rouge, un triangle dont les trois côtés sont de couleur rouge, ce qui représente trois paires d'étrangers mutuels—ou un triangle bleu, représentant les trois paires de connaissances mutuelles. En d'autres termes, quelles que soient les couleurs que vous utilisez, il y aura toujours au moins un triangle monochromatique (c'est un triangle dont tous les côtés ont la même couleur).

La preuve[modifier | modifier le code]

Choisissez un sommet quelconque ; appelons-le P. Il y a cinq arêtes issues de P. Elles sont de couleur rouge ou bleu. Le principe des tiroirs dit qu'au moins trois d'entre eux doivent être de la même couleur ; car s'il y a moins de trois d'une couleur, disons rouge, alors il y en a au moins trois qui sont en bleu.

Soient A, B, C les autres extrémités de ces trois arêtes, toutes de la même couleur, disons bleu. Si parmi AB, BC, CA, l'une est bleue, alors cette arête avec les deux arêtes joignant P aux extrémités de cette arête forme un triangle bleu. Si aucune parmi AB, BC, CA n'est bleue, alors les trois arêtes sont rouges et nous avons un triangle rouge, à savoir, ABC.

En fait, on peut trouver deux triangles monochromes.

L'article de Ramsey[modifier | modifier le code]

L'extrême simplicité de cet argument, qui a si puissamment produit une conclusion très intéressante, est ce qui rend le théorème attrayant. En 1930, dans un article intitulé Sur un problème de logique formelle (On a Problem in Formal Logic), Frank Ramsey a prouvé un théorème très général (maintenant connu comme le théorème de Ramsey) dont ce théorème est un cas simple. Ce théorème de Ramsey est à la base du domaine connu sous le nom de théorie de Ramsey dans le domaine de la combinatoire.

Limites du théorème[modifier | modifier le code]

La conclusion du théorème ne tient pas si l'on remplace la fête de six personnes par une fête de moins de six. Pour l'illustrer, nous donner une coloration de $K_{5}$ avec le rouge et le bleu qui ne contient pas de triangle avec toutes les arêtes de la même couleur. Nous dessinons $K_{5}$ sous la forme d'un pentagone entourant une étoile (un pentagramme). Nous colorions les arêtes du pentagone en rouge et les arêtes de l'étoile en bleu. Ainsi, 6 est le plus petit nombre pour lequel nous pouvons prétendre appliquer le théorème. Dans la théorie de Ramsey, nous écrivons ce fait par :

R(3,3:2)=6.\,

Bibliographie[modifier | modifier le code]

V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990. (ISBN 81-224-0272-0).

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Theorem on friends and strangers » (voir la liste des auteurs).

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

(en) Bogomolny, Alexander, Party Acquaintances sur Cut The Knot (nécessite Java)

Portail des mathématiques