Competition problem — Combinatorics

Library / /177 of 1394

Combinatorics Difficulty 4.8 AIME Find the answer United States

Problem:

Kelvin the frog is on the bottom-left lily pad of a $3 \times 3$ grid of lily pads, and his home is at the top-right lily pad. He can only jump between two lily pads which are horizontally or vertically adjacent. Compute the number of ways to remove 4 of the lily pads so that the bottom-left and top-right lily pads both remain, but Kelvin cannot get home.

Your answer

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

Solution

Solution:

We instead count the arrangements for which Kelvin can get home. Note that at minimum, Kelvin must use 5 lily pads to get home, leaving 4 lily pads that are not on the path. This means that if we were to remove 4 lily pads and Kelvin can still get home, the non-removed lily pads form a shortest path from the bottom-left to the top-right. As there are $\binom{4}{2} = 6$ of these shortest paths, our answer is $\binom{7}{4} - 6 = \boxed{29}$ .

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.