Problem of the Month (February 2016)

Consider a chess piece that has some possible moves that are not necessarily symmetric, each possible move being one square horizontally, vertically, diagonally, a knight move. What is the longest loop that piece can make on an n×m chessboard, visiting each square no more than once? How does the size of the longest loop change as n, m, or both approach infinity?

Up to symmetry, there are 17 different collections of such 3 moves, where loops of length more than 2 are possible. The longest-known loops (and paths) are shown for each of these below. Can you extend these results? Can you find any patterns? What about collections of 4 such moves? Which n×m chessboards can be completely visited?

ANSWERS

Paths

	1	2	3	4	5	6	7	…	n
1	1	1	1	1	1	1	1	…	1
2	2	2	2	2	2	2	2	…	2
3	3	6	9	12	15	18	21	…	3n
4	4	7	10	13	16	19	22	…	3n+1
5	5	8	11	14	17	20	23	…	3n+2
6	6	12	15	21	26	32	38	…	6n–4
7	7	13	19	25	31	37	43	…	6n+1
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋱	⋮
n	n	3⌊n/3⌋+n	4n–3–3⌊(n+1)/3⌋	?	?	?	?	…	?

Loops

	1	2	3	4	5	6	7	…	n
1	0	0	0	0	0	0	0	…	0
2	0	0	0	0	0	0	0	…	0
3	0	3	3	3	3	3	3	…	3
4	0	3	3	3	3	3	3	…	3
5	0	3	6	6	6	6	6	…	6
6	0	3	9	15	21	27	33	…	6n–9
7	0	3	12	18	24	30	36	…	6n–6
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋱	⋮
n	0	3	3n–9	?	?	?	?	…	?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 2 2 2 2 2 2 … 2
3 3 6 9 12 15 18 21 … 3n
4 4 7 10 13 16 19 22 … 3n+1
5 5 8 11 14 17 20 23 … 3n+2
6 6 9 18 21 27 33 38 … ?
7 7 10 19 25 31 37 43 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n n+3 6⌊n/3⌋+n ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 6 6 6 6 6 … 6
4 0 0 6 6 6 6 6 … 6
5 0 0 6 6 12 12 12 … 12
6 0 0 6 12 18 24 30 … 6n–12
7 0 0 6 18 24 30 36 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 6 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 4 6 8 10 12 14 … 2n
3 3 5 7 9 11 13 15 … 2n+1
4 4 6 12 14 18 22 25 … ?
5 5 7 13 17 21 25 29 … ?
6 6 8 18 22 26 34 38 … ?
7 7 9 19 25 31 37 43 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n n+2 4⌊n/2⌋+n ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 4 4 4 4 4 … 4
3 0 0 4 4 4 4 4 … 4
4 0 0 4 8 12 16 20 … 4n–8
5 0 0 4 12 16 20 24 … 4n–4
6 0 0 4 16 20 28 32 … ?
7 0 0 4 20 24 32 36 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 4 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 2 3 4 5 6 7 … n
2 2 3 4 5 6 7 8 … n+1
3 3 6 9 12 15 18 21 … 3n
4 4 8 12 16 20 24 28 … 4n
5 5 10 15 20 25 30 35 … 5n
6 6 11 18 24 30 35 42 … ?
7 7 14 21 28 35 42 ? … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n 2n–⌊(n+2)/4⌋
+⌊(n+1)/4⌋ 3n 4n ? ? ? … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 4 4 4 4 4 4 … 4
4 0 4 8 12 16 20 24 … 4n–4
5 0 4 8 12 16 20 24 … 4n–4
6 0 4 12 20 24 28 36 … 4n+4
7 0 4 16 28 32 40 ? … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 4 ? ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 2 3 4 5 6 7 … n
2 2 4 6 8 10 12 14 … 2n
3 3 6 9 12 15 18 21 … 3n
4 4 8 12 16 20 24 28 … 4n
5 5 10 15 20 25 30 35 … 5n
6 6 12 18 24 30 36 42 … 6n
7 7 14 21 28 35 42 49 … 7n
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n 2n 3n 4n 5n 6n 7n … n²

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 3 3 3 3 3 3 … 3
3 0 3 6 9 12 15 18 … 3n–3
4 0 3 9 12 15 21 24 … ?
5 0 3 12 15 18 27 30 … ?
6 0 3 15 21 27 33 39 … ?
7 0 3 18 24 30 39 ? … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 3 3n–3 * ? 6n–3 ? … ?
* = 3n+3⌊(n–3)/3⌋

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 2 4 4 6 6 8 … 2⌊(n+1)/2⌋
3 3 6 9 12 15 18 21 … 3n
4 4 7 10 13 17 21 24 … ?
5 5 8 15 20 25 30 35 … 5n
6 6 9 17 23 28 34 42 … ?
7 7 10 18 26 33 40 45 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n n+3 * ? ? ? ? … ?
* = 3n–2+2⌊(n+1)/3⌋–2⌊n/3⌋

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 8 8 8 8 8 … 8
4 0 0 8 8 8 8 8 … 8
5 0 0 8 8 16 16 24 … 8⌊(n-1)/2⌋
6 0 0 8 16 24 32 40 … ?
7 0 0 8 16 24 32 ? … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 8 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 4 6 8 10 12 14 … 2n
3 3 5 7 9 11 13 15 … 2n+1
4 4 6 12 16 18 24 28 … 4n–2⌊(n+1)/3⌋+2⌊n/3⌋
5 5 7 13 17 21 25 29 … 4n–2⌊(n+1)/3⌋+2⌊n/3⌋+1
6 6 8 18 24 28 36 42 … 6n–2⌊(n+1)/3⌋+2⌊n/3⌋
7 7 9 19 25 31 37 ? … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n n+2 4⌊n/2⌋+n 6⌊n/2⌋+n ? 10⌊n/2⌋+n 12⌊n/2⌋+n … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 6 6 6 6 6 … 6
3 0 0 6 6 6 6 6 … 6
4 0 0 6 12 12 18 24 … ?
5 0 0 6 12 18 24 24 … ?
6 0 0 6 18 24 30 36 … ?
7 0 0 6 24 30 36 42 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 6 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 2 4 4 6 6 8 … 2⌊(n+1)/2⌋
3 3 3 5 5 7 7 9 … 2⌊(n+1)/2⌋+1
4 4 4 8 8 12 12 16 … 4⌊(n+1)/2⌋
5 5 5 9 9 13 13 17 … 4⌊(n+1)/2⌋+1
6 6 6 12 12 18 18 24 … 6⌊(n+1)/2⌋
7 7 7 13 13 19 19 25 … 6⌊(n+1)/2⌋+1
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n n 2⌊n/2⌋+n 2⌊n/2⌋+n 4⌊n/2⌋+n 4⌊n/2⌋+n 6⌊n/2⌋+n … ⌊(n²+1)/2⌋

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 4 4 4 4 4 … 4
3 0 0 4 4 4 4 4 … 4
4 0 0 4 4 8 8 12 … 4⌊(n-1)/2⌋
5 0 0 4 4 12 12 16 … 4⌊(n+1)/2⌋
6 0 0 4 4 16 16 20 … ?
7 0 0 4 4 16 16 24 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 4 4 * * ? … ?
* = 4n–4⌊(n+5)/4⌋

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 4 6 8 10 12 14 … 2n
3 3 6 9 12 15 18 21 … 3n
4 4 7 11 15 18 22 26 … ?
5 5 10 15 20 25 30 35 … 5n
6 6 11 17 24 30 36 41 … ?
7 7 14 21 28 35 42 49 … 7n
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n * ** ? ? ? ? … ?
* = 2n–⌊(n–1)/5⌋+⌊(n–2)/5⌋–⌊(n–4)/5⌋+⌊(n–5)/5⌋
** = 3n–⌊(n–1)/5⌋+⌊(n–2)/5⌋–⌊(n–4)/5⌋+⌊(n–5)/5⌋

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 5 5 5 5 5 5 … 5
4 0 5 5 5 5 5 5 … 5
5 0 5 10 15 20 25 30 … 5n–5
6 0 5 15 20 25 30 35 … 5n
7 0 5 15 25 30 35 45 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 5 ? ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 4 6 8 10 12 14 … 2n
3 3 5 7 9 11 13 15 … 2n+1
4 4 8 12 16 20 24 28 … 4n
5 5 9 13 17 21 25 29 … 4n+1
6 6 12 18 24 30 36 42 … 6n
7 7 13 19 25 31 37 43 … 6n+1
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n 2⌊n/2⌋+n 4⌊n/2⌋+n 6⌊n/2⌋+n 8⌊n/2⌋+n 10⌊n/2⌋+n 12⌊n/2⌋+n … 2(n–1)⌊n/2⌋+n

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 4 4 4 4 4 4 … 4
3 0 4 4 4 4 4 4 … 4
4 0 4 8 12 16 20 24 … 4n–4
5 0 4 12 16 20 24 28 … 4n
6 0 4 16 20 24 32 36 … ?
7 0 4 16 24 28 36 40 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 4 4n–8 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 2 2 2 2 2 2 2 … 2
3 3 6 9 12 15 18 21 … 3n
4 4 7 10 13 16 19 22 … 3n+1
5 5 8 11 14 17 20 23 … 3n+2
6 6 12 18 24 30 36 42 … 6n
7 7 13 19 25 31 37 43 … 6n+1
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n n 3⌊n/3⌋+n 6⌊n/3⌋+n 9⌊n/3⌋+n 12⌊n/3⌋+n 15⌊n/3⌋+n 18⌊n/3⌋+n … 3(n-1)⌊n/3⌋+n

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 6 6 6 6 6 6 … 6
4 0 6 6 6 6 6 6 … 6
5 0 6 6 6 6 6 6 … 6
6 0 6 12 18 24 30 36 … 6n–6
7 0 6 18 24 30 36 42 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 6 ? ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 1 2 4 6 8 10 12 … 2n–2
3 1 4 7 10 13 16 19 … 3n–2
4 1 6 10 14 17 20 25 … ?
5 1 8 13 17 19 26 33 … ?
6 1 10 16 20 26 30 36 … ?
7 1 12 19 25 33 36 43 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 1 2n–2 3n–2 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 5 5 5 5 5 … 5
4 0 0 5 5 5 5 5 … 5
5 0 0 5 5 10 15 20 … ?
6 0 0 5 5 15 20 25 … ?
7 0 0 5 5 20 25 30 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 5 5 ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 1 2 2 2 2 2 2 … 2
3 1 4 9 10 13 18 19 … 3n–2+2⌊n/3⌋–2⌊(n-1)/3⌋
4 1 6 10 12 15 19 21 … ?
5 1 8 11 14 17 20 23 … ?
6 1 10 15 19 23 33 37 … ?
7 1 12 19 21 30 36 39 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 1 2n–2 3n–2 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 0 9 9 9 9 … 9
4 0 0 9 9 9 9 9 … 9
5 0 0 9 9 9 18 18 … ?
6 0 0 9 9 18 27 27 … ?
7 0 0 9 9 27 27 36 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 9 9 ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 1 2 2 2 2 2 2 … 2
3 1 2 4 12 13 14 16 … 7⌊n/4⌋–⌊(n+1)/4⌋+n
4 1 2 6 13 14 15 18 … ?
5 1 2 11 14 17 20 23 … ?
6 1 2 14 21 25 26 36 … ?
7 1 2 15 25 27 30 39 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 1 2 ? ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 0 0 12 12 12 … 12
4 0 0 0 12 12 12 12 … 12
5 0 0 0 12 12 12 12 … 12
6 0 0 12 12 12 24 24 … ?
7 0 0 12 12 12 24 36 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 12 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 1 2 2 2 2 2 2 … 2
3 1 6 7 12 13 18 19 … 4⌊n/2⌋+n
4 1 7 9 13 15 19 21 … 2⌊n/2⌋+2n+1
5 1 8 11 14 17 20 23 … 3n+2
6 1 12 13 18 25 30 37 … ?
7 1 13 15 24 27 36 39 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 1 3⌊n/3⌋+n 2n+1 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 6 6 6 6 6 … 6
4 0 6 6 6 6 6 6 … 6
5 0 6 6 12 12 12 12 … 12
6 0 6 6 12 18 24 30 … ?
7 0 6 6 18 24 30 36 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 6 6 ? ? ? ? … ?

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 1 2 2 2 2 2 2 … 2
3 1 2 3 4 5 6 7 … n
4 1 2 4 5 6 7 8 … n+1
5 1 2 5 6 7 8 11 … 3⌊n/3⌋+2
6 1 2 6 7 8 11 13 … *
7 1 2 7 8 11 13 14 … **
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 1 2 n n+1 3⌊n/3⌋+2 * ** … ?
* = 2⌊n/3⌋+⌊(n-1)/3⌋+n
** = 2⌊(n+1)/3⌋+⌊(n+3)/3⌋+n

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 3 3 3 3 3 … 3
4 0 0 3 3 3 3 3 … 3
5 0 0 3 3 6 6 6 … 6
6 0 0 3 3 6 9 9 … ***
7 0 0 3 3 6 9 12 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 0 3 3 6 *** ? … ?
*** = 3⌊n/3⌋+3⌊(n-2)/3⌋

1 2 3 4 5 6 7 … n
1 1 1 1 1 1 1 1 … 1
2 1 2 2 2 2 2 2 … 2
3 1 4 7 10 13 16 19 … 3n–2
4 1 8 9 14 17 20 25 … ?
5 1 9 11 17 21 26 31 … ?
6 1 10 13 18 23 30 35 … ?
7 1 12 15 24 29 35 43 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 1 * 2n+1 ? ? ? ? … ?
* = ⌊(n+1)/4⌋+3⌊n/4⌋+n

1 2 3 4 5 6 7 … n
1 0 0 0 0 0 0 0 … 0
2 0 0 0 0 0 0 0 … 0
3 0 0 0 8 8 8 8 … 8
4 0 0 8 8 8 8 8 … 8
5 0 8 8 8 8 8 8 … 8
6 0 8 8 16 16 24 32 … ?
7 0 8 8 16 24 32 40 … ?
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮
n 0 8 8 ? ? ? ? … ?

There are 89 different sets of 4 different directions where loops might be possible, and where no move can be reversed. For some of those sets, here are the smallest grids they completely fill by loops containing all 4 different moves:

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 4/1/16.