I The answer is 15! What is the problem?

  • I
  • Thread starter Thread starter Astronuc
  • Start date Start date
AI Thread Summary
The "packing coloring" problem explores how to fill an infinite grid with numbers while ensuring identical numbers maintain a specified distance apart, measured by taxicab distance. A recent computer-assisted proof has established that the minimum number of numbers required to solve this problem is 15, a significant finding that refines previous estimates. Initially, researchers, including Wayne Goddard, demonstrated that 22 numbers could solve the problem, while five was insufficient, indicating the true solution lies between these two figures. The discussion also touches on the reliability of algorithms in mathematical proofs, highlighting skepticism about their accuracy. This exploration underscores the complexity and intrigue of combinatorial mathematics.
Astronuc
Staff Emeritus
Science Advisor
Gold Member
Messages
22,352
Reaction score
7,173

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
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?
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...

Similar threads

Replies
50
Views
6K
2
Replies
71
Views
12K
4
Replies
175
Views
25K
Replies
1
Views
3K
Replies
1
Views
3K
Replies
1
Views
2K
Replies
1
Views
3K
Replies
16
Views
5K
Replies
1
Views
3K
Back
Top