Question

【题目】某国建了一座时间机器，形似一条圆形地铁轨道，其上均匀设置了2014个站台（编号依次为l，2，…，2014）分别对应一个年份，起始站及终点站均为第1站（对应2014年）.为节约成本，机器每次运行一圈，只在其中一半的站台停靠，出于技术原因，每次至多行驶三站必须停靠一次，且所停靠的任两个站台不能是圆形轨道的对径点.试求不同的停靠方式的种数.

Answer 1

【答案】

【解析】

令.设不同的停靠方式共有种.

首先，对每种停靠方式，定义停靠的站为类，未停靠的站为类，则类站与类站一一配对，组成对径点.

显然，不存在相邻的三个类站（否则，设、、为相邻的类站，则其对径点、、为相邻的类站，机器没有停靠，与题设矛盾），且第1站为类，第站为类.

从而，每种停靠方式对应一种第站的分类方式（第站的分类方式由第站的分类方式唯一确定），使得没有相邻三站同类.

接下来，考虑连续个站台的分类方式（其中，首尾两站为类，且没有相邻三站同类）.设其分类方式种数为.

显然，，，，.

对，考虑最末两个类站中间的类站的个数.若，则分类种数为；若，则分类种数为；若，则与其相邻站为类，分类种数为.

故.②

设.③

则

④

由结论①和式②得.则，.

由式④知为第个斐波那契数，即.

由式③得，

，

.

其次，计算第站的分类种数.

若为类，则相应分类种数为.

若为类，则、为类，2为类.

如果3为类，则相应分类种数为；

如果3为类，则4为类，相应分类种数为.

故.

最后，求.

.

由 .

故

.