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為黑色，染法個數為.從而，

.①

逐項計算得

，，，，，，，，，，.

由式①得

，

，

.

故.