ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (249)

あっという間に解けてしまってつまらなかった京大 (2003年), 東大 (2015 年) の問題. 最初の京大の問題の類題は昨年の大学入試でも他の大学から出題されているので, いまや定番問題といえる. 今年の西暦を使った整数問題も定番である. 今年は,  2021 = 43 \times 47 であったので, 素因数分解は数字の若い素数から順に試していくと大変であった. ちなみに来年は,  2022 = 2 \times 3 \times 337 (337 は, 各桁を足しても素数, 順番を入れ替えても素数) である.

※ 東大の問題の方は, 後から別解をつけた. この別解の方法だと, 前に難解な証明をしてしまった東大 1999 年の 2 項係数に関する整数問題 (記事 24) が, あっという間に片付くし, 問の主張は自明にも思える. この 2015 年の問題は, つまらない問題では全然なかったなあ.

【問】
多項式

 (x^{100}+1)^{100} + (x^2+1)^{100} + 1

は多項式  x^2+x+1 で割り切れるか.

【解】
以下, 合同式は  \mathrm{mod}\ x^2+x+1 で考える.

 x^3-1 = (x-1)(x^2+x+1)

だから,  x^3 \equiv 1 である.

 (x^{100}+1)^{100} + (x^2+1)^{100} + 1
\\\equiv (x+1)^{100} + (x^2+1)^{100}+1
\\\equiv (-x^2)^{100} + (-x)^{100} +1
\\\equiv x^2 + x + 1
\\\equiv 0

したがって, 割り切れる.
//

【問】
m2015 以下の正の整数とする.  {}_{2015}\mathrm{C}_m が偶数となる最小の  m を求めよ.

【解】
題意をみたす最小の  m m_0 とする.

 m =1 のときには, 奇数なので,  1< m_0 \leq 2015 である.

\displaystyle{ {}_{2015}\mathrm{C}_{m_0} 
\\ =\frac{2016-m_0}{m_0}\cdot  {}_{2015}\mathrm{C}_{m_0 -1}
\\ =\left(\frac{2^5 \cdot 3^2 \cdot 7}{m_0} -1\right) {}_{2015}\mathrm{C}_{m_0 -1}}

が成立するが, {}_{2015}\mathrm{C}_{m_0 -1} までは奇数なので,  m_0 = 2^5p (p は正の奇数) でなければならない. (m_0 = 2^{\gamma}p とおくと,  \gamma >5,  \gamma < 5 のどちらでも \displaystyle{ {}_{2015}\mathrm{C}_{m_0}} が偶数にならないことがすぐにわかる.) また,  p>1 だとすると  m_0 が最小であることに矛盾するので,  m_0 =2^5=32 である. (実際,

 \displaystyle{\frac{2016-m_0}{m_0} = 62}

なので,  {}_{2015}\mathrm{C}_{32} は偶数である.)
//

 \begin{align}
2016 - n &= 2^lp\\
n &=2^mq 
\end{align}
( p, q は奇数)

とすると,

 2^l p + 2^mq = 2016=2^5 \cdot 63

だが, ここで,  l > m とすると,

2^m ( 2^{l-m}  p + q )= 2^5 \cdot 63

となる.  2^{l-m}  p + q は奇数なので,  m = 5 でないといけない.
//

【別解】
2015 2 進法で表わすと,  11111011111 になる.  0 になるところは,  2^5 である.

偶奇の判定だけだから, 法 2 の剰余整数を係数とする多項式 (正確には標数 2 の素体  \mathbb{Z}/2\mathbb{Z} 上の多項式環) を母関数として計算することにして *1,

 (x+1)^{2015} 
\\= (x+1)^{1+2+4+8+16+64 + \cdots+1024}
\\=(x+1)(x^2+1)(x^4+1)
\\ \quad  \times (x^8+1)(x^{16}+1)\cdot \cdots \cdot (x^{1024}+1)

とすれば, この式を展開したときに  x^{32} の係数は法 2 0 であり, それより下の次数の項の係数は, すべて 法 21 である. したがって, 偶数となる最小の m は,  32 である.
//

*1:標数  p >0 の体の上の多項式環で成り立つ  (x+1)^{p^N} = x^{p^N} + 1 を用いた. ただし, N は非負の整数である. 証明は,  (x+1)^p = x^p +1 を示した後,  N についての帰納法を用いればよいだけである.