Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial question

  1. Mar 16, 2013 #1
    A rabbit lives on an ordinary chessboard 8x8. The rabbit located over the cell (1.1) (lower left, the upper right corner is (8.8), the lower right corner is (8,1)). At any time the rabbit jumps either to the right or upwards.

    How many different ways can move the rabbit to reach the cell (3.4)?


    I have a problem here.I think all the moves in the chessboard is (64 C 8) like (n C k) combinations, but i can not think how to move from the cell (1.1) to (3.4) maybe someone can give me any suggestion how?
     
  2. jcsd
  3. Mar 17, 2013 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    To understand the problem - draw out the chessboard and locate the cells.
    Start tracing out possible paths manually - at some point you'll see a pattern emerge.
     
  4. Mar 17, 2013 #3
    but the there are a lot of paths... maybe we can find another way to find them with combinatorial types?
     
  5. Mar 17, 2013 #4

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Rabbit can only move right or upwards though - that severely restricts the number of paths.

    Of course there is a shortcut involving combinations etc.
    Your problem is how to find it - with the first step being to understand the problem.

    Another way: since you already solved how to get to (8,8) from (1,1) ... presumably you can do it for any size square board?
    So how does that work?
     
  6. Mar 17, 2013 #5
    i will try to estimate it and i will post the result here to find out if its correct
     
  7. Mar 17, 2013 #6
    i find it there are 10 ways to move right and up in the chessboard!
     
  8. Mar 17, 2013 #7

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    well done - how did you do that?
     
  9. Mar 18, 2013 #8

    ssd

    User Avatar

    The rabbit reaches (8,8) from (1,1) in 14C7= 14!/(7!.7!) ways, if the rabbit jumps only one square at a time.
    Call a rightward jump 'R' and upward jump 'U'. The answer is the total number of linear permutation of 7 R's and 7 U's.
    Similarly, to reach (m,n) the rabbit can move in
    (m+n-2)!/ [(m-1)!(n-1)!] ways.
     
    Last edited: Mar 18, 2013
  10. Mar 19, 2013 #9

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Well done.
    The answer is not so important as how you got to it.
    Also I hope you can see that you sometimes have to mess about with a problem for a bit before finding out the short, simple, way to do it. Don't be scared to start a problem without knowing how to get to the answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorial question
  1. Combinatorial Question (Replies: 17)

  2. Combinatorial Problem (Replies: 1)

Loading...