递推：全部习题

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

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

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

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

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

对整数 $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$ 的准递增排列的个数。

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

设 $\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$ 是多少？

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