Organiser une soirée… sous contraintes sanitaires
Le BDF considère que la fête sera réussie si au moins trois invités se connaissent entre eux – car ils sauront alors initier une bonne dynamique pendant la soirée – ou si, au contraire, au moins trois convives ne se connaissent pas du tout – car les rencontres sont toujours stimulantes. Conscient des risques sanitaires, le BDF souhaite également inviter le moins de personnes possible. Combien de convives doit-il tirer au hasard pour respecter toutes ces contraintes ?
La réponse est 6. Mais combien aurait-il fallu inviter de personnes si, au lieu de trois, le BDF avait voulu garantir un groupe de k convives se connaissant les uns les autres ou au contraire ne se connaissent pas du tout entre eux ? Cette question se reformule ainsi en langage de théorie des graphes : déterminer le kème nombre diagonal de Ramsey R (k).
Des formes et des couleurs
Traduisons le problème du BDF en termes mathématiques.
Représentons chaque convive par un point (un sommet) sur une feuille, puis relions chaque paire de points par un trait (une arête), rouge si les deux convives qu’ils représentent se connaissent, bleu sinon. On a alors construit un graphe complet. Exiger qu’il existe soit ...
Lire la suite gratuitement