Content deleted Content added
Reverted 2 edits by 103.251.51.215 (talk): Unexplained removals |
Added the solution to the lead, so that the reader immediately gets that the answer is "No, from 7825 and up" |
||
| (24 intermediate revisions by 20 users not shown) | |||
Line 1:
{{short description|Can one split the integers into two sets such that every Pythagorean triple spans both?}}
The '''Boolean Pythagorean triples problem''' is a problem from [[Ramsey theory]] about whether the [[natural number|positive integers]] can be colored red and blue so that no [[Pythagorean triple]]s consist of all red or all blue members. The Boolean Pythagorean triples problem was solved by [[Marijn Heule]],
==Statement==
The problem asks if it is possible to color each of the positive integers either red or blue, so that no Pythagorean triple of integers ''a'', ''b'', ''c'', satisfying <math>a^2+b^2=c^2</math> are all the same color.
For example, in the Pythagorean triple 3, 4, and 5 (<math>3^2+4^2=5^2</math>), if 3 and 4 are colored red, then 5 must be colored blue.
==Solution==
[[Marijn Heule]],
{{math theorem|
}} There are {{nowrap|2<sup>7825</sup> ≈ 3.63×10<sup>2355</sup>}} possible coloring combinations for the numbers up to [[7825 (number)|7825]]. These possible colorings were logically and algorithmically narrowed down to around a trillion (still highly complex) cases, and those, expressed as [[Boolean satisfiability]] problems, were examined using a [[
The paper describing the proof was published in the SAT 2016 conference,<ref name="arXiv">{{Cite conference|
[[File:Ptn-7824-zoom-2.png|alt=|center|400x400px]]
==Prize==
In the 1980s [[Ronald Graham]] offered a $100 prize for the solution of the problem, which has now been awarded to [[Marijn Heule]].<ref name="nature"/>
== Generalizations ==
As of 2018, the problem is still open for more than 2 colors, that is, if there exists a ''k''-coloring (''k'' ≥ 3) of the positive integers such that no Pythagorean triples are the same color.<ref>{{Cite journal|
== See also ==
| |||