The Puzzle That Fights Back

This math puzzle completely defies human instinct — even challenging the very idea of what it means to do math. It’s a simple tiling question (or graph coloring question, depending on how you look at it), yet it took a 122 terabyte proof to solve, and an intuitive pattern of tiles that seems to always hold on the small scale is in fact destined to break on the larger scale. When Bernardo Subercaseaux and Professor Marijn Heule of Carnegie Mellon University (who eventually solved this problem using SAT Solvers — specialized computer programs for trying to satisfy logical constraints) figured out that the pattern must break in certain situations, it was so fascinating to them that they even made a framed art piece out of it. I’m so glad to have been one of many visitors to lay eyes on it and share that same wonder. I hope to now be able to share it with you through this video, which is about the truly beautiful story of how they solved this delightful math problem, which asks about the so-called “packing chromatic number” of, or the minimum number of different kinds of tiles needed to cover an infinite square grid, while enforcing a straightforward distancing requirement between tiles with the same number. Check out this other video I made with Professor Heule and Bernardo Subercaseaux about their solution to a century-old geometry problem about “empty hexagons”:    • The Mysterious Number That Took 100 Years ...   Special thanks to Bernardo Subercaseaux and Professor Marijn Heule for their contributions to making this video, and to Professor Heule and Carnegie Mellon University for funding the video. As always, special thanks to my Patreon Supporters for helping to fund this video as well. If you’d like to support this channel, this is one of the best ways to do it! Every contribution is sincerely, greatly appreciated. Join here:   / purplemindcreations   This video is part of "Forefront," a collection of videos on this channel that features the cutting edge of research in math and computer science. Full playlist here:    • Forefront   If you or your institution is interested in sponsoring the topic of a future PurpleMind video, please contact me via purplemindcs@gmail.com! References: Bernardo’s blog post about this story (very fun read, by the way): https://bsubercaseaux.github.io/blog/... Bernardo and Heule’s article about the stark contrast between the two variants of the problem (also a great read): https://www.cs.cmu.edu/~mheule/public... Subercaseaux and Heule paper where they proved the answer is at least 14: https://www.cs.cmu.edu/~mheule/public... Subercaseaux and Heule paper where they proved the answer is 15: https://arxiv.org/pdf/2301.09757 Goddard and Xu paper on graph coloring and packing chromatic number: https://people.computing.clemson.edu/... Basel Problem: https://en.wikipedia.org/wiki/Basel_p... SAT Solvers: https://en.wikipedia.org/wiki/SAT_solver SAT Competition 2023 (which Heule and a couple graduate students won due to ideas inspired by the plus-shaped regions): https://satcompetition.github.io/2023/ Structured Bounded Variable Addition (the generalized SAT solving optimization inspired by the plus shapes from the video): https://www.cs.cmu.edu/~mheule/public... Roa Church for those who are curious: https://maps.app.goo.gl/EiGdn67dNyE8d... Piet Hein quote:   / problems-worthy-of-attack-prove-their-wort...   Brittle Rille - Reunited by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/... We Always Thought the Future Would Be Kind of Fun by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/... Math animations are made using Manim, by 3Blue1Brown. Discord Server:   / discord  . Feel free to join! Business Inquiries: purplemindcs@gmail.com