【伝説の入試問題】自分で決めた好きな数が得点になる？【1995・京都大学】

今回は伝説の入試問題シリーズです。

京都大学にとてもユニークな問題が出題されました。

ざっくり言うと「あなたの好きな数を一つ決めて、その値が得点となる」と言うものです。

ロマンあふれる問題ですね。

それでは、早速問題を詳しく見ていきましょう。

問題（1995・京都大学　後期）
（１）解説
（２）解法
まとめ

問題（1995・京都大学　後期）

問題

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

$f(n)=n$を7で割ったあまり

$\displaystyle{g(n)=3f(\sum_{k=1}^{7}k^n)}$

によって定める

（１）全ての自然数nに対して$f(n^7)=f(n)$を示せ

（２）あなたの好きな自然数nを一つ決めて$g(n)$を求めよ

その$g(n)$の値をこの設問におけるあなたの得点とする

本当に「好きな自然数を一つ決めて、その値によって自分の得点が決まる」ようですね。

しかし、よく見ると好きな自然数nを決めて、それを代入した$g(n)$が得点となるようです。きっとここに出題者の意図が隠されているのでしょう。

それでは解説です。

（１）解説

方針

少し大変ですが、

①　nを７で割った時のあまりの７パターンで場合わけ

②「$n^7$」２項定理を使って展開して、７で割ったあまりが等しいことを示す

解法１

解法

（１）「$n$を７で割ったあまり」と「$n^7$を７で割ったあまり」が等しいことを示せばよい

整数kに対して

①　$n=7k$のとき　

nを７で割った余りは０

$$n^7=(7k)^7$$

$n^7$を７で割った余りは０

②　$n=7k+1$のとき

nを７で割った余りは１

$$n^7=(7k+1)^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot1+\cdots+_7C_6\cdot(7k)^1\cdot1^6}_{7の倍数}+1^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot1+\cdots+_7C_6\cdot(7k)^1\cdot1^6}_{7の倍数}+1$$

$n^7$を７で割った余りは１

③　$n=7k-1$のとき

nを７で割った余りは−１

$$n^7=(7k-1)^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot(-1)+\cdots+_7C_6\cdot(7k)^1\cdot(-1)^6}_{7の倍数}+(-1)^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot(-1)+\cdots+_7C_6\cdot(7k)^1\cdot(-1)^6}_{7の倍数}-1$$

$n^7$を７で割った余りは−１

④　$n=7k+2$のとき

nを２で割った余りは２

$$n^7=(7k+2)^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot2+\cdots+_7C_6\cdot(7k)^1\cdot2^6}_{7の倍数}+\underbrace{2^7}_{128}$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot2+\cdots+_7C_6\cdot(7k)^1\cdot2^6+7\times18}_{7の倍数}+2$$

$n^7$を２で割った余りは２

⑤　$n=7k-2$のとき

nを７で割った余りは−２

$$n^7=(7k-2)^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot(-2)+\cdots+_7C_6\cdot(7k)^1\cdot(-2)^6}_{7の倍数}+\underbrace{(-2)^7}_{-128}$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot(-2)+\cdots+_7C_6\cdot(7k)^1\cdot(-2)^6-7\times18}_{7の倍数}-2$$

$n^7$を７で割った余りは−２

⑥　$n=7k+3$のとき

これを７で割った余りは３

$$n^7=(7k+3)^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot3+\cdots+_7C_6\cdot(7k)^1\cdot3^6}_{7の倍数}+\underbrace{3^7}_{2187}$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot3+\cdots+_7C_6\cdot(7k)^1\cdot3^6+7\times312}_{7の倍数}+3$$

$n^7$を７で割った余りは３

⑦　$n=7k-3$のとき

nを７で割った余りは−３

$$n^7=(7k-3)^7$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot(-3)+\cdots+_7C_6\cdot(7k)^1\cdot(-3)^6}_{7の倍数}+\underbrace{(-3)^7}_{-2187}$$

$$=\underbrace{(7k)^7+_7C_1\cdot(7k)^6\cdot(-3)+\cdots+_7C_6\cdot(7k)^1\cdot(-3)^6-7\times312}_{7の倍数}-3$$

$n^7$を７で割った余りは−３

①〜⑦より

全ての自然数nに対して、$f(n^7)=f(n)$

長くなってしまいましたが、２項定理を使って地道にいくと以上のようになります。

他にもmodの計算を使って解く方法もあります。

解法２

「$n$を７で割ったあまり」と「$n^7$を７で割ったあまり」が等しいことを示すのは

$$n^7-n\equiv0\pmod7$$

を示せばよい。

$n\equiv0$のとき$$n^7-n\equiv0\pmod7$$

$n\equiv\pm1$のとき$$n^7-n\equiv0\pmod7$$

$n\equiv\pm2$のとき$$n^7-n\equiv\pm126\equiv0\pmod7$$

$n\equiv\pm3$のとき$$n^7-n\equiv\pm2184\equiv0\pmod7$$

したがって

$$n^7-n\equiv0\pmod7$$

また因数分解を利用して解く方法もあります。

解法３

解法3

「$n$を７で割ったあまり」と「$n^7$を７で割ったあまり」が等しいことを示すのは

$n^7-n$を7で割ったあまりが０であることを示せばよい。

$$n^7-n=n(n^6-1)$$

$$=n(n^3+1)(n^3-1)$$

$$=n(n+1)(n-1)(n^2+n+1)(n^2-n+1)$$

$$n,n+1,n-1,n^2+n+1,n^2-n+1$$

のいずれかが７の倍数になればよい

kを整数とするとき

n=7kのとき　nは７の倍数

n=7k+1のとき　n-1は７の倍数

n=7k-1のとき　n+1は７の倍数

n=7k+2のとき　$n^2+n+1$は７の倍数

n=7k-2のとき　$n^2-n+1$は７の倍数

n=7k+3のとき　$n^2-n+1$は７の倍数

n=7k-3のとき　$n^2+n+1$は７の倍数

したがって、$n^7-n$を7で割ったあまりが０である

いずれの解法も、nを７で割った時のあまりで分類しています。

ちなみにこの問題はフェルマーの小定理のp=7のときです。

フェルマーの小定理

p:素数、a:自然数としたとき

$$a^p\equiv a\pmod p$$

フェルマーの小定理　証明

以下pを法とする

m,nを自然数としたとき

$$(m+n)^p$$

$$=m^p+\underbrace{_pC_1\cdot m^{p-1}\cdot n+_pC_2\cdot m^{p-2}\cdot n^2 +\cdots +_pC_{p-2}\cdot m^2\cdot n^{p-2}+_pC_{p-1}\cdot m\cdot n^{p-1}}_{pの倍数}+n^p$$

$$\equiv m^p+n^p$$

であるので、

$$n^p=(1+n-1)^p$$

$$\equiv1^p+(n-1)^p$$

$$=1^p+(1+n-2)^p$$

$$\equiv1^p+1^p+(n-2)^p$$

$$\equiv\underbrace{1^p+1^p+\cdots1^p}_{n個}=n$$

「フェルマーの小定理」って言うと「いかつく」聞こえますが、意外と身近な問題で使われています。

（２）解法

続いて（２）です。

この問題が「伝説の問題」と言われる所以です。

自分で「好きな数」を決めてそれによって「得点」が決まるという形式になっています。

当然最大の点数をもらうために数字を決めたいと思います。

方針

n=1〜６を代入して具体的に計算する

n=7以上は（１）より考える必要はない

解法

$$g(n)=3f(\sum_{k=1}^{7}k^n)$$

$$=3f(1^n+2^n+3^n+4^n+5^n+6^n+7^n)$$

$n=1,2,3,4,5,6$を代入する

n=1のとき

$$g(1)=3f(1^1+2^1+3^1+4^1+5^1+6^1+7^1)$$

$$=3f(1+2+3+4+5+6+7)$$

$$=3f(28)=3\times0=0$$

n=2のとき

$$g(2)=3f(1^2+2^2+3^2+4^2+5^2+6^2+7^2)$$

$$=3f(1+4+9+16+25+36+49)$$

$$=3f(140)=3\times0=0$$

n=3のとき

$$g(3)=3f(1^3+2^3+3^3+4^3+5^3+6^3+7^3)$$

$$=3f(1+8+27+64+125+216+343)$$

$$=3f(784)=3\times0=0$$

n=4のとき

$$g(4)=3f(1^4+2^4+3^4+4^4+5^4+6^4+7^4)$$

$$=3f(1+16+81+256+625+1296+2401)$$

$$=3f(4676)=3\times0=0$$

n=5のとき

$$g(5)=3f(1^5+2^5+3^5+4^5+5^5+6^5+7^5)$$

$$=3f(1+32+243+1024+3125+7776+16807)$$

$$=3f(29008)=3\times0=0$$

n=6のとき

$$g(6)=3f(1^6+2^6+3^6+4^6+5^6+6^6+7^6)$$

$$=3f(1+64+729+4096+15625+46656+117649)$$

$$=3f(184820)=3\times6=18$$

f(n)の最大は６であるので

n=6のとき最大となる

好きな数字を「６」と決めて

$g(6)=18$

この値「１８」が得点となる

７を法としたそれぞれの値

７を法としたときのそれぞれの値を表にまとめると

\begin{array}{|c|c|c|} \hline & & k=1 & k=2 &k=3&k=4&k=5&k=6&k=7&合計\\\hline n=1のとき&k^1&1&2&3&4&5&6&0&0\\\hline n=2のとき&k^2&1&4&2&2&4&1&0&0\\\hline n=3のとき&k^3&1&1&6&6&6&1&0&0\\\hline n=4のとき&k^4&1&2&4&4&2&1&0&0\\\hline n=5のとき&k^5&1&4&5&2&3&6&0&0\\\hline n=6のとき&k^6&1&1&1&1&1&1&0&6\\\hline \end{array}

6の倍数のときのみ得点が「１８点」入り、それ以外は「０点」となると言う結論でした。

自分で点数を決められるようで、n=6に辿り着かなければ「０点」と言うなかなか厳しい問題ですね。