Question

【题目】设，为所有满足下列条件的整数数列的个数：

（1），，且；

（2）不存在、，使得.

试求的值.

Answer 1

【答案】2012

【解析】

将长度为的圆周等分成份，分点依次标为0，1，…，.再将标的分点染为黑色，其他个分点染为白色.则题设数列与以下染法一一对应：

（1）标0的点为黑点，且黑点将圆周分成段圆弧，每段弧长为1或2或3；

（2）圆周上没有两个黑点为对径点，即黑点与白点一一对应，组成对径点.

显然，不存在相邻的三个黑点.否则，设、、为相邻黑点.则其对径点、、为相邻白点，但包含这三个白点的弧长大于3，矛盾.

从而，满足（1）、（2）的染法为标0的点为黑色，将各点染黑、白两色，使得其中没有相邻的三个点同色，再对应地将点染色（染黑色染白色）.

首先，对长为的圆弧各分点染两色，使得两端点为黑色，且没有相邻的三个点同色.

设其染法个数为.易知，，，.

对，考虑最后一段以黑点为端点的圆弧.

若其弧长为3，则相应染法个数为；

若其弧长为2，则相应染法个数为；

若其弧长为1，则其相邻的弧长为2或3，其染法个数为.

故.

下面求满足（1）、（2）的染法个数.

若点为黑色，则染法个数为.

若点为白色，而为白色，则、为黑色，1为白色.如果2为黑色，则染法个数为；如果2为白色，则3为黑色，染法个数为.从而，

.①

逐项计算得

，，，，，，，，，，.

由式①得

，

，

.

故.