The simple number solves a notoriously complicated problem.
A duo of mathematicians just solved a 15-year-old problem.
They found an answer to how many numbers you need to fill an infinite grid under specific conditions.
The answer: a simple 15.
15: That’s the answer to an incredibly complicated math problem recently solved by a two-person team at Carnegie Mellon University (CMU). Usually, big, complicated math problems that are hard to solve have big, complicated answers that are almost equally hard for the layperson to understand. But not this one. This one is just … 15.
The question, originally posed in 2008, went as such: If you had an infinite grid of squares—like a sheet of graph paper that went on for eternity—and you wanted to fill it with numbers that had to be more-than-that-number squares apart, what is the minimum number of different numbers you would need? This is called the “packing coloring” problem.
And it had this caveat—repeating numbers’ distance “apart” refers to something called their “taxicab distance,” meaning you only squares between numbers in straight lines along paths made of right angles. So, for example, two 1s could not be right next to each other, because their “taxicab distance” would only be one square. But they could be diagonal from each other, because their “taxicab distance” would be two—one to the side and one up or down. The same rule goes for all the other numbers. Their “taxicab distance” from their nearest repeat had to be one more than their value.
Confused yet?
If so, it’s fair. After all, the problem took top mathematicians over a decade to solve, and it wasn’t possible without a lot of computing power and a fair amount of creativity.
According to a Quanta Magazine article, the duo who solved the problem— CMU grad student Bernardo Subercaseaux and CMU professor Marijn Heule—originally managed to narrow the list of potential answers down to just 13, 14, or 15. But that group of answers had already been achieved by another team a few years before, and Subercaseaux and Heule wanted a true answer, not a range of possibilities. So, they turned to powerful computers. Especially because, in order to rule out a potential answer, they had to make sure they tried every single combination of number placements.
Unfortunately, that takes a lot of time to do, even for a highly advanced and extremely powerful computer. So, the researchers got creative. They figured out that, for the sake of this problem, symmetrical answers are the same. Mirroring the whole grid wouldn’t change the result, but it would double the amount of work the computer had to do. So, they implemented the “don’t worry about symmetrical results” rule and were able to rule out 13, leaving just 14 and 15 on the table.
But every time the number tested got bigger, the computer process took a whole lot longer. So, even with the “don’t worry about symmetrical results” rule in place, the computation to test 14 was going to take too long for the satisfaction of Subercaseaux and Heule. In addition, University of Colorado mathematician Alexander Soifer told Quanta Magazine that the duo didn’t just want to brute-force the problem, but wanted to “solve it in an impressive way.”
Subercaseaux and Heule eventually realized that if they had the computer examine chunks of space together instead of each individual square, the calculation became a lot more efficient. So, they divided the space up into plus signs built from 5 squares, and had the computer check each plus sign for red flags instead of each square.
And in just a little while, the computer ran it’s experiment and threw a flag on 14. Leaving only 15 as an option and 15 as the answer. All that work, and all that programming, and all that creativity for a simple 15.
You’re probably not going to run into an infinite grid that needs filled under very specific conditions in real life, but solving problems like this isn't always about making the most real-world-applicable discovery. Sometimes, it really is more about the journey than the destination.
Popular Mechanics
