HMMT 二月 2002 · 冲刺赛 · 第 15 题

HMMT February 2002 — Guts Round — Problem 15

[7] How many sequences of 0s and 1s are there of length 10 such that there are no three 0s or 1s consecutively anywhere in the sequence?

解析

How many sequences of 0s and 1s are there of length 10 such that there are no three 0s or 1s consecutively anywhere in the sequence? Solution: We can have blocks of either 1 or 2 0s and 1s, and these blocks must be alternating between 0s and 1s. The number of ways of arranging blocks to form a sequence of length n is the same as the number of omino tilings of a 1-by- n rectangle, and we may start each sequence with a 0 or a 1, making 2 F or, in this case, 178 sequences. n