一道高中数学竞赛题

Question

设n为正整数,f(n)表示一下满足条件十进制n位数(称为波形数)的个数
满足(i)每一位上的数码是1,2,3,4中的一个
(ii)当n>=3时,每个数码都要么比其相邻左右两个数码都小,要么比其相邻左右两个数码都大

求:(1)f(10)的值
(2)f(2008)被13除得的余数
答案是8008和10
但我想要过程

PS. kdlx2006 的递推过程中有个问题,就是这些结尾不仅仅只有一个,一定有很多数的结尾都是一样的两位,所以就不能只算一次

Answer 1

兄弟，人家出题要答案，你出题要命啊-。-花了半天的时间，脑细胞都死光了。。。不知道你这题是属于哪套2008年的竞赛题，估计也是大题吧。。如果是道填空题，我就吐血了。。我用了很笨的办法，做的累死。。但愿还有清晰高效的方法吧。。
首先说一句，谢谢kdlx2006，给了一个递归的思路，这题我乱想了很久，以前也没碰过类似的题，单想求f(n)确实很难，所以想了很久还是用递归，可是也不好做哦。。>_<
看楼主的问题补充，感觉楼主还是有点水品的，那我就能简则简地答咯。。话不多说，开解！

解：
补充定义：f(n)<1+,2+[-],3+[-],4->，其中，f(n)<i+[-]>表示在f(n)中还满足如下条件的数的个数：
i)此数首位为i
ii)此数第二位比首位大[小]
于是，先考察f(1)、f(2)：
f(1)=1
f(2):<1+>=3；<2+>=2；<3+>=1；<2->=1；<3->=2；<4->=3.
先做递归再看后面的情况：
递归公式：
f(n+1)<1+>=f(n)<2->+f(n)<3->+f(n)<4->；
f(n+1)<2+>=f(n)<3->+f(n)<4->；
f(n+1)<3+>=f(n)<4->；
f(n+1)<2->=f(n)<1+>；
f(n+1)<3->=f(n)<1+>+f(n)<2+>；
f(n+1)<4->=f(n)<1+>+f(n)<2+>+f(n)<3+>；
然后再补充f(3)、f(4)、f(5):
f(3):<1+>=6；<2+>=5；<3+>=3；<2->=3；<3->=5；<4->=6.
f(4):<1+>=14；<2+>=11；<3+>=6；<2->=6；<3->=11；<4->=14.
f(5):<1+>=31；<2+>=25；<3+>=14；<2->=14；<3->=25；<4->=31.
和斐波那契数列的原理一样，这样做是无法获得一个通式的。
由于对称，下面只考虑一半的情况：<2-><3-><4->
将他们写出来，即：1 2 3；3 5 6；6 11 14；14 25 31...
下面，设某一组的3个数为a b c，则根据通式写下去：
a b c；c c+b c+b+a；c+b+a 2c+2b+a 3c+2b+a；3c+2b+a 5c+4b+2a 6c+5b+3a...
现在计算这四组数每组3数之和(即f(n)/2的值)：
a+b+c；a+2b+3c；3a+5b+6c；6a+11b+14c
现在做待定系数法：
α(a+b+c)+β(a+2b+3c)+γ(3a+5b+6c)=6a+11b+14c
于是，可解得：α=-1,β=1,γ=2.
所以，终于得到了递推公式：
f(n+3)=2f(n+2)+f(n+1)-f(n)(n≥2) //注意！范围很重要！！
后面的事就简单了。
(1)直接根据递推式求：
f(1)=1；f(2)=12；f(3)=28；f(4)=62；f(5)=140；
f(6)=314；f(7)=706；f(8)=1586；f(9)=3564；f(10)=8008.
(2)易知f(n+3)≡2f(n+2)+f(n+1)-f(n) (mod13)(n≥2)
于是，将余数先一个个写出来，期望能找到周期性，事实上余数是有周期的，从f(1)开始，余数数列为：1 (12 2 10 10 2 4 0 1 0 2 2 6) (12 2...
除第一个数外，以12个数为一周期，易推得f（2008）真好对应余数10

答完睡觉了zzz

Answer 2

f(1)=4
f(2)=可重复的从四个数字中取两个为16
当n>=3时，考虑f（n-1）最后两位数字
12 1
21 2
13 1
31 3
14 1
41 4
23 2
32 3
24 2
42 4
34 3
43 4

在n-1位数字的最后加上第n-2位的数字构成n位数字共f（n-1）种
然后分上述12种情况考虑f（n）比f（n-1）多出的部分：
12 0种
21 2种（3 4）
13 1种（2)
31 2种（2 4）
14 2种(2 3)
41 2种（2 3）
23 1种（1）
32 1种（4）
24 2种（1 3）
42 1种（3）
34 2种（1 2）
43 0种
共16种
综上：f（n)=f(n-1)+16
由f（2）=12得f(n)=16（n-2）+12=16n-20（n>=2)

故f（10）=140
f(2008)=32128被13除的余数是5

这类问题通常都是用递归数列做

Answer 3

第一问f(10)=(3^5+2*3^4+2^2*3^2+2^4*3+2^5+1*3^4+1^2*3*3+1^3*3^2+1^4*3+1^5)*2=1572
第二问是1吧 不确定..

Answer 4

不会做
有答案麻烦你给我留下言
我很感兴趣