Colorez en rouge ou en bleu chacune des lignes qui relient six points. Quelque part dans le résultat il y a un triangle dont les trois côtés sont de la même couleur, et six est le plus petit nombre de points pour lequel c'est garanti. La preuve est l'argument de la fête : choisissez une personne, qui a cinq relations, et au moins trois d'entre elles sont du même type par le principe des tiroirs ; si deux quelconques de ces trois se connaissent entre elles vous avez votre triangle, et si aucune ne se connaît, ces trois sont mutuellement inconnues et vous avez l'autre. Les six personnes font 6 × 5/2 = 15 paires (deuxième lien), alors une machine peut résoudre par épuisement en 2^15 = 32 768 cas (premier lien) : assez petit pour que personne n'ait d'excuse pour ne pas le faire, et l'optimalité se vérifie avec le cycle à cinq, un pentagone rouge avec une étoile bleue à l'intérieur, qui évite les deux triangles sur cinq points.
Le nombre diagonal suivant, R(4,4) = 18, coûte 2^153 colorations : dix-huit points ont 18 × 17/2 = 153 paires entre eux (troisième lien), et 2^153 est 1.1417981541648⋅10+46 (quatrième), ce qui n'est pas un nombre dont on discute en comptant. Greenwood et Gleason ont obtenu 18 en 1955 avec un mélange de bornes et de cas vérifiés à la main ; R(5,5), les trois premières couleurs de la même question, reste ouvert depuis, sachant seulement qu'il est dans une fourchette étroite qui a un peu bougé en soixante-dix ans. Le théorème de Ramsey lui-même, de 1930, traitait de la machinerie logique en dessous de tout cela, et il a été démontré parce qu'on en avait besoin pour une question de philosophie des mathématiques : la certitude que toute structure suffisamment grande contient une grande pièce ordonnée d'elle-même.
Réponse
32768
Comment la lire
2^15 dans l'espace de travail : chaque bicoloration des quinze paires de six personnes. Le deuxième lien est les quinze paires elles-mêmes.
Source
Frank P. Ramsey, 'On a Problem of Formal Logic', 1930; R(3,3) = 6 is the party theorem, R(4,4) = 18 was proved by Greenwood and Gleason in 1955, and R(5,5) is still unknown
Résolvez-le dans la calculatrice
Ces liens ouvrent la calculatrice appropriée avec les nombres de ce problème déjà saisis. La ligne ci-dessus correspond à ce que l'écran devrait afficher : vérifiez par vous-même.