Maths Olympiad Prep

Library / /981 of 1394

Combinatorics Difficulty 5.5 AIME, harder Find the answer United States

Problem:
In the coordinate plane, a closed lattice loop of length 2n2n is a sequence of lattice points P0,P1,P2,,P2nP_{0}, P_{1}, P_{2}, \ldots , P_{2n} such that P0P_{0} and P2nP_{2n} are both the origin and PiPi+1=1P_{i}P_{i + 1} = 1 for each ii. A closed lattice loop of length 20262026 is chosen uniformly at random from all such loops. Let kk be the maximum integer such that the line \ell with equation x+y=kx + y = k passes through at least one point of the loop. Compute the expected number of indices ii such that 0i20250 \leq i \leq 2025 and PiP_{i} lies on \ell.
(A lattice point is a point with integer coordinates.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
We claim that if 20262026 is replaced with 2n2n, the answer is 2nn+1\frac{2n}{n + 1}.

Write the path as a sequence of UU, DD, LL, and RR moves. The possible sequences that can result are precisely those with an equal number of UU's and DD's, and an equal number of RR's and LL's. We first project this sequence onto a single dimension by converting each UU and RR to a 11, and each DD and LL to a 1-1. The resulting sequence will have an equal number of 11's and 1-1's.

We claim that every such sequence of nn 11's and nn 1-1's corresponds to the same number of closed lattice loops. Indeed, given such a sequence, a corresponding lattice loop can be made by replacing all 11's with UU's and RR's, and all 1-1's with DD's and LL's, so that there are an equal number of UU's and DD's. Nothing in this replacement process is order-dependent, so the number of ways to create this loop does not depend on the initial sequence.

We can see that each of the 11's move the path towards \ell and the 1-1's move the path away. Hence, we can think of the path as a one-dimensional walk, starting and ending in the same place, where the points on \ell correspond exactly to the maxima of this one-dimensional walk.

Using Catalan numbers, the probability that any given point is at the maxima is
1n+1(2nn)(2nn)=1n+1, \frac{\frac{1}{n + 1}\binom{2n}{n}}{\binom{2n}{n}} = \frac{1}{n + 1},
and thus by linearity, the expected number of i[0,2025]i \in [0, 2025] such that PiP_{i} is on \ell is 2nn+1\frac{2n}{n + 1}.

Plugging in n=1013n = 1013 gives a final answer of [1013507]\left[\frac{1013}{507}\right].

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.