Maths Olympiad Prep

Library / /575 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

An up-right path between two lattice points PP and QQ is a path from PP to QQ that takes steps of length 1 unit either up or to the right. How many up-right paths from (0,0)(0,0) to (7,7)(7,7), when drawn in the plane with the line y=x2.021y=x-2.021, enclose exactly one bounded region below that line?

A number or a short expression. Spacing and $ signs are ignored.

Solution

We will make use of a sort of bijection which is typically used to prove the closed form for the Catalan numbers. We will count these paths with complementary counting. Since both the starting and ending points are above the line x2.021x-2.021, any path which traverses below this line (and hence includes a point on the line y=x3y=x-3 ) will enclose at least one region. In any such path, we can reflect the portion of the path after the first visit to the line y=x3y=x-3 over that line to get a path from (0,0)(0,0) to (10,4)(10,4). This process is reversible for any path to (10,4)(10,4), so the number of paths enclosing at least one region is (144)\binom{14}{4}. More difficult is to count the paths that enclose at least two regions. For any such path, consider the first and final times it intersects the line y=x3y=x-3. Since at least two regions are enclosed, there must be some point on the intermediate portion of the path on the line y=x2y=x-2. Then we can reflect only this portion of the path over the line y=x3y=x-3 to get a new path containing a point on the line y=x4y=x-4. We can then do a similar reflection starting from the first such point to get a path from (0,0)(0,0) to (11,3)(11,3). This process is reversible, so the number of paths which enclose at least two regions is (143)\binom{14}{3}. Then the desired answer is just (144)(143)=637\binom{14}{4}-\binom{14}{3}=637.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.