Consider a 25×25 grid of city streets. Let S be the points of intersection of the streets, and let P be the set of paths from the bottom left corner to the top right corner of which consist of only walking to the right and up. A point s is chosen uniformly at random from S and then a path p is chosen uniformly at random from P. Over all (s,p) pairs, the probability that the point s is contained in the path p can be expressed as a/b where a and b are coprime positive integers. What is the value of a+b?
To solve this problem, let's break it down into smaller steps.
Step 1: Count the total number of points of intersection in the grid.
We have a 25x25 grid, so the total number of points of intersection can be found by counting the number of vertical street lines and horizontal street lines. There are 26 vertical lines and 26 horizontal lines, so there are a total of (26+1) * (26+1) = 27 * 27 = 729 points of intersection.
Step 2: Count the total number of paths from the bottom left corner to the top right corner.
To reach the top right corner from the bottom left corner, we need to take a total of 25 steps up and 25 steps right. Since there are 50 steps in total, we need to calculate the number of ways to choose 25 steps to go up (or equivalently, to choose 25 steps to go right). This can be calculated using the binomial coefficient:
C(50, 25) = 50! / (25! * (50-25)!) = 196,875.
Step 3: Count the total number of (s, p) pairs.
Since we have 729 points of intersection and 196,875 paths, we can multiply these two numbers together to get the total number of (s, p) pairs:
729 * 196,875 = 143,531,875.
Step 4: Count the number of (s, p) pairs where the point s is contained in the path p.
To count the number of (s, p) pairs where s is contained in p, we can consider the position of s within the grid. If s is on the bottom row or the rightmost column, it cannot be contained in any paths that reach the top right corner. So we need to exclude these points from consideration.
There are 25 points of intersection on the bottom row and 25 points on the rightmost column, giving a total of 25 + 25 = 50 excluded points. Therefore, the number of (s, p) pairs where s is contained in p is:
143,531,875 - 50 = 143,531,825.
Step 5: Calculate the probability.
The probability that s is contained in p is equal to the number of (s, p) pairs where s is contained in p divided by the total number of (s, p) pairs:
Probability = (Number of (s, p) pairs where s is contained in p) / (Total number of (s, p) pairs)
Probability = 143,531,825 / 143,531,875
Probability = 1 - 50 / 143,531,875
Probability = 1 - 1/2,870,637
So the probability that s is contained in p can be expressed as 1 - 1/2,870,637.
The value of a + b is therefore 1 + 2,870,637 = 2,870,638.