0
$\begingroup$

In x-y coordinate you start out at (0,0) and you want to get to (8,14) by either moving up or right only.

You can't move to any points that are both odd, e.g. (1,1), (1,3)... (3,1), (3,3) ... (7, 13).

So my strategy is to count all the possible paths and subtract out the path that hits the (odd,odd) coordinates.

Total path in this 8 by 14 grid is

$$\binom{22}{8} or \binom{22}{14}$$

Now I need to subtract the paths that hit (odd,odd) from that.

I'm not wrapping my head around how to count the number of ways you can hit the (odd,odd) coordinates. One way is to brute force it by counting # of ways to get to (1,1), (1,3)... etc. but that's really inefficient and I think I will accidentally double count a lot of the paths.

$\endgroup$
1
$\begingroup$

Hint: In two consecutive steps, you must move uu (up, up) or rr (right, right). Let's shorten uu to U and rr to R. Then you have to make a total of $4$ R's and $7$ U's.

$\endgroup$
  • $\begingroup$ Thank you, I "see" how that avoids the (odd,odd) coordinates now. $\endgroup$ – rawr rang Oct 30 '15 at 18:43
1
$\begingroup$

If you start writing down the number of possible paths, do you see a pattern developing? (The faintly shaded bits are examples of where there two positions from which you could arrive at one spot, so the numbers of paths from the start to each of those previous positions need to be added.)

enter image description here

$\endgroup$
  • $\begingroup$ So would this approach require filling in all the squares then until you reach the top right corner? Looks like you can add the piece to your left and to the bottom because that's the possible paths to get there, e.g. 2 + 1 = 3. So for (6,2) you would add 3+1=4. And then keep doing this for the rest of the squares till I reach (8,14)? $\endgroup$ – rawr rang Oct 30 '15 at 18:55
  • $\begingroup$ That’s the idea. How about trying it out and let us know if it gets you the right answer? (You may see familiar patterns develop, too, that could help you find an answer for a much bigger grid that wasn’t manageable by hand...) $\endgroup$ – Steve Kass Oct 31 '15 at 0:11
1
$\begingroup$

From the picture of Steve Kass it is obvious that once you are on any white square between two red ones the next step is predetermined and will not contribute to the multiplicity of the possible paths. If you are on the white square which up- and right-neighbours are white, you are in the situation (locally) as if there would be no restrictions (no red squares) on the grid.

Therefore, the number of paths would be still the same if you delete all the rows and columns with red squares. The new grid has the size $4 \times 7$, resulting in $\binom{11}{4}$ possible paths.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.