All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
King on the run (Posted on 2016-06-01) Difficulty: 3 of 5
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?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer assisted solution | Comment 1 of 5
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information