返回题库

三角形顶点随机游走：长度 8 回到 A 的路径数

A bug starts at a vertex A of triangle ABC

专题
Algorithmic Programming / 算法编程
难度
L4

题目详情

一只虫子从三角形 ABC 的顶点 A 出发。每一步它会移动到相邻的两个顶点之一。

问：长度为 8 的路径中，有多少条最终回到 A？例如 ABABABABA 是一条（长度 8）回到 A 的路径。

A bug starts at a vertex A of triangle ABC. It then moves to one of its two adjacent vertices. How many paths of length 8 end back at vertex A? For example, one such path is ABABABABA.

解析

设 ana_n 为从 A 出发走 nn 步回到 A 的路径数，bnb_n 为从 A 出发走 nn 步到达 B 的路径数（到 C 同样也是 bnb_n）。

递推：

  • 要在 n+1n+1 步回到 A，前一步必须在 B 或 C：an+1=2bna_{n+1}=2b_n。
  • 要在 n+1n+1 步到 B，前一步在 A（走 A→B）或在 C（走 C→B）：bn+1=an+bnb_{n+1}=a_n+b_n。

初值 a0=1,b0=0a_0=1,b_0=0。

逐步算到 n=8n=8：

a1=0, b1=1; a2=2, b2=1; a3=2, b3=3; a4=6, b4=5; a5=10, b5=11; a6=22, b6=21; a7=42, b7=43; a8=2b7=86.a_1=0,\ b_1=1; \ a_2=2,\ b_2=1; \ a_3=2,\ b_3=3; \ a_4=6,\ b_4=5; \ a_5=10,\ b_5=11; \ a_6=22,\ b_6=21; \ a_7=42,\ b_7=43; \ a_8=2b_7=86.

因此答案为 86\boxed{86}。