title: Problème des triplets booléens de Pythagore
text: # Problème des triplets booléens de Pythagore
  
  Le problème des triplets booléens de Pythagore est un problème de la théorie de Ramsey qui consiste à savoir si les entiers positifs peuvent être colorés en rouge et en bleu de sorte qu'aucun triplet de Pythagore ne se compose de tous les membres rouges ou bleus. Le problème des triplets booléens de Pythagore a été résolu par Marijn Heule, Oliver Kullmann et Victor W. Marek en mai 2016 grâce à une preuve assistée par ordinateur.
  
  ## Énoncé
  
  Le problème consiste à savoir s'il est possible de colorier chacun des entiers positifs en rouge ou en bleu, de sorte qu'aucun triplet de Pythagore d'entiers a, b, c, satisfaisant $a^{2}+b^{2}=c^{2}$ soient tous de la même couleur.
  
  Par exemple, dans le triplet de Pythagore 3, 4 et 5 ( $3^{2}+4^{2}=5^{2}$ ), si 3 et 4 sont colorés en rouge, alors 5 doit être coloré en bleu.
  
  ## Solution
  
  Marijn Heule, Oliver Kullmann et Victor W. Marek ont montré qu'une telle coloration n'est possible que jusqu'au nombre 7824. L'énoncé réel du théorème prouvé est
  
  Théorème — L'ensemble {1, . . . , 7824} peut être partitionné en deux sous-ensembles de sorte qu'aucun des sous-ensembles n'inclut un triplet de Pythagore. Cela est impossible pour {1, . . . , 7825}.
  
  Il existe $2^{7825}$ ≈ $3.63×10^{2355}$ combinaisons de couleurs possibles pour les nombres jusqu'à 7825 . Ces colorations possibles ont été logiquement et algorithmiquement réduites à environ un billion de cas (toujours très complexes), et celles-ci ont été examinées à l'aide d'un solveur booléen de satisfiabilité. La création de la preuve a nécessité environ 4 années CPU de calcul sur une période de deux jours sur le supercalculateur Stampede du Texas Advanced Computing Center et a généré une preuve propositionnelle de 200 téraoctets, qui a été compressée à 68 gigaoctets.
  
  L'article décrivant la preuve a été publié lors de la conférence SAT 2016, où il a remporté le prix du meilleur article. La figure ci-dessous montre une famille possible de colorations pour l'ensemble {1,...,7824} sans triplet de Pythagore monochromatique, et les carrés blancs peuvent être colorés en rouge ou en bleu tout en satisfaisant à cette condition.
  
  ## Prix
  
  Dans les années 1980 , Ronald Graham a offert un prix de 100 $ pour la solution du problème, qui a maintenant été décerné à Marijn Heule.
  
  ## Généralisations
  
  Depuis 2018, le problème est toujours ouvert pour plus de 2 couleurs, c'est-à-dire s'il existe une k-coloration ( k ≥ 3) des entiers positifs telle qu'aucun triplet de Pythagore n'est de la même couleur.
  
  