15: This is the answer to an incredibly difficult math problem that was recently solved by a team of two at Carnegie Mellon University (CMU). Often, large, complex math problems that are difficult to solve have large, complex answers that are almost equally difficult for a layman to understand. But this is not it. It’s just … 15. The question that was first asked in 2008 was: If you had a grid of infinite squares, like an endless graph paper, and you wanted to fill it with numbers that had to be greater than that—what is the minimum number of distinct numbers you would need when dividing the number squares? This is called the “packaging color” problem.
And the caveat was this: “Separately” repeated number range refers to the so-called “taxi range”; this means you only place squares between numbers on straight lines along rails made at right angles. So for example two units cannot be side by side because the “taxi distance” would be just one square. But they can be placed diagonally from each other, because their “taxis” will be two – one to the sides and one up or down. The same rule applies to all other numbers. The “taxi distance” from the nearest repeat must be one greater than their value.
Are you still confused?
If so, then it’s fair. After all, it took more than a decade for leading mathematicians to solve this problem, and this wouldn’t be possible without a lot of computing power and a fair amount of creativity.
According to the article Quanta MagazineThe duo who solved the problem – CMU graduate student Bernardo Subercaso and CMU professor Marijn Heule – were first able to reduce the list of possible answers to just 13, 14 or 15. But this set of answers had already been obtained by another team. a few years ago and Suberkaso and Guleh wanted a real answer, not a set of possibilities. That’s why they turned to powerful computers. Especially since they need to make sure they try every combination of number placements to rule out a potential response.
Unfortunately, this takes a long time, even for a very advanced and extremely powerful computer. So researchers approached creativity. They found that the symmetrical answers for this problem were the same. Mirroring the entire grid does not change the result, but doubles the amount of work the computer has to do. So they applied the “don’t worry about the symmetric results” rule and managed to eliminate 13, with only 14 and 15 left on the table.
But each time the number of subjects increased, the computer processing took much longer. Thus, even with the “don’t worry about symmetric results” rule, the calculation to verify 14 would have taken too long to satisfy Suberkaso and Guleh. Also, University of Colorado mathematician Alexander Soifer said: Quanta Magazine, He said that the duo not only wanted to tackle the problem, but also wanted to “solve it in a fantastic way”.
Eventually, Suberkaso and Guleh realized that calculations would become much more efficient if the computer explored pieces of space together rather than each square. So they divided the space into 5 square crosshairs and had the computer check each cross for red flags instead of each square.
And after a while the computer ran the experiment and marked 14. 15 is left as an option and 15 as an answer. All this work, all this programming and all that creativity for only 15.
You probably wouldn’t encounter an endless grid that would be filled under very specific circumstances in real life, but solving problems like this isn’t always about making the most real-world exploration. Sometimes it’s really more about the journey than the destination.
Source: Port Altele
