Results 1 to 11 of 11

Math Help - Probability Grid

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    12

    Probability Grid

    Hi, I've got a problem with a 4x3 grid. I can move right and vertically only. I need to know how many different ways I can go from (0,0) to (4,3). I know how to do it if only going right and up. But in this problem I can go right, up, or down.

    Thanks!

    Kelli
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    I'd say infinitely many since it is possible to go up-down-up-down-up-down-...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Laurent View Post
    I'd say infinitely many since it is possible to go up-down-up-down-up-down-...
    what if you had to alternate vertical and horizontal movements? and of course, you can only move to the right, so you can't go around the same square infinitely, for instance
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    Posts
    12
    Yeah, I'm having trouble understanding what the question is saying. All it says is right and vertical. How about we pretend you can't backtrack. Could anyone figure that out? I'm pretty sure vertical means up and down because another part of the question asks how many possible paths are there if you must pass through points (2,3) and (3,2). Thanks everyone!

    Kelli
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    In the usual ‘city-block’ problem we say that one can move east or north.
    In the problem, we would move 4 blocks east and 3 blocks north.
    So how many ways can we arrange the string “EEEENNN”?

    Now in the present problem let’s do add no backtracks.
    One possibility is 4 E’s, 1 S and 4 N’s: ex. ENESENNEN.
    But note there are restrictions. No string can begin or end with S.
    Moreover, S cannot appear next to an N.

    The most extreme case: NNNESSSENNNESSSENNN.

    The job is to count all these possiblites.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Plato View Post
    Now in the present problem let’s do add no backtracks.
    One possibility is 4 E’s, 1 S and 4 N’s: ex. ENESENNEN.
    But note there are restrictions. No string can begin or end with S.
    Moreover, S cannot appear next to an N.

    The most extreme case: NNNESSSENNNESSSENNN.

    The job is to count all these possiblites.
    Here's another way to code the problem. In fact, it is equivalent (under the no-backtrack condition) to be given the whole trajectory (sequence of N,S,E) or only the arrival points in each new column.
    The walk starts at (0,n_0) where n_0=0. It goes up a few steps, and then to (1,n_1). From there, it goes either up or down (but not both) and then to (2,n_2). And so on, until (5,n_5) where n_5=3 (I add a column for the sake of simplifying the presentation, but the walk doesn't go up/down in this new column so it doesn't affect the computation). If you know the n_i's, you can deduce the trajectory.
    The nice thing is: there is no constraint on the n_i's, except that they belong to \{0,1,2,3\} and that n_0 and n_5 are fixed.
    As a consequence, there are exactly 4^4 paths satisfying the asumptions: number of choices of n_1,n_2,n_3,n_4. The same reasoning works for any number instead of 4 or 3.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2008
    Posts
    12
    thank you so much!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Oct 2008
    Posts
    12
    How would this change if I had to go through both (2,3) and (3,2) on the way up to (4,3)?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by kelli_rie View Post
    How would this change if I had to go through both (2,3) and (3,2) on the way up to (4,3)?
    Then n_2 and n_3 would be fixed, so it remains to choose n_1 and n_4: 4^2=16 possible paths.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Oct 2008
    Posts
    12
    Ah ha! Thanks, now I see exactly what you're doing!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Laurent View Post
    Then n_2 and n_3 would be fixed, so it remains to choose n_1 and n_4: 4^2=16 possible paths.
    In fact I was wrong... "The walks goes through (3,2) and (2,3)" doesn't mean that n_3=2 and n_2=3: this is only one possibility.
    Since 3 is the top row, we notice that the possibilities are:
    - n_2\leq 2 and n_3=3 (because the walk goes through (2,3)) and n_4 must be \leq 2 to go through (3,2) and avoid backtracking;
    - n_2=3 and n_3=3 and n_4\leq 2;
    - n_2=3 and n_3=2 and n_4 is anything.
    - n_2=3 and n_3\leq 1 and n_4\geq2.
    So that there are 3\cdot 1\cdot 3 + 1\cdot 1\cdot 3 + 1\cdot 1\cdot 4+1\cdot1\cdot 2=18 possibilities to choose (n_2,n_3,n_4). And there are 4 choices for n_1, so that the final answer is 18\cdot 4=72.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Grid Distances
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: February 20th 2010, 12:53 PM
  2. Ten by Ten grid
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2009, 03:50 PM
  3. nxn grid problem.
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: October 31st 2009, 08:00 AM
  4. Help With A Grid
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 31st 2008, 01:34 PM
  5. grid dots
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 17th 2007, 10:13 AM

Search Tags


/mathhelpforum @mathhelpforum