1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of ways to move the king across chess board

  1. Dec 7, 2015 #1
    1. The problem statement, all variables and given/known data
    On how many ways the king can be moved from the bottom left field to the upper right field on the chess board such that such that for every move it is closer to the upper right field?

    2. Relevant equations

    3. The attempt at a solution
    I assume it is diagonal path of [itex]8\times 8[/itex] matrix.
    Is there some strict method in combinatorics (exclusion-inclusion, generating functions,...) to prove this?
  2. jcsd
  3. Dec 7, 2015 #2
    There's probably more than one way to attack this problem, but I would start with the observation that without diagonal moves, it will take 14 moves, 7 up and 7 across in any order. Then, each time an up is followed by an across or an across is followed by an up, then the move can be replaced by a diagonal move - but only one for each up/across, across/up pair.
    If you can program, this would not be difficult to code.

    Alternatively: You are computing F(7,7) by walking through each step with an up, diagonal, or across move as follows:

    F(X,Y) = F(Y,X)

    For any F(X,Y) where X>0 and Y>0:
    F(X,Y) = F(X-1,Y) + F(X-1,Y-1) + F(X,Y-1)

    F(X,0) = F(0,Y) = 1

    F(1,1) = F(0,1) + F(0,0) + F(1,0) = 1+1+1 = 3
    F(1,2) = F(0,2) + F(0,1) + F(1,1) = 1+1+3 = 5
    F(2,1) = F(1,2) = 5
    F(2,2) = F(2,1) + F(1,1) + F(1,2) = 5+3+5 = 13
    F(3,1) = ...
    F(7,7) = F(7,6)+F(6,6)+F(6,7) = ...

    Not counting the F(X,0) = F(0,Y) = 1, this would require 49 computations. And can also be coded.
  4. Dec 7, 2015 #3


    User Avatar
    Homework Helper
    Gold Member

    Does 'upper right field' mean 1step beyond the diagonal? On the diagonal?mifncan do one can do the other, but is the question that?
    At each step you have 3 choices, if that helps.
    I guess you could do it for first row, then second and see what pattern suggests itself.
  5. Dec 7, 2015 #4
    Upper right field is the top right field of the entire board (the king is at the bottom left).
  6. Dec 7, 2015 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I would consider combinations of ##r, u, d## with the appropriate constraints.
  7. Dec 7, 2015 #6


    User Avatar
    Science Advisor
    Homework Helper

    At each step you have 3 choices, until your reach the last column or last row. From then you have only one choice.
  8. Dec 8, 2015 #7


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    A general approach to the problem involves recurrence relations and generating functions. Are you familiar with these, gruba?
    That said, it doesn't make it much easier. You end up having to find the coefficient of x7y7 in the expansion of (1-x-y-xy)-1.
  9. Dec 8, 2015 #8
    Could you elaborate on your method with recurrences and generation functions? How did you get the expansion [itex](1-x-y-xy)^{-1}[/itex]?
  10. Dec 8, 2015 #9


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    First, consider the more general question of moving from one corner to the far corner on a r x s rectangle. Let the number of ways of doing this be Nr,s. Can you see how to write Nr,s as a combination of Nr,s-1, Nr-1,s and Nr-1,s-1? That's called a recurrence relation.
    We need to supply boundary conditions. I would use:
    The relation applies for all r, s >=1
    N0,0=1, N0,s=0 for s>0, Nr,0=0 for r>0. You can check this produces the right numbers for r=1 etc.
    The next step is to define a generating function ##G(x,y)=\Sigma_{r=1,s=1}N_{r,s}x^ry^s##.
    Multiplying through the recurrence relation by xrys and summing produces an equation for the generating function. A little careful working through the boundary parts of the sums leads to G=xy(1-x-y-xy)-1.
    If we then expand G as a power series in x and y we can read off the values of Nr,s as the coefficients.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted