トップ› 名古屋大学› 1999年› 理系第4問

名古屋大学 1999年理系第4問解説

方針・初手

定義された式 $m(k_1, k_2, \dots, k_n)$ の各項はすべて $2$ の累乗であり、右にいくほど指数が小さくなっていることに着目する。もっとも次数の低い $2^{k_n}$ をくくり出すことで、

$$ m(k_1, \dots, k_n) = 2^{k_n} ( m(k_1, \dots, k_{n-1}) - 1 ) $$

という漸化式が導かれる。これと、条件 $k_1 \geqq 1, \dots, k_{n-1} \geqq 1$ から得られる「$m(k_1, \dots, k_{n-1})$ は偶数」という性質を利用し、素因数分解の一意性（奇数部分と $2$ の累乗部分の比較）に持ち込むのが定石である。

解法1

まず、与えられた $m(k_1, k_2, \dots, k_n)$ の式について、$n \geqq 3$ のときの変形を考える。

$$ \begin{aligned} m(k_1, \dots, k_n) &= 2^{k_1+\dots+k_n} - 2^{k_2+\dots+k_n} - \dots - 2^{k_{n-1}+k_n} - 2^{k_n} \\ &= 2^{k_n} (2^{k_1+\dots+k_{n-1}} - 2^{k_2+\dots+k_{n-1}} - \dots - 2^{k_{n-1}} - 1) \\ &= 2^{k_n} (m(k_1, \dots, k_{n-1}) - 1) \end{aligned} $$

また、$n=2$ のときは、

$$ m(k_1, k_2) = 2^{k_1+k_2} - 2^{k_2} = 2^{k_2}(2^{k_1} - 1) $$

となる。

(1)

$m(k_1, k_2, k_3, k_4) = 1999$ より、上記の変形を適用して、

$$ 2^{k_4}(m(k_1, k_2, k_3) - 1) = 1999 $$

ここで、$k_3 \geqq 1$ より $m(k_1, k_2, k_3) = 2^{k_3}(m(k_1, k_2) - 1)$ は偶数である。よって $m(k_1, k_2, k_3) - 1$ は奇数である。 $1999$ は奇数であるから、$2^{k_4} = 1$ すなわち $k_4 = 0$ と定まる。

このとき、

$$ m(k_1, k_2, k_3) - 1 = 1999 \iff m(k_1, k_2, k_3) = 2000 $$

再び変形を用いて、

$$ 2^{k_3}(m(k_1, k_2) - 1) = 2000 = 2^4 \cdot 125 $$

条件 $k_2 \geqq 1$ より $m(k_1, k_2)$ は偶数であるから、$m(k_1, k_2) - 1$ は奇数である。素因数分解の一意性から、

$$ 2^{k_3} = 2^4 \quad \text{かつ} \quad m(k_1, k_2) - 1 = 125 $$

よって、$k_3 = 4$ であり、$m(k_1, k_2) = 126$ となる。さらに $m(k_1, k_2) = 2^{k_2}(2^{k_1} - 1)$ であるから、

$$ 2^{k_2}(2^{k_1} - 1) = 126 = 2^1 \cdot 63 $$

条件 $k_1 \geqq 1$ より $2^{k_1} - 1$ は正の奇数であるから、同様に

$$ 2^{k_2} = 2^1 \quad \text{かつ} \quad 2^{k_1} - 1 = 63 $$

よって、$k_2 = 1$。 $2^{k_1} = 64$ より $k_1 = 6$ となる。以上より、$(k_1, k_2, k_3, k_4) = (6, 1, 4, 0)$ である。

(2)

$m(k_1, k_2) = m(l_1, l_2)$ より、

$$ 2^{k_2}(2^{k_1} - 1) = 2^{l_2}(2^{l_1} - 1) $$

条件 $k_1 \geqq 1, l_1 \geqq 1$ より、$2^{k_1} - 1$ および $2^{l_1} - 1$ は正の奇数である。任意の自然数は（$2$ の累乗 $\times$ 奇数）の形に一意に素因数分解されるため、奇数部分と $2$ の累乗部分がそれぞれ等しくなる。

$$ 2^{k_2} = 2^{l_2} \quad \text{かつ} \quad 2^{k_1} - 1 = 2^{l_1} - 1 $$

前者から $k_2 = l_2$ を得て、後者から $2^{k_1} = 2^{l_1}$ すなわち $k_1 = l_1$ を得る。よって、$k_1 = l_1, k_2 = l_2$ が成り立つことが示された。

(3)

数学的帰納法を用いて示す。 (2) より、$n=2$ のとき $m(k_1, k_2) = m(l_1, l_2) \implies k_j = l_j \ (j=1, 2)$ が成り立つ。

ある $n \geqq 2$ について、以下の命題が成り立つと仮定する。「$m(k_1, \dots, k_n) = m(l_1, \dots, l_n)$ であれば、$k_j = l_j \ (j=1, \dots, n)$ が成り立つ」

$n+1$ の場合を考える。 $m(k_1, \dots, k_{n+1}) = m(l_1, \dots, l_{n+1})$ であるとする。漸化式を用いて変形すると、

$$ 2^{k_{n+1}} (m(k_1, \dots, k_n) - 1) = 2^{l_{n+1}} (m(l_1, \dots, l_n) - 1) $$

ここで、$k_n \geqq 1, l_n \geqq 1$ であるから、 $m(k_1, \dots, k_n) = 2^{k_n}(m(k_1, \dots, k_{n-1}) - 1)$ （ただし $n=2$ のときは $2^{k_2}(2^{k_1}-1)$）により、$m(k_1, \dots, k_n)$ と $m(l_1, \dots, l_n)$ はともに偶数である。よって、$m(k_1, \dots, k_n) - 1$ と $m(l_1, \dots, l_n) - 1$ はともに奇数である。

素因数分解の一意性より、$2$ の累乗部分と奇数部分はそれぞれ等しくなるため、

$$ 2^{k_{n+1}} = 2^{l_{n+1}} \quad \text{かつ} \quad m(k_1, \dots, k_n) - 1 = m(l_1, \dots, l_n) - 1 $$

前者から $k_{n+1} = l_{n+1}$ が成り立つ。後者から $m(k_1, \dots, k_n) = m(l_1, \dots, l_n)$ が成り立つ。

帰納法の仮定より、$m(k_1, \dots, k_n) = m(l_1, \dots, l_n)$ であれば $k_j = l_j \ (j=1, \dots, n)$ が成り立つ。これと $k_{n+1} = l_{n+1}$ を合わせると、すべての $j=1, 2, \dots, n+1$ について $k_j = l_j$ が成り立つ。

したがって、数学的帰納法により、$n \geqq 3$ のときも題意が成り立つことが示された。

解説

2進法展開に似た構造を持つ整数の問題である。すべての項に共通する因数として、もっとも指数の小さい $2^{k_n}$ をくくり出すことが最大のポイントとなる。これにより、「偶数と奇数の積」の形を作り出すことができ、素因数分解の一意性によって式を等式として分割できるようになる。(1) はその具体例を用いた計算であり、(2) と (3) はその一般論を帰納的に証明するものである。(1) を解く過程で一般の漸化式の構造に気づくことができれば、(2) と (3) はほぼ同じ論理の繰り返しとなる。