入試数学コンテスト第1回第6問解答解説

更新日時 2021/10/30
目次
  • 第6問[整数・整式]

第6問[整数・整式]

第6問

pp を素数とする。xx の整数係数多項式 f(x)=a0+a1x++anxn f(x) = a_0 + a_1 x + \cdots + a_n x^n について,全ての係数 aia_ipp の倍数のとき,「f(x)f(x)pp で割り切れる」ということにする。 これにより,整数係数多項式 f(x),g(x)f(x),g(x) について,f(x)g(x)f(x) - g(x)pp で割り切れるとき,「f(x)f(x)g(x)g(x)pp を法として合同である」と定義する。 問題のなかで,f(x),g(x)f(x), g(x) が整数係数多項式のとき, (f(x)+g(x))p \left(f(x) + g(x)\right)^p {f(x)}p+{g(x)}p \left\{f(x)\right\}^p + \left\{g(x)\right\}^p pp を法として合同な多項式であることを用いてもよい。

(1) 00 以上の整数 m,lm,l に対し, (x+1)mpl=a0+a1x++amplxmpl (x+1)^{mp^l} = a_0 + a_1 x + \cdots + a_{mp^l} x^{mp^l} となるような係数 aia_i をとる。このとき,apla_{p^l}pp を法として合同であるような数を mm のみを用いて表せ。

(2) 一般に,有限集合 AA に対し,A\sharp A は集合の元の個数を表すとする。有限集合 GG に対し,ある 00 以上の整数 m,lm,l が存在して, G=mpl\sharp G = mp^l を満たすとする。これを用いて X={YYG,Y=pl} X = \left\{Y \mid Y \subset G, \sharp Y = p^l\right\} とおく。X\sharp Xpp を法として合同であるような数を mm のみを用いて表せ。

第5問に引き続き,問題文が長めで難しい問題が出題されています。そもそも問題の意味がわからないという人もいたかもしれません。ただ,この問題は,問題文の意味さえわかってしまえば見た目ほど難しい問題ではありません。一つずつゆっくりみていきましょう。

まず,問題になれるという意味でも,問題文で与えられている「f(x),g(x)f(x), g(x) が整数係数多項式のとき, (f(x)+g(x))p \left(f(x) + g(x)\right)^p {f(x)}p+{g(x)}p \left\{f(x)\right\}^p + \left\{g(x)\right\}^p pp を法として合同な多項式である」という条件についてこれを証明することから始めてみましょう。二項定理を用いると,以下のように変形できます: (f(x)+g(x))p({f(x)}p+{g(x)}p)=k=0ppCk{f(x)}k{g(x)}pk({f(x)}p+{g(x)}p)=k=1p1pCk{f(x)}k{g(x)}pk(1)\begin{aligned} &\left(f(x) + g(x)\right)^p - \left(\{f(x)\}^p + \{g(x)\}^p\right)\\ &= \sum_{k=0}^p {}_p\mathrm{C}_k \cdot \{f(x)\}^k \{g(x)\}^{p-k} - \left(\{f(x)\}^p + \{g(x)\}^p\right)\\ &= \sum_{k=1}^{p-1} {}_p\mathrm{C}_k \cdot \{f(x)\}^k \{g(x)\}^{p-k} \tag{1} \end{aligned} ここで,pCk=p!k!(pk)!{}_p\mathrm{C}_k = \dfrac{p!}{k!(p-k)!}pp の倍数ですから,(1)(1) 式は pp の倍数を係数に持つ項の和で構成された式です。よって,(1)(1) という多項式は pp で割り切れますから,これにより問題文で与えられていることが証明されました。この式が示すことは,「多項式の和の pp 乗は,それぞれの多項式の pp 乗の和に分解できる」ということです。このことを意識しているかどうかで,(1)を解く上で多少見通しがよくなります。

では,(1)の考察を始めます。検討をつけるために,いくつか式を具体的に計算してみます。m=l=0m = l = 0 のとき, (x+1)0p0=1 (x+1)^{0\cdot p^0} = 1 より,apl=0a_{p^l} = 0 です。また,m=1,l=0m = 1, l = 0 のとき, (x+1)1p0=1+x (x+1)^{1\cdot p^0} = 1 + x より,apl=1a_{p^l} = 1 です。さらに,m=2,l=0m = 2, l = 0 のとき, (x+1)2p0=1+2x+x2 (x+1)^{2\cdot p^0} = 1 + 2x + x^2 より,apl=2a_{p^l} = 2 です。どうやら mm を増やすにつれて,apla_{p^l} の値も同様に増えていくことがわかりました。ll を増やして行った場合はどうでしょうか。m=0m = 0 のときは, (x+1)0pl=1 (x+1)^{0\cdot p^l} = 1 であるから,どんな ll に対しても apl=0a_{p^l} = 0 となります。m=1,l=1m=1, l=1 のときは,問題文での仮定を使うと, (x+1)1p11+xp (x+1)^{1\cdot p^1} \equiv 1 + x^p となります。ただし,f(x),g(x)f(x), g(x)pp を法として合同であることを合同式を用いて f(x)g(x) f(x) \equiv g(x) と略記しています(整数の分野でも同様に使われる,便利な表現です)。このとき,apl=1a_{p^l} = 1 となります。どうやら apla_{p^l}mmpp を法として合同である かもしれない,と予想できます。値を大きくして,m=3,l=5m=3, l=5 のときを計算してみると, (x+1)3p5=(x3+3x2+3x+1)p5(x3p+3px2p+3pxp+1)p4x3p5+3p5x2p5+3p5xp5+1\begin{aligned} &(x+1)^{3\cdot p^5}\\ &= (x^3 + 3x^2 + 3x + 1)^{p^5}\\ &\equiv (x^{3p} + 3^p x^{2p} + 3^{p}x^p + 1)^{p^4}\\ &\equiv \cdots \\ &\equiv x^{3p^5} + 3^{p^5}x^{2p^5} + 3^{p^5}x^{p^5} + 1 \end{aligned} となり,apl3p5(mod  p)a_{p^l} \equiv 3^{p^5} \quad (\mathrm{mod} \; p) となります。3p533^{p^5} \equiv 3 となってくれれば,今までの予想も成立するのですが,これは成立するのでしょうか?実際に p=2,3,5p = 2,3,5 等を入れて計算してみると,これは成立しそうであることがわかります。実はこの式は,「フェルマーの小定理」という定理から一般に成立する式であることが保証されています。

フェルマーの小定理の証明ができなくとも,ここまでの思考に自力で辿り着けた人は,自分の実行力に自信を持って良いと思います。フェルマーの小定理は,整数分野においてしばしば用いられる定理であり,ステートメント自体もそこまで難しくありません。今回の問題を通じてぜひ知っておいて欲しいと思います。

第6問(1)

ll についての帰納法により,apla_{p^l}mmpp を法として合同である」 ことを証明する。

(i) l=0l = 0 のとき

(x+1)m=k=0mmCkxk=1+mx+\begin{aligned} (x+1)^m &= \sum_{k=0}^m {}_m\mathrm{C}_k x^k\\ &= 1 + mx + \cdots \end{aligned} より,a1m(mod  p)a_1 \equiv m \quad (\mathrm{mod} \; p)

(ii) ll において下線部が成立すると仮定する。 (x+1)mpl+1=a0+a1x++ampl+1xmpl+1(x+1)mpl=b0+b1x++bmplxmpl\begin{aligned} (x+1)^{mp^{l+1}} &= a_0 + a_1 x + \cdots + a_{mp^{l+1}}x^{mp^{l+1}}\\ (x+1)^{mp^{l}} &= b_0 + b_1 x + \cdots + b_{mp^{l}}x^{mp^{l}} \end{aligned} と書くことにすれば,帰納法の仮定は bplm(mod  p) b_{p^l} \equiv m \quad (\mathrm{mod} \; p) である。問題文における仮定を用いれば, (x+1)mpl+1={(x+1)mpl}p=(b0+b1x++bmplxmpl)pb0p+b1pxp++bpllxpl+1++bmplpxmpl+1(mod  p)\begin{aligned} &(x+1)^{mp^{l+1}}\\ &= \left\{(x+1)^{mp^{l}}\right\}^p\\ &= \left(b_0 + b_1 x + \cdots + b_{mp^{l}}x^{mp^{l}}\right)^p\\ &\equiv b_0^p + b_1^p x^p + \cdots + b_{p^l}^lx^{p^{l+1}} + \cdots + b_{mp^l}^p x^{mp^{l+1}}\quad (\mathrm{mod} \; p) \end{aligned} よって,xpl+1x^{p^{l+1}} の係数を比較すれば apl+1bpll a_{p^{l+1}} \equiv b_{p^l}^l 帰納法の仮定と,フェルマーの小定理により, apl+1mpm(mod  p) a_{p^{l+1}} \equiv m^p \equiv m \quad (\mathrm{mod} \; p)

(i),(ii)より,下線部の事実は証明された。

(2)です。問題文が難しく書かれていますが,XX は,「要素が mplmp^l 個ある有限集合 GG の部分集合 YY のうち,要素が plp^l 個であるようなものの集合」です。つまり,「番号が振られた mplmp^l 個のボールがあり,plp^l 個のボールを取る時,そのボールに書かれた数字の組み合わせは何通りありますか?」というものを表したのが,X\sharp X なのです。

数学では,より厳密に簡潔に表現をするために,このような厳かに見える方法で事象を記述することがあります。ただ,このような表現は数学において欠くことはできません。例えば,あなたは 2+32 + 3 のことをわざわざ「2と3を足したもの」と書き換えないと 2+32+3 が理解できない訳ではないと思います。記号は表現を豊かにするための重要な道具なわけです。この問題の意味がよくわからなかったという人は,単に数学の記号に慣れていないだけです。少しずつで構いませんから,このような複雑な数式も「読める」ようになっていきましょう。

この問題の意味が理解できた人にとっては,(1)を利用すれば,解を導くことは難しいことではありません。

第6問(1)

X\sharp X

(x+1)mpl=a0+a1x++amplxmpl(✴︎) (x+1)^{mp^{l}} = a_0 + a_1 x + \cdots + a_{mp^{l}}x^{mp^{l}} \tag{✴︎}

における apla_{p^l} に等しいことを示す。

左辺は (x+1)(x+1)(x+1)undefinedmpl \underbrace{(x+1)(x+1)\cdots(x+1)}_{mp^l \text{個}} であり,これを展開した xplx^{p^l} の係数は,mplmp^l 個のものの中から plp^l 個選ぶやり方の個数に等しく,つまり,X\sharp X に等しい。よって, X=apl \sharp X = a_{p^l} (1)より,aplm(mod  p)a_{p^l} \equiv m \quad (\mathrm{mod} \; p) だから,答えは mm となる。

(1) について

実験を繰り返すことで法則性が見えてくることが多々あります。また,難しそうに見える問題でも,実際に値を代入しながら計算を進めることで理解が進むことも多いです。実際の入試で難問にぶち当たったときは,少し落ち着いて計算をしてみる,というのもありかもしれません。

(2) について

一見難しそうな表現に見えても,よく噛み砕いて解釈するとそれほど理解が難しい概念ではないことがあります。数式から本質を見抜く力を少しずつ養っていきましょう。

配点 25点

(1)

[10点] m m

(2)

[15点] m m

平均点 (1) (2)
X - - -
Y - - -
Z 9.7 4.8 4.9