Minor pieces on a chessboard

[BMAD]

Consider a an infinite chessboard.

How many squares can a knight reach after precisely n moves?

How about a bishop?

[bonanova]

I interpret the question to ask the number m of additional and unvisited squares that

are within reach of a knight after n moves. Summing these numbers gives the number

of squares a knight can reach with n moves or fewer. I do not double-count any squares.

Note that interpreting m as an incremental quantity will make it linear in n.

The partial sums will be quadratic in n.

Here are the squares that are first reached for n=1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 moves, color coded.

It's easier to count the moves by looking at even and odd n, respectively:

The numbers of dots in the colored regions are 8, 32, 68, 96, 120, 148, 176, 204, 232, and 260.

This discloses the general result that the number of additional squares increases by 28 with each move.

The anomalous values of m are

m(2) = 32 instead of 36, dark green

m(3) = 68 instead of 64, dark blue, and

m(4) = 96 instead of 92, orange.

These are the moves numbers for which the knight has unvisited squares back toward the original square.

For larger numbers, concentric regions for even and odd moves do not intermingle.

For these values of n,

m(n) = 4(7n-5).

Again, this is the number of squares that move n adds to the total.

Repeating the solution for a bishop:

A bishop on an infinite board can reach every square of its color in two moves.

The cardinality of that set of squares is aleph null.

That is, the black (or white) squares on an infinite chessboard are countable.

[bonanova]

Interpreting the question to mean what is the greatest number of squares a knight can reach after n moves,

A Knight can reach 8 + 7(n-1) squares.

A Bishop can reach a countably infinite number of squares on first move.

If infinity were a number we could say after n moves it can reach infinity + (infinity-1)(n-1) squares.

But infinity is not a number.

So we can just say a Bishop can reach a countably infinite number of squares after precisely n moves.

That is, Aleph null.

[BobbyGo]

For all cases larger than 2 moves, the total number of unique squares that a knight can end up on after n moves is equal to 7n

² + 4n + 1. (This equation's results for cases 1 and 2 are four larger than the actual number of squares the knight can end up at. Not sure how to balance.)

The bishop problem is a bit of fun. If the bishop can move to an infinite number of spaces on the first move (infinity times 4, if you want to count all diagonals separately), then on the second move it can reach an infinite number of spaces for each of the infinite spaces from the first move. Additionally, after the second move, no additional spaces can be reached; all the possible spaces that the bishop can reach have already been counted.

So after the first move, on an infinite chess board, a bishop can uniquely reach infinity² spaces... all while only using half of the infinite board!

[BMAD]

Interpreting the question to mean what is the greatest number of squares a knight can reach after n moves,

A Knight can reach 8 + 7(n-1) squares.

A Bishop can reach a countably infinite number of squares on first move.

If infinity were a number we could say after n moves it can reach infinity + (infinity-1)(n-1) squares.

But infinity is not a number.

So we can just say a Bishop can reach a countably infinite number of squares after precisely n moves.

That is, Aleph null.

For all cases larger than 2 moves, the total number of unique squares that a knight can end up on after n moves is equal to 7n

² + 4n + 1. (This equation's results for cases 1 and 2 are four larger than the actual number of squares the knight can end up at. Not sure how to balance.)

The bishop problem is a bit of fun. If the bishop can move to an infinite number of spaces on the first move (infinity times 4, if you want to count all diagonals separately), then on the second move it can reach an infinite number of spaces for each of the infinite spaces from the first move. Additionally, after the second move, no additional spaces can be reached; all the possible spaces that the bishop can reach have already been counted.

So after the first move, on an infinite chess board, a bishop can uniquely reach infinity² spaces... all while only using half of the infinite board!

Both are well said but there seems to be disagreement as to the knight moves; however the balancing issue that BobbyGo references may be an issue resolved by Bonanova's equation.

Edited April 4, 2014 by BMAD

[bonanova]

my knight answer is wrong. in 2 moves a bishop can reach all the same-color squares, a countably infinite number.