An undergraduate at the University of Chile spotted a question posed at an online forum and he fell in love with it, wanting to find the answer. The question asked about filling an infinite grid with numbers and in order to solve it, he had to leave Chile to attend Carnegie Mellon University in the United States.
In August, this young man met with a computer scientist who loves using the computer to solve hard problems and they began collaborating to find an answer to the question. This past January, they finally came up with the solution. 15! A nice beautifully simple answer.
Now let's go back in history a bit. In 2002, some folks were looking at the question about coloring maps with certain constraints applied such as no two contiguous areas could have the same color. To work the problem, they relied on the premise that a grid that goes on infinitely in both directions is a good place to start. They made the constraint that the distance between two numbers could be closer than the number itself. Distance was defined as adding the vertical and horizontal separation together.
An example of this would be the number one. Ones cannot be next to each other because their distance is one apart but they can be placed diagonally from each other since the distance is two ( 1 over + 1 up). When they finally published their results, they'd calculated the numbers needed as 22 in 2008. One thing about this problem is that they didn't have to do it for the whole infinite grid. Instead, they could use a small subset such as a 10 by 10 grid to show how many numbers needed because it is thought that the smaller grid repeats itself infinitely.
The young man from Chile, Bernardo Subercaseaux, originally attacked this problem by trying to sketch out various scenarios using pencil and paper. When he got tired of this he asked a friend to design a web-based application he could use and play with like a game. Eventually, he hit a point where he couldn't move any further because it is harder to prove can't be covered by a certain group of numbers than it is to prove they can.
Once he began collaborating with the computer person, he was able to expand his search and discovered 15 numbers is the perfect set and they also were able to rule out 12 numbers in the subset. Shortly after they realized that others had concluded that the answer could not be less than 13 or more than 15. In fact, there was 20 years of research on this particular problem.
In order to effectively use the computer, they needed to find ways of limiting the number of combinations the computer had to try. They didn't want to use brute force but find a way that would be more elegant. They were able to acknowledge that many of the combinations are pretty much the same. For instance, certain locations are essentially the same such as one up and one over or one down and one the other direction. These two are symmetrical to each other so it's not necessary to check both.
Using this and a couple of other constraints, they were able to rule out 13 as a possibility in January of 2022. Then redoing a couple of things, they were able to rule out 14 in September of 2022 and thus came to the conclusion that 15 was the proper answer. If you want to read the article it's here.
I think this is cool. Let me know what you think, I'd love to hear. Have a great day.
No comments:
Post a Comment