HMMT 二月 2025 · COMB 赛 · 第 2 题

HMMT February 2025 — COMB Round — Problem 2

Kelvin the frog is on the bottom-left lily pad of a 3 × 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.

解析

Kelvin the frog is on the bottom-left lily pad of a 3 × 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. Proposed by: Srinivas Arun Answer: 29 Solution: We instead count the arrangements for which Kelvin can get home. Note that at minimum, Kelvin must use 5 lilypads to get home, leaving 4 lily pads that are not on the path. This means that if we were to remove 4 lilypads and Kelvin can still get home, the non-removed lilypads form a shortest 4 path from the bottom-left to the top-right. As there are = 6 of these shortest paths, our answer is 2 7 − 6 = 29 . 4