叶卢庆的博客

1997年全国高中数学联赛一个计数问题

下面我们来做1997年全国高中数学联赛一试第5题.

图1
题目:如图1.设ABCDEF为正六边形,一只青蛙开始在顶点A处,它每次可随意地跳到相邻两顶点之一.若在5次之内跳到D点,则停止跳动;若5次之内不能到达D点,则跳完5次也停止跳动,那么这只青蛙从开始到停止,可能出现的不同跳法共几种?


图2

解:如图2所示,画出树状图,表示出青蛙所经过的所有可能的路径.从图中得知,青蛙从A出发,到达D最近需要3步.由于树状图第4层有两个D,因此跳三步就到D,有两条路径.而青蛙走五步最多有$2^5=32$种可能,由于第四层的两个D之后树状图不再延续下去,因此青蛙共有$32-2\times 2^2+2=26$种走法.