★東大入試作問者になったつもりのスレ★ 第十一問

>>464
一般に，任意の自然数mに対して，a[n]がmの倍数になるような自然数nが存在することを示せば，
m=10^2008 ととることにより題意を満たすnが存在することが示される。

まず，{a[n]}に第0項 a[0]=0 を付け加えても，漸化式
a[n+2]=a[n+1]+a[n] は n≧0 で成り立つ。

さて，任意の自然数mに対して，m^2+1個の組
　(a[0],a[1]), (a[1],a[2]), (a[2],a[3]), ……, (a[m^2],a[m^2+1])
を考える。
一般に，整数を m で割った余りは 0〜m-1 の m 通りしかないので，
整数の組(x,y)のそれぞれを m で割った余りの組み合わせは m^2 通りしかない。

よって，上記の m^2+1 個の数の組の中には，m で割った余りが両方とも等しいような数の組がある。
それを (a[j], a[j+1]) と (a[k], a[k+1]) とする。（0≦j＜k≦m^2）

a[j-1]=a[j+1]-a[j] と a[k-1]=a[k+1]-a[k] より，
(a[j-1],a[j]) と (a[k-1],a[k]) も m で割った余りが等しい組になっている。

これを繰り返すと，(a[0],a[1]) と (a[k-j],a[k-j+1]) も m で割った余りが等しいことが言える。
k-j>0 より k-j は自然数で，a[k-j]≡a[0]=0 (mod m) なので，
a[n] が m の倍数となる自然数 n が存在することが示された。