Library / Harvard-MIT Mathematics Tournament /27 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 4.3 AIME Find the answer United States

Problem:
Determine the number of ways of walking from $(0,0)$ to $(5,5)$ using only up and right unit steps such that the path does not pass through any of the following points: $(1,1)$ , $(1,4)$ , $(4,1)$ , $(4,4)$ .

Your answer

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

Solution

Solution:
In the following figure, each lattice point (with the bottom-left-most point $(0,0)$ ) is labeled with the number of ways of reaching there from $(0,0)$ . With the exception of the forbidden points, the labels satisfy the recursion formula $f(x, y) = f(x-1, y) + f(x, y-1)$ . We see from the diagram that there are 34 ways to reach $(5,5)$ .

1	1	5	17	17	34
1	0	4	12	0	17
1	2	4	8	12	17
1	1	2	4	4	5
1	0	1	2	0	1
1	1	1	1	1	1

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

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