El problema de las triples pitagóricas booleanas es un problema de la teoría de Ramsey acerca de si los números enteros positivos pueden ser de color rojo y azul para que ninguna tripleta pitagórica consista en todos los miembros rojos o azules. El problema de las triples booleanas pitagóricas fue resuelto por Marijn Heule , Oliver Kullmann y Victor W. Marek en mayo de 2016 a través de una prueba asistida por computadora . [1]
Declaración
El problema pregunta si es posible colorear cada uno de los enteros positivos de rojo o azul, de modo que ningún triple pitagórico de los enteros a , b , c , satisfaga son todos del mismo color.
Por ejemplo, en el triple pitagórico 3, 4 y 5 (), si 3 y 4 son de color rojo, entonces 5 debe ser de color azul.
Solución
Marijn Heule , Oliver Kullmann y Victor W. Marek demostraron que tal coloración solo es posible hasta el número 7824. El enunciado real del teorema demostrado es
Teorema : el conjunto {1,. . . , 7824} se puede dividir en dos partes, de modo que ninguna parte contenga un triple pitagórico, mientras que esto es imposible para {1,. . . , 7825}. [2]
Hay 2 7825 ≈ 3,63 × 10 2355 posibles combinaciones de colorante para los números de hasta 7.825 . Estos posibles colorantes se redujeron lógica y algorítmicamente a alrededor de un billón de casos (aún muy complejos), y se examinaron utilizando un solucionador de satisfacibilidad booleano . La creación de la prueba tomó aproximadamente 4 años de CPU de cálculo durante un período de dos días en la supercomputadora Stampede en el Centro de Computación Avanzada de Texas y generó una prueba proposicional de 200 terabytes, que se comprimió a 68 gigabytes.
El artículo que describe la prueba fue publicado en la conferencia SAT 2016, [2] donde ganó el premio al mejor artículo. [3] La siguiente figura muestra una posible familia de colorantes para el conjunto {1, ..., 7824} sin triple pitagórico monocromático, y los cuadrados blancos se pueden colorear en rojo o azul mientras se sigue cumpliendo esta condición.
Premio
En la década de 1980, Ronald Graham ofreció un premio de $ 100 por la solución del problema, que ahora ha sido otorgado a Marijn Heule . [1]
Generalizaciones
A partir de 2018, el problema todavía está abierta durante más de 2 colores, es decir, si existe un k -Coloreado ( k ≥ 3) de los números enteros positivos tales que no hay triples pitagóricos son del mismo color. [4]
Ver también
Referencias
- ↑ a b Lamb, Evelyn (26 de mayo de 2016). "La prueba matemática de doscientos terabytes es la más grande hasta ahora" . Naturaleza . 534 : 17-18. Código Bib : 2016Natur.534 ... 17L . doi : 10.1038 / nature.2016.19990 . PMID 27251254 .
- ^ a b Heule, Marijn JH; Kullmann, Oliver; Marek, Victor W. (2016). "Resolver y verificar el problema de las triples pitagóricas booleanas a través de Cube-and-Conquer". En Creignou, Nadia; Le Berre, Daniel (eds.). Teoría y aplicaciones de las pruebas de satisfacción - SAT 2016: XIX Conferencia Internacional, Burdeos, Francia, 5-8 de julio de 2016, Actas . Apuntes de conferencias en Ciencias de la Computación. 9710 . págs. 228–245. arXiv : 1605.00723 . doi : 10.1007 / 978-3-319-40970-2_15 .
- ^ SAT 2016
- ^ Eliahou, Shalom; Fromentin, Jean; Marion-Poty, Virginie; Robilliard, Denis (2 de octubre de 2018). "¿Son inevitables las tripletas pitagóricas monocromáticas bajo los colorantes mórficos?" . Matemáticas experimentales . 27 (4): 419–425. arXiv : 1605.00859 . doi : 10.1080 / 10586458.2017.1306465 . ISSN 1058-6458 .