A chess king starts at a position A in the top row of a standard chessboard. The number of paths of length 7 to a
position B in the bottom row is a perfect square, but not a perfect cube.
The number of paths of length 7 from A
to a position C in the bottom row is a perfect cube, but not a perfect square.
The number of paths of length 7 to a
position D is both a perfect square and a perfect cube.
How many chess king paths of length
5 are there from B to C?
It's quite a hard work to do this without a computer program.
Anyway the first part is more accesible than the second.
The fact that the king moves from the top row to the bottom row in 7 steps means that he must gain a row closer to the bottom row in every move.
If we suppose the king beginning at the left upper corner of the chessboard he can reach only 2 squares on the next inferior row in his first move. This => 2 possible paths.
From this 2 squares he can reach 3 squares in the successive inferior row. He can reach two of these squares from both squares of the superior row and the third square only from the second square of the superior row. Possible paths now have then grown to 5.
In the successive inferior row he can reach 4 squares from the 3 squares of the inmediate superior row...
So the area of possible paths is a "triangle" (because the king can extend right his path to one more square at any new row), and this triangle is compose of all the "reachable" squares. He can reach each square inside the "triangle" in a number of ways (paths) which is not difficult to determine. The whole is known as the Motzkin triangle.
1
1 1
2 2 1
4 5 3 1
9 12 9 4 1
21 30 25 14 5 1
51 75 69 44 20 6 1
126 196 188 133 70 27 7 1
Each number inside the triangle is the sum of some numbers of the inmediate superior row: just that numbers placed at a distance of one king move.
For ex., 126 (comes from 51 and 75) and is the numbers of possible paths from the upper corner to the square containing the 126 number. And the same works for each square inside the triangle.
From these numbers it's clear where positions B (196: perfect square), C (27: perfect cube) and D (1: both square and cube), are.
Between B and C there are 3 squares, corrisponding to at least four moves of the king.
But the king "choose" to reach C with a 5 moves walk.
Here begins the second part of the problem: know the number of possible 5-lenght paths from B to C.
The strategy to solve this is: see what squares are at distance 1 from C, that can be reach in four moves of the king. For each of those squares, do the same again (see what are the squares at distance 1 from them that can be reach in three moves of the king). Iterate again for two moves...
It's quite boring without a computer program. Fortunately we already know from Charlie's post that they are 60 possible paths.
Edited on June 2, 2016, 2:20 pm
|
|
Posted by armando
on 2016-06-02 12:27:12 |
Some sharings
