What are the possible routes from A to D in a 2D grid?

[cronuscronus]

Thanks for sticking with me.

So, A to D is 497420 options.
A to B is 35 options.
B to D is 10 down, 5 right. 15choose5 = 3003.

Now we want to know how many routes through B, so we can "avoid" that.

The routes through B is (35 * 3003). Which equals 105,105.

So, 497420-105105 = 392,315 possible routes from A to D while avoiding B.

 

[LCKurtz]

Thanks for sticking with me.

So, A to D is 497420 options.
A to B is 35 options.
B to D is 10 down, 5 right. 15choose5 = 3003.

Now we want to know how many routes through B, so we can "avoid" that.

The routes through B is (35 * 3003). Which equals 105,105.

So, 497420-105105 = 392,315 possible routes from A to D while avoiding B.

Ok. That's good. Now, using the concepts you have used so far, see if you can do (c) and (d). I won't be back to this thread until later today or maybe tomorrow.

 

[cronuscronus]

Thanks again for the help.

For c, we want to know how many routes pass through both B and C.
I think this is more straight forward. Can simply multiply our way through this.
A to B is 35.
For B to C, we have 5 down, and 2 right required to get to C. So, we can calculate 7choose2, which equals 21.
For C to D, we have 5 down, and 3 right required to get to D. So we can calculate 8choose3, which equals 56.

So, 35*21*56 = 41,160 routes going through B and C.

For d we want to know how many routes must go through B, and must avoid C.
Here are our steps to each point:
A to B = 35
B to C = 21
C to D = 56
A to C is 8 down, 6 across. 14choose8 = 3003 (interesting).
B to D is also 3003
I would compute 35*3003 - 21*3003 = 42,042 routes which must pass through B and avoid C.

 

[cronuscronus]

I think part d has an error.

We need to calculate (A to B * B to D) - (B to C * C to D), which equals
(35*3003) - (21*56)
105105 - 1176 = 103,929

 

[LCKurtz]

Thanks again for the help.

For c, we want to know how many routes pass through both B and C.
I think this is more straight forward. Can simply multiply our way through this.
A to B is 35.
For B to C, we have 5 down, and 2 right required to get to C. So, we can calculate 7choose2, which equals 21.
For C to D, we have 5 down, and 3 right required to get to D. So we can calculate 8choose3, which equals 56.

So, 35*21*56 = 41,160 routes going through B and C.

Correct.

 

[LCKurtz]

I think part d has an error.

We need to calculate (A to B * B to D) - (B to C * C to D), which equals
(35*3003) - (21*56)
105105 - 1176 = 103,929

That is ALMOST correct. Think about what the 35 should multiply.

 

[cronuscronus]

It looks like we need to calculate (A to B * B to D) - (B to C * C to D * A to B)
so
(35*3003)-(21*56*35) = 63,945 routes for part d.

 

[LCKurtz]

It looks like we need to calculate (A to B * B to D) - (B to C * C to D * A to B)
so
(35*3003)-(21*56*35) = 63,945 routes for part d.

Yes. It might have been better to express it as
(A to B)*(B to D - BtoCtoD)

I think you have it now and hopefully you understand it well enough that you could explain to others how to do it.

 

[cronuscronus]

I am going to explain to a friend tonight. If you're ever in San Diego I'll buy you a beer :)