Problem 15 - Entrance Test

A shortest path from (0,0) to (3,3) involves only moving right (R) or up (U). To reach (3,3) from (0,0), you must make exactly 3 steps to the right and 3 steps up, for a total of 6 steps. The total number of shortest paths from (0,0) to (3,3) is given by the combination C(total steps, steps in one direction) = C(6,3). C(6,3) = 6! / (3! * 3!) = (6 * 5 * 4) / (3 * 2 * 1) = 20. Next, we need to find the number of paths that DO pass through the point (1,1) and subtract them from the total. A path passing through (1,1) can be broken into two independent parts: 1. A shortest path from (0,0) to (1,1). 2. A shortest path from (1,1) to (3,3). Number of paths from (0,0) to (1,1): This requires 1 Right step and 1 Up step, for a total of 2 steps. The number of paths is C(2,1) = 2! / (1! * 1!) = 2. Number of paths from (1,1) to (3,3): This requires (3-1) = 2 Right steps and (3-1) = 2 Up steps, for a total of 4 steps. The number of paths is C(4,2) = 4! / (2! * 2!) = (4 * 3) / (2 * 1) = 6. Total number of paths that pass through (1,1) = (paths from (0,0) to (1,1)) * (paths from (1,1) to (3,3)) = 2 * 6 = 12. Finally, the number of shortest paths from (0,0) to (3,3) that do NOT pass through (1,1) is: Total paths - Paths passing through (1,1) = 20 - 12 = 8.