HMMT 二月 2012 · COMB 赛 · 第 3 题

HMMT February 2012 — COMB Round — Problem 3

个人笔记

In the ﬁgure below, how many ways are there to select 5 bricks, one in each ro w, such that any two bricks in adjacent rows are adjacent?

解析

In the figure below, how many ways are there to select 5 bricks, one in each row, such that any twobricks in adjacent rows are adjacent?
Answer: 61 The number of valid selections is equal to the number of paths which start at a topbrick and end at a bottom brick. We compute these by writing 1 in each of the top bricks and lettinglower bricks be the sum of the one or two bricks above them. Thus, the number inside each brick isthe number of paths from that brick to the top. The bottom row is 6, 14, 16, 15, 10, which sums to

1 1 1 1 1
2 2 2 2 1
2 4 4 4 3
6 8 8 7 3
6 14 16 15 10