数轴的原点处有一点青蛙，它可以按照以下规则移动：每一次，青蛙或者跳到比其所在位置大的最小的 $3$ 的倍数处，或者跳到比其所在位置大的最小的13的倍数处。一个移动序列是指从 $0$ 跳到 $39$ 的一种移动方式中，青蛙所经过的各点坐标形成的序列。例如，$0$，$3$，$6$，$13$，$15$，$26$，$39$ 是一个移动序列。求青蛙可能形成的所有移动序列的个数。
【难度】
【出处】
2007年第25届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
169
【解析】
移动序列的集合可以被分为两个子集，即包含 $26$ 移动的移动序列的集合与不包含 $26$ 的移动序列的集合，若一个移动序列不含有26，则它必须包含子序列 $24$，$27$ 。为了计算出这样的序列的数目，注意到青蛙有六种方法从 $0$ 跳到 $24$（经过 $13$ 的由 $5$ 种方法，不经过 $13$ 的有 $1$ 种方法），它有四种方法从 $27$ 跳到 $39$（$27$，$30$，$33$ 和 $36$ 都可以成为移动序列中倒数第二个元素）。因此不包含 $26$ 的移动序列有 $24$ 个。若一个移动序列包含 $26$，则它或者包含 $13$ 或者不包含它。若一个这样的移动序列不包含 $13$，则它必然要包含子序列 $12$，$15$，而在这种情况下，青蛙从 $0$ 到 $12$ 只有一种跳法，从 $15$ 到 $26$ 有四种跳法（与从 $27$ 跳到 $39$ 类似）。若一个移动序列包含从 $13$ 到 $26$，则青蛙从 $0$ 到 $13$ 有五种跳法时，从 $13$ 到 $26$ 也有五种跳法，因此青蛙从 $0$ 跳到 $26$ 有 $1\cdot 4+5\cdot 5=29$ 种方法，而它从 $26$ 跳到 $39$ 有五种跳法，故包含 $26$ 的移动序列共有 $145$ 个。因此，青蛙总共有 $24+145=169$ 个移动序列。
答案
解析
备注
