HMMT 二月 1998 · ADV 赛 · 第 6 题

HMMT February 1998 — ADV Round — Problem 6

In the diagram below, how many distinct paths are there from January 1 to December 31, moving from one adjacent dot to the next either to the right, down, or diagonally down to the right? Jan. 1 -> * * * * * * * * * *

解析

In the diagram below, how many distinct paths are there from January 1 to December 31, mov- ing from one adjacent dot to the next either to the right, down, or diagonally down to the right? Answer: 372 . For each dot in the diagram, we can count the number of paths from January 1 to it by adding the number of ways to get to the dots to the left of it, above it, and above and to the left of it, starting from the topmost leftmost dot. This yields the following numbers of paths: So the number of paths from January 1 to December 31 is 372.