The answer is 15! What is the problem?

  • I
  • Thread starter Astronuc
  • Start date
In summary, the "packing coloring" problem seeks to fill an infinite grid with numbers while ensuring that identical numbers are not too close to each other. A new proof using computer assistance has determined that the minimum number of numbers needed is 15. This problem was initially proposed in 2002 and has since been proven by Wayne Goddard and his collaborators to require at least 22 numbers, but not as few as 5. The reliability of computer-assisted proofs has been called into question, but this new proof provides a simple and definitive answer to the problem.
  • #1
Astronuc
Staff Emeritus
Science Advisor
2023 Award
21,922
6,367

The Number 15 Describes the Secret Limit of an Infinite Grid​

https://www.quantamagazine.org/the-...he-secret-limit-of-an-infinite-grid-20230420/
The “packing coloring” problem asks how many numbers are needed to fill an infinite grid so that identical numbers never get too close to one another. A new computer-assisted proof finds a surprisingly straightforward answer.

In 2002, Wayne Goddard of Clemson University and some like-minded mathematicians were spitballing problems in combinatorics, trying to come up with new twists on the field’s mainstay questions about coloring maps given certain constraints.

Eventually they landed on a problem that starts with a grid, like a sheet of graph paper that goes on forever. The goal is to fill it with numbers. There’s just one constraint: The distance between each occurrence of the same number must be greater than the number itself. (Distance is measured by adding together the vertical and horizontal separation, a metric known as “taxicab” distance for the way it resembles moving on gridded urban streets.) A pair of 1s cannot occupy adjoining cells, which have a taxicab distance of 1, but they can be placed in directly diagonal cells, which have a distance of 2.

Initially, Goddard and his collaborators wanted to know whether it was even possible to fill an infinite grid with a finite set of numbers. But by the time he and his four collaborators published this “packing coloring” problem in the journal Ars Combinatoria in 2008, they had proved that it can be solved using 22 numbers. They also knew that there was no way it could be solved with only five numbers. That meant the actual answer to the problem — the minimum number of numbers needed — lay somewhere in between.

. . .
 
Mathematics news on Phys.org
  • #2
Poor dude who has to prove the correctness of those programs or calculations. I remember I, too, once used an algorithm to cover a finite number of exceptions, the exceptional simple Lie algebras, and months later I found a loophole. I checked manually all the cases the algorithm missed, so my general result remained true. But I do not trust such algorithms very much anymore. On the other hand, who really read and understood Wiles's proof?
 

Similar threads

  • Math Proof Training and Practice
3
Replies
71
Views
9K
  • High Energy, Nuclear, Particle Physics
Replies
19
Views
3K
  • Math Proof Training and Practice
6
Replies
175
Views
20K
Replies
1
Views
2K
  • Topology and Analysis
Replies
4
Views
2K
  • Math Proof Training and Practice
Replies
16
Views
5K
  • Biology and Chemistry Homework Help
Replies
2
Views
2K
  • Beyond the Standard Models
Replies
20
Views
10K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
Replies
13
Views
9K
Back
Top