10. 递推 · Mastering AMC 10/12

10.10%

递推基础

在本节中，你将能够 从较小的答案一步步算出较大的答案，数出爬楼梯的方法数。

Jeff 爬一段 6 级的楼梯，每步跨 1 级或 2 级。把所有爬法都列出来太慢了。你能不列举就数出来吗？

别直接去攻第 6 级。先问一个更小的问题：到达第 1 级有几种方法？第 2 级呢？再问：登上某一级的最后一步可能从哪里出发？这样，一个大的计数问题就变成了一串小的计数问题。

注意：每一种爬到第

n

级的爬法，都以某一步结束。按这最后一步的起点把爬法分类。

动手探索先玩，再学公式

试一试： 一直按“填下一级”，直到填出 f(6)。每个新格子是由哪两个格子算出来的？
试一试： 多按几次“演示一种爬法”。最后一步是不是总跨 1 级或 2 级？为什么这就得到 f(n) = f(n − 1) + f(n − 2)？
试一试： 再打开“跨 3 级”（这就是习题 10.5.1）。现在 f(6) 由哪些格子算出来？

认识概念

定义 10.1.1 · 递推

递推就是先求出较小的值，再用它们计算较大的值。

注 10.1.2 · 斐波那契？

注意： $1, 2, 3, 5, 8, 13$ 这些数正好是斐波那契数列。这是因为递推 $f(n) = f(n-1) + f(n-2)$ 和斐波那契数列的递推一样。但并不是每道递推题都这样。

注 10.1.3 · 工程归纳法

递推题的答案常常可以用工程归纳法得到：算出前几个值，找出规律，然后相信它。（参见第 45 章中关于应试技巧的一节。）

看例题先预测，再揭晓

例 10.1

Jeff 在爬一段 6 级的楼梯。如果他每次可以爬 1 级或 2 级，那么他有多少种不同的方法爬到顶？

1
分类讨论会花很长时间。不如从小处入手。Jeff 到达第 0 级（地面）有多少种方法？

先预测一下：
你的预测

自己做

习题 10.5.1

AMC

Jo 每天在学校都要爬一段 6 级的楼梯。Jo 每次可以爬 1 级、2 级或 3 级。例如，Jo 可以先爬 3 级，再爬 1 级，再爬 2 级。Jo 爬这段楼梯有多少种方法？

过关检测（第 10.1 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

10.20%

有限制的递推

在本节中，你将能够 在规则中途改变时，建立初始值和递推。

Mike 每步跨 2 级或 3 级，但到了第 9 级，他可以迈一级登顶。结尾多了一条特殊规则。递推会因此失效吗？

每道递推题都走同样的四步：先自己数出初始值，再根据“从哪里到达”写出递推，然后一个一个算出后面的值。特殊规则只是改变你要把哪些格子加起来，以及在哪里加。

注意：往回看 3 步的递推，需要先有 3 个初始值，才能自己运转起来。

动手探索先玩，再学公式

台阶数10

步长：

求 f(10)：到达第 10 级的方法数

每步跨 2 或 3 级；登上第 10 级的最后一步可以跨 1、2 或 3 级。

试一试： 先填前几级。为什么对 Mike 来说 f(1) = 0？
试一试： 最后一步可以跨 1 级。选中顶层的格子：哪三个格子加起来等于它？
试一试： 关掉“最后一步可跨 1、2 或 3 级”。顶层的值怎么变了？这就是例 10.2 里的陷阱。

认识概念

概念 10.2.1 · 递推法

用递推解题分几步：

自己动手解出几个较小的初始值。
一般来说，递推式右边有几项，就需要几个初始值。
对一般的 $f(n)$ ，看看到达这一步有哪些不同的方式，用前面的值写出递推式。
一步一步计算 $f(n)$ ，直到算出你要的那个数。

注 10.2.2 · f(0) = 1

你也可以把 $f(0) = 1$ 当作初始值：到达第 0 级一步也不用走，而这样做恰好有 1 种方法。这样可能更快，不过一开始会有点绕，所以例题里不用它。做习题时可以放心用。

注 10.2.3 · 初始值多求几个没坏处

初始值求多了永远没坏处。如果递推中遇到一个你不确定怎么算的值（比如 $f(2)$ 或 $f(3)$ ），就回头再自己多数几个初始值。

看例题先预测，再揭晓

例 10.2

Mike 在爬一段 10 级的楼梯。他很赶时间，所以大部分路程每次爬 2 级或 3 级。如果他到达了第 9 级，就可以再爬 1 级到达第 10 级。Mike 爬到楼梯顶有多少种方法？

1
从初始值开始。Mike 到达第 1 级有多少种方法？

先预测一下：
你的预测

过关检测（第 10.2 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

10.30%

更复杂的递推

在本节中，你将能够 通过插入最新的对象，或者考虑最后一个对象的情况，找出递推。

八个正方体，棱长 1 到 8，叠起来时每个正方体至多比下面那个大 2。叠法有成千上万种。有多少种是合法的？

对象不是台阶时，爬楼梯的技巧照样管用。用规模 $n-1$ 的答案构造规模 $n$ 的答案。对于塔，把最大的正方体插入较小的塔。对于集合，就问 $n$ 本身选不选。

注意：如果每个大的排法都恰好来自一个小的排法，计数就只是相乘。

动手探索先玩，再学公式

试一试： 把正方体 4 插入由 1–3 搭成的塔。有几个位置是合法的？
试一试： 继续插入。n ≥ 3 以后，合法位置的个数还会变吗？看看表格下方的 ×3。
试一试： 按几次“拿走”。剩下的总是合法的塔吗？

认识概念

注 10.3.1 · 检验你的递推

要检验递推式，就自己数几个小的情况，看看递推给出的数是否一样。

看例题先预测，再揭晓

例 10.3

AIME

一组 8 个正方体，对每个满足 $1 \le k \le 8$ 的整数 $k$ ，都恰有一个棱长为 $k$ 的正方体。要用全部 8 个正方体按以下规则搭一座塔：

任何一个正方体都可以放在塔的最底层。
紧挨着放在棱长为 $k$ 的正方体上面的那个正方体，棱长至多为 $k+2$ 。

设 $T$ 为可以搭出的不同的塔的个数。 $T$ 除以 1000 的余数是多少？

1
设 $T(n)$ 为用正方体 $1$ 到 $n$ 搭成的合法的塔的个数。 $T(2)$ 是多少？

先预测一下：
你的预测

在 YouTube 上打开

例 10.4

AMC 12

如果一个整数集合中，任意三个连续整数里至多只有一个属于它，就称这个集合是稀疏的。 $\{1, 2, 3, \ldots, 12\}$ 有多少个子集（包括空集）是稀疏的？

n3

稀疏集：任意连续三个数中至多选一个

a(3): 选了 n · 1

{3}

b(3): 没选 n · 3

∅
{2}
{1}

a(3) = 1：初始值，要自己数出来b(3) = 3：初始值，要自己数出来n = 3 时的总数：a(3) + b(3) = 4

虚线框的列是初始值，要自己数出来。描边的格子是所选列的来源。

1
设 $S(n)$ 为 $\{1, \ldots, n\}$ 的稀疏子集的个数。自己数出 $S(1)$ 、 $S(2)$ 和 $S(3)$ 。 $S(3)$ 是多少？

先预测一下：
你的预测

在 YouTube 上打开

竞赛角真实竞赛题

习题 10.5.5（补充题）

AIME

对整数 $1, 2, \ldots, n$ 的一个排列 $a_1, a_2, \ldots, a_n$ ，如果对每个 $1 \le k \le n-1$ 都有 $a_k \le a_{k+1} + 2$ ，就称它是准递增的。例如， $53421$ 和 $14253$ 是整数 $1, 2, 3, 4, 5$ 的准递增排列，而 $45123$ 不是。求整数 $1, 2, \ldots, 7$ 的准递增排列的个数。

习题 10.5.8（补充题）

AIME挑战

求 $1, 2, 3, 4, 5, 6$ 的排列的个数，使得对每个满足 $1 \le k \le 5$ 的 $k$ ，排列的前 $k$ 项中至少有一项大于 $k$ 。

过关检测（第 10.3 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

10.40%

多个递推函数

在本节中，你将能够 同时记录两个计数，按字符串的结尾来区分。

一条街上有 19 户人家，邮递员从不给相邻两家同时送信，也从不连续三家都不送信。可能的送信方式有多少种？

这里一个计数不够用：接下来能怎么送，取决于这种送信方式怎么结尾。所以要记两个计数： $a(n)$ 表示以收到信结尾的方式数， $b(n)$ 表示以没收到信结尾的方式数。两者互相递推。

注意：答案是两个计数的组合，这里是

a(19) + b(19)

。

动手探索先玩，再学公式

模关

n4

送信：相邻两家不同时收信，不连续三家都没信

a(4): 最后一家收到信 · 2

b(4): 最后一家没收到信 · 3

a(4) = b(3) = 2b(4) = a(3) + a(2) = 2 + 1 = 3n = 4 时的总数：a(4) + b(4) = 5

虚线框的列是初始值，要自己数出来。描边的格子是所选列的来源。

试一试： 看 n = 4 时的列表。一种送信方式以“收到信”结尾时，前一家必须是什么情况？
试一试： 一种送信方式以“没收到信”结尾时，上一封信最远可以在多少家之前？选中 n = 6，看看哪些格子亮了。
试一试： 切换到“连续 ≤ 3”，再把“模”设为 12。看表格下方的说明：总数每隔多少列重复一次？

认识概念

概念 10.4.1 · 两个递推函数

很多时候，定义两个递推函数会更简单，比如 $a(n)$ 和 $b(n)$ ，真正的答案是两者的某种组合（例如 $a(n) + b(n)$ ）。

看例题先预测，再揭晓

例 10.5

AIME 2001

一位邮递员给 Elm 街东侧的十九户人家送信。邮递员注意到，同一天里从来没有相邻的两户都收到信，但同一天里也从来没有超过两户连续都没收到信。可能的送信方式有多少种？

n3

送信：相邻两家不同时收信，不连续三家都没信

a(3): 最后一家收到信 · 2

b(3): 最后一家没收到信 · 2

a(3) = b(2) = 2b(3) = a(2) + a(1) = 1 + 1 = 2n = 3 时的总数：a(3) + b(3) = 4

虚线框的列是初始值，要自己数出来。描边的格子是所选列的来源。

1
设 $a(n)$ 为 $n$ 户人家中最后一户收到信的送信方式数， $b(n)$ 为最后一户没收到信的方式数。如果最后一户收到信，它前面那户必须是什么情况？

先预测一下：
点击一个选项，或输入它的字母（A–E）。

竞赛角真实竞赛题

习题 10.5.3（补充题）

AIME

每个字母都是 A 或 B 的 10 个字母的字符串共有 $2^{10} = 1024$ 个。求其中没有超过 3 个相同字母连在一起的字符串的个数。

n4

A/B 字符串，相同字母至多连续 3 个

f(4): 以 A 结尾 · 7

BBBA
BBAA
BABA
BAAA
ABBA
ABAA
AABA

g(4): 以 B 结尾 · 7

BBAB
BABB
BAAB
ABBB
ABAB
AABB
AAAB

f(4) = g(3) + g(2) + g(1) = 4 + 2 + 1 = 7g(4) = f(3) + f(2) + f(1) = 4 + 2 + 1 = 7n = 4 时的总数：f(4) + g(4) = 14

虚线框的列是初始值，要自己数出来。描边的格子是所选列的来源。

习题 10.5.4（补充题）

AMC 12

对每个正整数 $n$ ，设 $S(n)$ 为只由字母 $A$ 和 $B$ 组成、长度为 $n$ 的序列的个数，要求连续的 $A$ 不超过三个，连续的 $B$ 也不超过三个。 $S(2015)$ 除以 12 的余数是多少？

模12

n4

A/B 字符串，相同字母至多连续 3 个

f(4) = g(3) + g(2) + g(1) ≡ 4 + 2 + 1 ≡ 7g(4) = f(3) + f(2) + f(1) ≡ 4 + 2 + 1 ≡ 7n = 4 时的总数：f(4) + g(4) ≡ 2（mod 12）

模 12 时，总数每 52 列重复一次。

虚线框的列是初始值，要自己数出来。描边的格子是所选列的来源。

过关检测（第 10.4 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

10.5

练习题

在本节中，你将能够 在博弈、圆环和不断缩小的三角形问题中运用递推。

三道挑战题：一个拿砖游戏、一个涂色的圆环、一个不断缩小的三角形。每一道里都藏着一个递推。

想在一页上看到本章的所有题目？打开习题集。

竞赛角真实竞赛题

习题 10.5.2

AMC 10/12挑战

这道题在书中还以 3.3.14 的编号出现。

Arjun 和 Beth 玩一个游戏：两人轮流从若干堵砖墙中的某一堵“墙”上拿走一块砖或两块相邻的砖，拿走后留下的空隙可能产生新的墙。每堵墙都只有一块砖高。例如，大小为 $4$ 和 $2$ 的一组墙，走一步后可以变成下面任意一种： $(3, 2)$ 、 $(2, 1, 2)$ 、 $(4)$ 、 $(4, 1)$ 、 $(2, 2)$ 或 $(1, 1, 2)$ 。

Arjun 先走，拿走最后一块砖的玩家获胜。对于下面哪一种初始局面，Beth 有必胜策略？

习题 10.5.6（补充题）

AIME挑战

下图是一个由六个小区域组成的圆环，你要把它画在墙上。你有四种颜色的颜料，每个区域涂成一种纯色。如果相邻的两个区域不能涂相同的颜色，求涂色方法的种数。

习题 10.5.7（补充题）

AMC 12挑战

设 $\triangle A_0B_0C_0$ 是一个三个角恰好为 $59.999^\circ$ 、 $60^\circ$ 和 $60.001^\circ$ 的三角形。对每个正整数 $n$ ，定义 $A_n$ 为从 $A_{n-1}$ 向直线 $B_{n-1}C_{n-1}$ 所作的高的垂足。类似地，定义 $B_n$ 为从 $B_{n-1}$ 向直线 $A_{n-1}C_{n-1}$ 所作的高的垂足， $C_n$ 为从 $C_{n-1}$ 向直线 $A_{n-1}B_{n-1}$ 所作的高的垂足。使 $\triangle A_nB_nC_n$ 为钝角三角形的最小正整数 $n$ 是多少？