shaitan's blog

長文書きたいときに使う。短文書きたいときにも使う。

1993年東工大前期問題4

箱庭数学

1993 東京工業大学 前期MathJax
[解1]
k>n なる整数 k に対し、P(k) が整数となることを示せば十分である。なぜなら、多項式 P(n-x) も P(x) と同じ条件を満たすので、P(k) は k<0 のときも整数となり、また、0\leq k\leq n のときは条件より整数であるから。
0\leq m\leq n を満たす m に対し、多項式 p_m(x) を p_m(x)=\displaystyle\prod_{0\leq i\leq n\\\,\, i\neq m}\frac{x-i}{m-i} と定義すると、 p_m(x) は高々n次の多項式であり、p_m(k)=\begin{cases} 1 & k=m\\ 0 & k\neq m, 0\leq k\leq n\end{cases} である。よって、Q(x)=\displaystyle\sum_{j=0}^nP(j)p_j(x) も高々n次の多項式であり、x=0, 1,\ldots, n という相異なる n+1 個の x で P(x)=Q(x) を満たすので恒等的に P(x)=Q(x) となる。これらより、 p_m(k) が整数であることを示せばよいが、
p_m(k)=\displaystyle\prod_{0\leq i\leq n\\\,\, i\neq m}\frac{k-i}{m-i}=\dfrac{k(k-1)\cdots(k-m+1)(k-m-1)\cdots(k-n)}{m!(n-m)!(-1)^{n-m}}=\displaystyle(-1)^{n-m}\binom km\binom{k-m-1}{n-m} は整数。

[解2: 2025.09.21追記]
非不整数 m に対し、f(x, m) =\begin{cases} 1 & m=0\\ (x-m+1)f(x, m-1)& m>0\end{cases} と定義する。f(x, m) は m 次多項式であり、f(x+1,m)-f(x,m)=mf(x, m-1) を満たす。また、任意の整数 k に対し f(k, m) は m 個の連続した整数の積なので m! の倍数となる。
従って、P(x)=\displaystyle\sum_{m=0}^{n-1}a_m\cdot\frac{f(x, m)}{m!} とおいたとき、a_m が全て整数となることを示せば十分。
ここで、ある 0\leq k\leq n に対し、a_m（m< k）が整数で、a_k が整数でないと仮定すると、P(k)=a_k+\displaystyle\sum_{m=0}^{k-1}a_m\cdot\frac{f(x, m)}{m!} が整数でないため不適（k=0 のときは第二項は存在しないが議論に影響はない）。よって a_m は全て整数である。


[2025.09.23]
「nについての数学的帰納法で示す」という方針で部分点が与えられたというエピソードが有名。そのため、数学的帰納法を使わない解答にした。解2はnについてではないが数学的帰納法になりそうだったので背理法に逃げた。
解2の f(x, m) は下降冪であり (x)_m や x^{\underline{m}} と表記されることがある（物理で超幾何関数を習ったときは前者だった記憶があり、後者は差分方程式の本で見た）。また、\frac{f(x, m)}{m!} は一般化された二項係数である。