京大で次のような面白い問題が出されたことがある。


問題

(京大)

自然数nの関数f(n),g(n)を

f(n)=nを7で割った余り

g(n)=

によって定める.

(1) すべての自然数nに対してf()=f(n)を示せ.

(2) あなたの好きな自然数nを1つ決めてg(n)を求めよ.そのg(n)の値をこの設問(2)におけるあなたの得点とする.



この問題の面白いところは(2)でg(n)の値がそのまま得点になるところである。このような問題は今まで見たことないし、非常に難しい問題だ。

さすが京大。一発かましてくれるね!と思った。



解答

(1)

自然数はkを自然数として、7k−6、7k−5、…、7kに分けることができる。

それぞれにおいて一般にn=7k−p(p=0、1、…、6)とすれば、

となる。ここで、−pとの余りについて考える。

ここで、それぞれのpの場合について求めればf()=f(n)となることが分かる。


※法(mod)を知っていればかなり楽に解ける。


(2)

この場合最大は18点となる。なぜなら7で割る余りの最大は6であるからだ。(なおこの問題は30点分なのでかなり妥当な点数である。)

よってf(n)=6となる場合が存在するかを調べる。

ここで、余りについて次の等式が成り立つ。

f(f(a)+f(b))=f(a+b)…①

f(f(a)f(b))=f(ab)…②

ここで、②より、

よってとなる。(tは整数)

変形してとなるが、より、t=0のときにのみこの等式が成り立つ。

よってf(n)≠0のとき(つまりn≠7の倍数)、となる。

また、①(これを拡張したもの)より、

よって6となるので、これが答えとなる。



①の証明

f(x)をnで割った余り、a=nX+A,b=nY+Bとすると、

f(a+b)=f(n(X+Y)+A+B)=f(A+B)

f(f(a)+f(b))=f(A+B)である。


②の証明

f(ab)=f(n(nXY+AY+BX)+AB)=f(AB)

f(f(a)f(b))=f(AB)である。



受験では使えないが、もしフェルマーの小定理を知っていたら…

pを素数とし、aとpは互いに素のとき、

となる。


まず、を証明する。これから上の式は自明となる。


ここで、となる。ここでは整数で、また(p−k)!k!はpを因数にもたない。(∵pは素数)

よってはpを因数にもつ。よって…①

ここで、m=1のとき、となる。

m=k−1のときにが成り立つとすると、

(∵①)

これより、m=kの場合も成り立つ。

また、a=0,1の場合も成り立つ。

以上数学的帰納法より、となる。

これよりが成り立つ。


これを使うと、となる。(ただし、aと7は互いに素)

よってg(6)=

inserted by FC2 system