The longest induced path in the n×n grid

A snake in a graph is an induced path. Let a(n) be the largest number of cells of a snake in the n × n grid. We prove that a(n) = (2n2 − 4n + c(n))/3, where c(n) is an explicit constant depending only on n modulo 6, for every n ≥ 13 except n = 15; with exhaustive values for n ≤ 18 this determines a(n) for every n. Previously a(n) was known for n ≤ 17, and a(n) = 2n2/3 + O(n). Equivalently, if cells of an n × n board are blocked so that the shortest path between two free cells is as long as possible, that path has a(n) − 1 steps; on the 19 × 19 board of Go it has 226. The upper bound rests on an exact waste identity and on finite transfer-matrix certificates for the boundary strips and the corners of the board, checked by computer; the lower bound is an explicit family of snakes into which six rows and six columns can be inserted any number of times. Version 1.0.1 corrects the proof of Lemma 5.2(3), on which the constructions of Theorems 5.3 and 5.4 rely: the decomposition of the arms of the band designs is now derived from the hypotheses, and the threshold k0 is explicit (8, 8, 8, 8, 8, 10 and 14 for the seven designs, within the range of the finite checks); the exact computation on the arms is added to condition C9 of the reproduction archive. Lemma 2.1 is stated for distinct endpoints and n ≥ 2, with a note on n = 1 below Table 4. The statements of Theorems 1.1, 5.3 and 5.4, all values, and all other parts of the paper are unchanged. 2020 Mathematics Subject Classification: Primary 05C38; Secondary 05C12, 05C35, 68V05. Files: the paper (PDF, 21 pages), its LaTeX source, a README, and a reproduction archive with the programs, certificates, data and recorded outputs of every computer-checked condition of Appendix A (C1 to C11), one folder per condition, each with a script that re-runs its checks.