1.3. Paths with a Blocked Intersection

So, we have a grid, a rectangular grid, where we start walking at the bottom left corner, and the rule is that we can only go up or right. So, we want to start at the bottom and we want to reach the top right corner. So, we can number the coordinates. So, the bottom right corner we call (0,0). This particular grid has got 5 columns and 10 rows. So, the top right corner is (5, 10). And the question that we ask is how many different ways are going, are that go from (0, 0) to (5, 10).

In this chunk, the problem is introduced. We start at the lower left corner of a grid (0,0) and want to reach the upper right corner (5,10) only moving up or to the right. The task is to find out how many different paths exist to reach this destination considering some constraints.

Think of it like someone who is trying to walk through a city grid, starting from a point (like a park at the bottom left) to reach a tall building at the top right. The only way the person can move is either up a street (like going north) or over a street (like going east). The goal is to count all possible ways to navigate the streets to reach that building.

Now, it turns out this problem is actually a very classical problem in combinatorics counting. So, the way to analyze this is to see, that if I want to go from the bottom to the top, then I must, on the, in one-dimensional I must go from 0 to 5. In the other dimensions, I must go to 0 to 10. So, totally I must make 15 steps… So, therefore, all I need to do to determine exactly which path I am taking is to fix the position of the 5 rights moves among the total 15, right. So, among 15 positions I choose 5. This is usually written as 15 choose 5, right.

This chunk dives into the mathematical approach to counting the paths. Since you must move a total of 15 steps (5 rights and 10 ups), we need to fix the positions of the right moves. This is expressed using combinatorial notation (15 choose 5), which calculates how many ways we can choose 5 positions for rights out of 15 total steps.

Imagine writing a program where you have to list your favorite 5 out of 15 movies. The combinations you can create based on your favorite choices represent how you can choose to move right in the grid, while the rest can be understood as the upwards movements. Each unique selection leads to a different 'path' to goshows your preferences.

So, what, for example, if this is not a perfect grid. Supposing we have some intersections, which are blocked. So, in this particular case, if you look at this intersection, which is (2, 4), right, it is 1, 2 and then 1, 2, 3, 4. So, we have put a black mark to indicate that for the moment, you cannot go through it, right. So, any part that goes through (2, 4), should not be counted among the valid path from (0, 0) to (5, 10).

This chunk introduces an important constraint in the problem: blocked intersections. For the example given, the intersection at (2,4) is blocked, meaning any path that crosses this point cannot be counted as a valid path. The challenge is to adjust the total path calculations to exclude those that pass through blocked intersections.

Think of this like a construction site blocking a street in a town. If the original routes from a park to the tall building realistically pass through that construction site, you cannot count those routes as valid, since they are not usable. You must find alternatives that avoid the blocked area altogether.

So, it turns out that actually this also has a combinatorial solution. So, what you can say is that in order to go from here and if I want to avoid a block intersection... So, I get 6 choose 2. So, I get there are 15 ways to go from (0, 0) to (2, 4). Likewise, if I consider this grid, then this is 3 and this is 6 because it was 10 and 5, I have done 2 and 4 respectively... So, this is total number of paths which are going through (2,4), but I do not want paths going through (2,4).

In this chunk, we learn how to count valid paths despite blocked intersections. We calculate the total paths that go through the blocked intersection and subtract those from the initial total. By doing so, we get the number of valid paths that avoid the intersection altogether.

Continuing the street analogy, if you know that there are a certain number of routes that go through a blocked street, you can simply subtract that number from the total options you had at the start. This way, you can find out exactly how many paths you can still walk without running into construction.

So, this imperfection could be more complex. I could have two positions blocked, right... But now what happens is, this yellow path is subtracted twice because it is part of the paths going through (2,4) and part of the paths going through (4,4), right. So, I have accidentally removed it twice from my total, so I have to put it back. You have to now compute those paths, which go through both the intersections and add them back.

When there are more than one blocked intersections, this chunk describes a more advanced counting method called inclusion-exclusion. It involves first subtracting paths that go through either blocked point, but making sure that paths that cross both points are added back in because they were subtracted twice.

Think of filtering through all possible routes in a scenario where two routes are both blocked. If you remove all paths that go through either block but accidentally exclude those that might have crossed both cities, it's like trying to figure out the real number of valid routes when both towns have road closures.

--