Maths Olympiad Prep

Library / /45 of 94

Combinatorics Difficulty 4.8 AIME Find the answer United States

Problem:
A path of length nn is a sequence of points (x1,y1),(x2,y2),,(xn,yn)(x_{1}, y_{1}),(x_{2}, y_{2}), \ldots,(x_{n}, y_{n}) with integer coordinates such that for all ii between 11 and n1n-1 inclusive, either
(1) xi+1=xi+1x_{i+1}=x_{i}+1 and yi+1=yiy_{i+1}=y_{i} (in which case we say the iith step is rightward) or
(2) xi+1=xix_{i+1}=x_{i} and yi+1=yi+1y_{i+1}=y_{i}+1 (in which case we say that the iith step is upward).
This path is said to start at (x1,y1)(x_{1}, y_{1}) and end at (xn,yn)(x_{n}, y_{n}). Let P(a,b)P(a, b), for aa and bb nonnegative integers, be the number of paths that start at (0,0)(0,0) and end at (a,b)(a, b).
Find i=010P(i,10i)\sum_{i=0}^{10} P(i, 10-i).

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

Solution

Solution:
This is just the number of paths of length 1010. The iith step can be either upward or rightward, so there are 210=10242^{10}=1024 such paths.

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.