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?
With 7 rows to go in 7 moves, each move must include a vertical component, and the only options are to go diagonally left, right or go straight down at each turn.
The table below lists, for the 8 possible starting positions that A might be, the number of ways of getting to the positions from left to right on the bottom row. If the number is a cube it's marked with a c, if a square it's marked with an s.
Only if the king started in a corner square do the conditions of the puzzle hold and points B and C are separated by 4 spaces (i.e., 3 intervening squares so you can count over 4 squares to get from one to the other).
column ways of getting to the different
for positions on bottom row
A
1 127 196s 189 133 70 27c 7 1sc
2 196s 316 329 259 160 77 28 7
3 189 329 386 356 266 161 77 27c
4 133 259 356 393 357 266 160 70
5 70 160 266 357 393 356 259 133
6 27c 77 161 266 356 386 329 189
7 7 28 77 160 259 329 316 196s
8 1sc 7 27c 70 133 189 196s 127
One of B and C is next to a corner square and the other is 2 away from the other bottom corner (one intervening square).
Starting at the bottom of the second column, here are the numbers of paths of length 5 to each other place on the board from point B:
A
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
30 46 44 30 15 5 1 0
90 140 140 100 55 20 5 0
230 354 356 250 140 50 14 0
340 520 540 380 225 80 25 0
395 595 625 430 260 90 30 0
255 380 409 280 175 60 21 0
B C D
Specifically, there are 60 ways of getting from point B to point C.
Of course the mirror image case would have the same total.
In the program below I obviously wrote the second part after seeing the results of the first part:
DefDbl A-Z
Dim crlf$, x, ways(), grid(8, 8), y
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For a = 1 To 8
ReDim ways(8)
x = a
moveKing 1
Text1.Text = Text1.Text & a & " "
For i = 1 To 8
Text1.Text = Text1.Text & Str(ways(i))
sr = Int(Sqr(ways(i)) + 0.5)
If sr * sr = ways(i) Then Text1.Text = Text1.Text & "s"
cr = Int(ways(i) ^ (1 / 3) + 0.5)
If cr * cr * cr = ways(i) Then Text1.Text = Text1.Text & "c"
Next
Text1.Text = Text1.Text & crlf
Next a
x = 2: y = 8
moveKingAgain 1
For y = 1 To 8
For x = 1 To 8
Text1.Text = Text1.Text & mform(grid(x, y), "###0")
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub moveKing(wh)
For newx = x - 1 To x + 1
oldx = x
x = newx
If newx > 0 And newx <= 8 Then
If wh = 7 Then
ways(x) = ways(x) + 1
Else
moveKing wh + 1
End If
End If
x = oldx
Next
End Sub
Sub moveKingAgain(wh)
For dx = -1 To 1
For dy = -1 To 1
If dx <> 0 Or dy <> 0 Then
oldx = x: oldy = y
x = x + dx: y = y + dy
If x > 0 And x <= 8 Then
If y > 0 And y <= 8 Then
If wh = 5 Then
grid(x, y) = grid(x, y) + 1
Else
moveKingAgain wh + 1
End If
End If
End If
x = oldx: y = oldy
End If
Next
Next
End Sub
Function mform$(x, t$)
a$ = Format$(x, t$)
If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
mform$ = a$
End Function
|
|
Posted by Charlie
on 2016-06-01 15:37:46 |
computer assisted solution
