Maths Olympiad Prep

Library / /221 of 377

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:
Let n>6n>6 be a positive integer. Determine the number of ways to walk from (0,0)(0,0) to (n,3)(n, 3) using only up and right unit steps such that the path does not meet the lines y=xy=x or y=xn+3y=x-n+3 except at the start and at the end.

Solution

Solution:
Answer: 16(n6)(n1)(n+1)\quad \frac{1}{6}(n-6)(n-1)(n+1)

Consider the first point of the path that lies on x=3x=3. There are two possibilities for this point: (3,0)(3,0) and (3,1)(3,1), and there is exactly one valid way of getting to each point from the origin. Similarly, consider the last point of the path that lies on x=n3x=n-3. There are two possibilities: (n3,2)(n-3,2) and (n3,3)(n-3,3), and there is exactly one valid way of getting to the destination from each of the two points. Now we count the number of valid paths from each of (3,0)(3,0) and (3,1)(3,1), to each of (n3,2)(n-3,2) and (n3,3)(n-3,3), and the answer will be the sum.

- From (3,1)(3,1) to (n3,2)(n-3,2): there are no forbidden points along the way, so there are n5n-5 ways.
- From (3,0)(3,0) to (n3,2)(n-3,2): the path must not pass through (n3,0)(n-3,0), and there is exactly one invalid path. So there are (n42)1\binom{n-4}{2}-1 ways.
- From (3,1)(3,1) to (n3,3)(n-3,3): the path must not pass through (3,3)(3,3), and there is exactly one invalid path. So there are (n42)1\binom{n-4}{2}-1 ways.
- From (3,0)(3,0) to (n3,3)(n-3,3): the path must not pass through (n3,0)(n-3,0) and (3,3)(3,3), and there are exactly two invalid paths. So there are (n33)2\binom{n-3}{3}-2 ways.

Summing, we obtain the answer:
n5+(n42)1+(n42)1+(n33)2=n36n2n+66=(n6)(n1)(n+1)6. n-5+\binom{n-4}{2}-1+\binom{n-4}{2}-1+\binom{n-3}{3}-2=\frac{n^{3}-6 n^{2}-n+6}{6}=\frac{(n-6)(n-1)(n+1)}{6}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.