ARML 2024 掷币游戏中Marcelo第10次掷币获胜的序列数计算技术问询

咱们先来看这道来自ARML 2024的原题：

Marcelo和Marta玩一个反复掷公平硬币的游戏，硬币落地要么是正面（H）要么是反面（T）。两人会一直玩到出现连续三次掷币结果为HTH或HHH为止——如果HTH先出现，Marcelo获胜；如果HHH先出现，Marta获胜。现在需要计算：能让Marcelo在第10次掷币时刚好获胜的不同掷币序列有多少个？

接下来是官方给出的解法思路，我一步步给你拆解清楚：

首先，我们定义$W_n$为Marcelo在第n次掷币时获胜的掷币序列总数。先看几个基础情况，一眼就能看出来：

• $W_1 = W_2 = 0$：毕竟要分出胜负至少需要3次连续掷币，前两次根本没法结束游戏
• $W_3 = 1$：只有唯一的序列HTH能让Marcelo在第3次获胜
• $W_4 = 2$：对应的序列是HHTH和THTH，这两个都是到第4次才第一次出现HTH，而且之前没出现过HHH

当$n ≥ 5$时，直接枚举就不太现实了，得用递推的方式。核心逻辑是：要让Marcelo在第n次获胜，那第n-2、n-1、n次的结果必须是HTH，而且在第n-3次掷币结束时，游戏还没结束（也就是之前的序列里既没出现过HTH，也没出现过HHH）。

为了方便递推，我们先定义几个状态来追踪未结束游戏的序列：

• $s0_n$：第n次掷币后，处于「最后一位是T，且不会触发任何终止前缀」的未终止序列数
• $s1_n$：第n次掷币后，处于「最后一位是H，且最后两位不是HH」的未终止序列数
• $s2_n$：第n次掷币后，处于「最后两位是HT」的未终止序列数（这个状态很关键，因为再掷一次H就会形成HTH，让Marcelo获胜）
• $s3_n$：第n次掷币后，处于「最后两位是HH」的未终止序列数（这个状态再掷一次H就会形成HHH，让Marta获胜）

根据规则，我们能推导出这些状态之间的递推关系：

1. $s0_n = s0_{n-1} + s2_{n-1}$：状态0的序列要么是前一次就在状态0掷T得到，要么是前一次在状态2掷T得到
2. $s1_n = s0_{n-1}$：状态1的序列只能是前一次在状态0掷H得到
3. $s2_n = s1_{n-1} + s3_{n-1}$：状态2的序列要么是前一次在状态1掷T得到，要么是前一次在状态3掷T得到
4. $s3_n = s1_{n-1}$：状态3的序列只能是前一次在状态1掷H得到

而$W_n$（第n次获胜的序列数），就是前一次处于状态2的序列数（也就是$s2_{n-1}$）——因为这些序列再掷一次H就会形成HTH，刚好在第n次获胜。

现在我们一步步计算到n=10：

从表格里能直接看到，$W_{10}=24$，也就是Marcelo在第10次掷币获胜的不同序列有24个。

备注：内容来源于stack exchange，提问作者TheMultiRounderGamer