Paths with a Blocked Intersection

Let’s start our discussion about grid paths! Can anyone tell me what we mean by paths in a grid?

Are those the different ways we can move from one corner of the grid to the opposite corner?

Exactly! In a rectangular grid, we can move either right or up. If we start at (0,0) and aim to reach (m,n), we have to make 'm' moves to the right and 'n' moves up.

So how do we figure out how many different ways we can do that?

Great question! We calculate this using combinations. The total number of moves you need to make is 'm+n' and then you can choose positions for the 'm' right moves, which gives you $C(m+n, m)$.

And what does $C$ stand for?

Good catch! $C(n,k)$ represents combinations, which is the number of ways to choose 'k' items from 'n' items. In our case, that's how we calculate the paths.

So if we have a 5 column and 10 row grid, how many paths are there?

That would be $C(15, 5)=3003$. So remember, the formula is key here!

To summarize: We can calculate paths using combinations and learn that in a grid with 'm' columns and 'n' rows, total paths are $C(m+n, m)$.

Now, let’s talk about what happens when there are blocked intersections, like (2,4). What do we do then?

Do we just exclude the paths that go through that intersection?

Exactly! We can calculate how many paths go through the blocked intersection and then subtract that from the total. But first, can anyone tell me how to find paths passing through (2,4)?

We would need to find paths from (0,0) to (2,4) and then from (2,4) to (5,10).

Correct! So we compute the two segments: $C(6,2)$ for the first segment and $C(9,3)$ for the second.

And then we multiply those two values together to find all paths that pass through that point?

Right! So if we multiply these, we would calculate the invalid paths and to compute the valid paths, we perform: total paths minus these invalid ones. What do we end up with if the total is 3003 and invalid paths are 1260?

That would be 1743 remaining valid paths!

Exactly! Well done! So remember, counting invalid paths helps us filter out valid paths in grids with blocked intersections.

In summary: Blocked intersections require us to calculate invalid paths through them and subtract from the total. We keep adjusting our calculations based on new blocks entering the picture.

Now that we’ve tackled single block paths, what happens if we have two blocked intersections? For example, (2,4) and (4,4)?

Wouldn't we just add blocked path counts together?

That's a common mistake! We need to subtract paths through both intersections because we’ll end up counting some paths twice. Can anyone tell me what that principle is called?

I think it’s inclusion-exclusion!

Correct! We include individual blocked paths and exclude the paths traversing both blocks.

How do we find those paths that go through both?

You’d compute the paths from (0,0) to (2,4) then to (4,4) and finally to (5,10). It’s a combination of three segments. Path count through both is then added back after subtraction. What’s our result if we calculate that?

So we learn to adjust our block counts to keep everything intact!

Exactly! Always be cautious of double counts, using inclusion-exclusion helps us keep our math aligned. Well done!

To recap: For multiple blocked intersections, use inclusion-exclusion to accurately calculate and adjust path counts.