OFFSET
1,2
COMMENTS
a(n) is the minimum k such that an n X n grid can be colored with positive integers less than or equal to k, and the taxicab distance between each pair of cells containing the same value v is greater than v.
The sequence converges to 15, because the packing chromatic number of the infinite square grid is 15. See links.
a(11) <= 12, a(12) <= 12, a(13) <= 13, a(14) <= 13 and a(15) <= 14. - Martin Ehrenstein, May 01 2023
LINKS
Martin Ehrenstein, Example grids illustrating terms and bounds for n = 9..16
Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, John M. Harris, and Douglas F. Rall, Broadcast Chromatic Numbers of Graphs, Ars Combinatoria, 86 (2008), 33-49.
Kevin Hartnett, The Number 15 Describes the Secret Limit of an Infinite Grid, Quanta Magazine, Apr 20 2023.
Robert C. Lyons, Python program that calculates the sequence.
Bernardo Subercaseaux and Marijn J. H. Heule, The Packing Chromatic Number of the Infinite Square Grid is 15, arXiv:2301.09757 [cs.DM], 2023.
EXAMPLE
In the following 2 X 2 grid, the maximum value is 3, and the distance between the two cells containing 1 is 2:
1 2
3 1
In the following 3 X 3 grid, the maximum value is 4, and the distance between the two cells containing 3 is 4:
2 1 3
1 4 1
3 1 2
In the following 4 X 4 grid, the maximum value is 5, and the distance between each pair of cells containing 3 is 4:
1 2 1 3
3 1 4 1
1 5 1 2
2 1 3 1
In the following 5 X 5 grid, the maximum value is 7, and the distance between each pair of cells containing 3 is greater than 3:
1 2 1 3 1
3 1 4 1 2
1 5 1 6 1
2 1 7 1 3
1 3 1 2 1
In the following 6 X 6 grid, the maximum value is 8, and the distance between the two cells containing 5 is 6:
1 2 1 3 1 2
3 1 4 1 5 1
1 6 1 2 1 3
2 1 3 1 7 1
1 5 1 8 1 2
3 1 2 1 3 1
In the following 7 X 7 grid, the maximum value is 9, and the distance between the two cells containing 7 is 8:
1 2 1 3 1 2 1
3 1 4 1 5 1 3
1 6 1 2 1 7 1
2 1 3 1 8 1 2
1 5 1 9 1 3 1
3 1 2 1 4 1 5
1 7 1 3 1 2 1
In the following 8 X 8 grid, the maximum value is 9, and the distance between the two cells containing 7 is 8:
1 2 1 3 1 2 1 3
3 1 4 1 5 1 6 1
1 7 1 2 1 3 1 2
2 1 3 1 8 1 4 1
1 5 1 9 1 2 1 3
3 1 2 1 3 1 7 1
1 6 1 4 1 5 1 2
2 1 3 1 2 1 3 6
PROG
(Python) # See link.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Robert C. Lyons, Apr 25 2023
EXTENSIONS
a(9)-a(10) from Martin Ehrenstein, May 01 2023
STATUS
approved