トップ› 東京工業大学› 1994年› 理系第4問

東京工業大学 1994年理系第4問解説

方針・初手

$m, n$ は負でない整数であるから、$m \geqq 0, n \geqq 0$ である。まず、$m+n \geqq 1$ のとき、$f(m,n)$ に含まれるシグマ計算を実行し、式を扱いやすい形に整理する。さらに、その式が $m=n=0$ の場合（$f(0,0)=0$）にも当てはまることを確認する。

その後、$m+n = l$ （$l$ は負でない整数）とおくことで、見通しが良くなる。$l$ を固定したとき、$n$ のとりうる範囲が $0 \leqq n \leqq l$ に制限されることを利用して値の範囲を絞り込むのが鍵である。

解法1

(1)

$m+n \geqq 1$ のとき、和の公式を用いて $f(m,n)$ を計算すると、

$$ f(m,n) = \frac{1}{2}(m+n)(m+n+1) + n $$

となる。$m=n=0$ のとき、この式の右辺は $\frac{1}{2} \cdot 0 \cdot 1 + 0 = 0$ となり、定義で与えられた $f(0,0)=0$ と一致する。したがって、すべての負でない整数 $m, n$ に対して上記の式が成り立つ。

ここで、$m+n=l$ （$l$ は負でない整数）とおく。$m \geqq 0$ であるから、$n \leqq l$ であり、条件より $n \geqq 0$ だから、$0 \leqq n \leqq l$ である。 $f(m,n)$ を $l$ と $n$ で表すと、

$$ f(m,n) = \frac{1}{2}l(l+1) + n $$

となる。$f(m,n) \leqq 5$ を満たす $(m,n)$ を探すため、$l$ の値で場合分けする。

(i)

$l=0$ のとき $0 \leqq n \leqq 0$ より $n=0$。このとき $f(0,0) = 0 \leqq 5$ より適する。 $m=l-n=0$ より、$(m,n) = (0,0)$ である。

(ii)

$l=1$ のとき $0 \leqq n \leqq 1$ であり、$f(m,n) = \frac{1}{2} \cdot 1 \cdot 2 + n = 1+n$ となる。 $1+n \leqq 5$ を満たすのは $n=0, 1$ であり、いずれも適する。 $m=l-n$ より、$(m,n) = (1,0), (0,1)$ である。

(iii)

$l=2$ のとき $0 \leqq n \leqq 2$ であり、$f(m,n) = \frac{1}{2} \cdot 2 \cdot 3 + n = 3+n$ となる。 $3+n \leqq 5$ を満たすのは $n=0, 1, 2$ であり、いずれも適する。 $m=l-n$ より、$(m,n) = (2,0), (1,1), (0,2)$ である。

(iv)

$l \geqq 3$ のとき $n \geqq 0$ であるから、 $f(m,n) \geqq \frac{1}{2} \cdot 3 \cdot 4 + 0 = 6$ となり、$f(m,n) \leqq 5$ を満たす組 $(m,n)$ は存在しない。

以上より、条件を満たす点 $(m,n)$ は $(0,0), (1,0), (0,1), (2,0), (1,1), (0,2)$ の6点である。これを座標平面上に図示すればよい（解答欄の図には、これらの座標に点を打つ）。

(2)

(1) と同様に、$l = m+n$、$l' = m'+n'$ とおく（$l, l'$ は負でない整数）。 $0 \leqq n \leqq l$ であるから、ある固定された $l$ に対して $f(m,n)$ がとりうる値の範囲は、

$$ \frac{1}{2}l(l+1) \leqq f(m,n) \leqq \frac{1}{2}l(l+1) + l $$

である。ここで、$l+1$ のときの $f(m,n)$ の最小値は、上の式の $l$ を $l+1$ に置き換えて $\frac{1}{2}(l+1)(l+2)$ となる。 $l$ のときの $f(m,n)$ の最大値と、$l+1$ のときの $f(m,n)$ の最小値の差を計算すると、

$$ \frac{1}{2}(l+1)(l+2) - \left\{ \frac{1}{2}l(l+1) + l \right\} = \frac{1}{2}(l^2+3l+2) - \frac{1}{2}(l^2+3l) = 1 $$

となる。これは $1 > 0$ であるから、任意の負でない整数 $l$ に対して、

$$ \frac{1}{2}l(l+1) + l < \frac{1}{2}(l+1)(l+2) $$

が成り立つ。すなわち、$l$ が異なれば $f(m,n)$ のとりうる値の区間は全く重ならず、すべて異なる値をとることがわかる。したがって、$f(m,n) = f(m',n')$ が成り立つならば、必ず $l = l'$ でなければならない。

$l = l'$ のとき、

$$ \frac{1}{2}l(l+1) + n = \frac{1}{2}l(l+1) + n' $$

であるから、両辺から $\frac{1}{2}l(l+1)$ を引いて $n = n'$ を得る。さらに、$l = m+n$ と $l' = m'+n'$ より $m+n = m'+n'$ であり、$n=n'$ だから $m = m'$ となる。以上より、$f(m,n) = f(m',n')$ ならば $(m,n) = (m',n')$ であることが示された。

解説

この問題の関数 $f(m,n)$ は、「カントールのペアリング関数」と呼ばれる有名な関数に合致している。これは2つの自然数（あるいは0以上の整数）の組 $(m,n)$ を、1つの自然数に1対1に対応させる（全単射）ための関数である。

(2) の証明は、まさにこの全単射性（特に単射性）を示すものである。$m+n=l$ という「対角線」の群に分けて考え、$l$ ごとに値の範囲が重ならないことを示すのが王道のアプローチである。(1) を具体的に書き下すことで、$f(0,0)=0, f(1,0)=1, f(0,1)=2, f(2,0)=3, f(1,1)=4, f(0,2)=5, \dots$ のように、座標平面上で斜めに進みながら0から順に番号を振っている規則性に気づくことができれば、(2) の大小評価のイメージが容易に掴めるようになっている。