Thread: 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

I'd say infinitely many since it is possible to go up-down-up-down-up-down-...

Originally Posted by Laurent

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

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

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.

Originally Posted by Plato

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 where . It goes up a few steps, and then to . From there, it goes either up or down (but not both) and then to . And so on, until where (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 's, you can deduce the trajectory.
The nice thing is: there is no constraint on the 's, except that they belong to and that and are fixed.
As a consequence, there are exactly paths satisfying the asumptions: number of choices of . The same reasoning works for any number instead of 4 or 3.

thank you so much!

How would this change if I had to go through both (2,3) and (3,2) on the way up to (4,3)?

Originally Posted by kelli_rie

How would this change if I had to go through both (2,3) and (3,2) on the way up to (4,3)?

Then and would be fixed, so it remains to choose and : possible paths.

Ah ha! Thanks, now I see exactly what you're doing!

Originally Posted by Laurent

Then and would be fixed, so it remains to choose and : possible paths.

In fact I was wrong... "The walks goes through (3,2) and (2,3)" doesn't mean that and : this is only one possibility.
Since 3 is the top row, we notice that the possibilities are:
- and (because the walk goes through (2,3)) and must be to go through (3,2) and avoid backtracking;
- and and ;
- and and is anything.
- and and .
So that there are possibilities to choose . And there are choices for , so that the final answer is .