I'd say infinitely many since it is possible to go up-down-up-down-up-down-...
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
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.
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.
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 .