Knights to Infinity

According to OEIS , the number of squares $a(n)$ that can be reached by a knight in $n$ or fewer moves is $a(n) \; = \; 5 - 6n + 14n^2 \hspace{1cm} n \ge 4$ There is a slight adjustment to this formula for $n=0,1,2,3$ . Thus the number of squares that can be reached in precisely $n$ moves is $b(n) \; = \; a(n) - a(n-1) \; = \ 14(2n-1) - 6 \; = \; 28n - 20 \hspace{1cm} n \ge 5$ The number of squares that can be reached after $n$ moves is equal to $c(n) \; =\; \sum_{j=0}^{\lfloor \tfrac12n\rfloor} b(n-2j)$ To see this, any square that takes exactly $n - 2j$ moves to reach can be reached after $n$ moves; take $n-2j$ moves to get there, and then jump to a square and back again a total of $j$ times. Obviously, squares that take exactly $n - 2j-1$ moves to reach cannot be reached in $n$ moves, since they will be of the wrong colour. Thus $c(n) \; \sim \; \sum_{j=0}^{\lfloor \tfrac12n\rfloor} (28n-56j - 20) \; \sim \; 28n\lfloor \tfrac12n\rfloor - 28\lfloor \tfrac12n\rfloor\big(\lfloor \tfrac12n \rfloor + 1\big) - 20\lfloor \tfrac12n \rfloor \; \sim \; 7n^2 \hspace{2cm} n \to \infty$ making the answer $7+2=\boxed{9}$ .

---

To save quoting from OEIS, here is a direct proof of the formula for $b(n)$ . After playing around a bit, a clear pattern emerges as to which squares can be covered when.

This is the general pattern. The black squares are those that can be reached in fewer than $n$ moves, and the red squares are the ones that can be reached in $n$ moves, but not fewer than $n$ , (so that $b(n)$ is the number of red squares. This pattern occurs for all $n \ge 5$ . The overall pattern is a "fringed octagon", where the outermost fringe describes an octagon with $n+1$ red squares (interspersed with gaps) on each horizontal and vertical side, and $n+1$ red squares on each diagonal side. The above picture is the pattern for $n=15$ .

It is easy to see that any of the white squares within the outer red/white fringe can be reached from one of the red squares in one knight's move. In the move from the pattern for $n$ to the pattern for $n+1$ , all the red squares in the outer fringe will turn black, and all the white squares in the outer fringe will turn red. In addition, it is clear that knight's moves from the red squares outwards will create an additional red/white fringe in the $n+1$ pattern as required. That this pattern is correct for all $n \ge 5$ is therefore shown by induction.

In this pattern, counting the columns from left to right:

• there are $4$ columns containing $n+1,n+2,n+3,n+4$ red squares each,
• then there are $n-3$ columns each containing $6$ red squares,
• then there are $2n-1$ columns each containing $4$ red squares,
• then there are $n-3$ columns each containing $6$ red squares,
• finally there are $4$ columns containing $n+4,n+3,n+2,n+1$ red squares,

and so we deduce that $b(n) \; = \; 2\big[(n+1)+(n+2)+(n+3)+(n+4) + 6(n-3)\big] + 4(2n-1) \; = \; 28n - 20 \hspace{2cm} n \ge 5 \;.$ Direct calculation shows that $b(1) = 8$ , $b(2) = 32$ , $b(3) = 68$ and $b(4) = 96$ .

Note: This is not a solution (more of an asymptotic hack), and I'd encourage people to work out the problem in nicer ways (i.e., via induction ).

When a knight moves "optimally" away from its original square, it moves about $\sqrt{1^2+2^2} = \sqrt{5}$ units per move. When it moves "unoptimally" away (in a ~straight line) from its original square, it moves about $2$ units per move (i.e., up-right followed by up-left).

The knight can then move around in this "blob" (something like a circle, but really closer to an octagon) that has radius at most $\sqrt 5 n$ and at least $2n.$ However, it can only move around to half of the squares, due to even/odd parity.

So, the number of square it can move to in $n$ moves is between $2\pi n^2 \approx 6.28n^2$ and $2.5 \pi n^2 \approx 7.85 n^2.$ However, you can prove that the number of reachable squares should be quadratic in $n$ with integer coefficients, so the asymptotic behavior is $7n^2.$

Now fit an exponent to your curve. Low and behold 7*n^2 works pretty well.

Taking n=1, we get that the knight can go to 8 different places.
Taking n=2,we get that the knight can go to 16 different places.
This you can know by drawing the diagrams. .
So, $a 1^{b}=8$ So, $a=8$ .
Now, taking n=2, a=8, $8\times 2^{b}=16$ So, $b=1$ Now a+b=8+1=9

You can see in the picture how it looks for $n=10$

the yellow line includes the pattern that we get for $n=8$

summing top to bottom we get: $sum(10)-sum(8)=10+11+12+13+6*6+17*4+6*6+13+12+11+10=232$

or in the more general case

$sum(n)-sum(n-2)=2*[4n+6+(n-4)*6] + (2n-3)*4= 28n - 48$

which goes like $28n$ as n goes to infinity.

So the difference is a linear function of n.

It implies that $sum(n)=a*n^2+b*n+c$ As n goes to infinity this sum(n) goes like $a*n^2$

now we know that $a*n^2-a*(n-2)^2=28n$

Which means

$4an-4a=28n$

$a(4n-4)=28n$

$a=7$

it means that $sum(n)$ goes like $7*n^2$ which means $a=7$ and $b = 2$ or in other words $\boxed{9}$