2014/06/14

不定方程式の難問

分野: 難問・良問  レベル: 数学オリンピック

2014年日本数学オリンピック本選第二問です:

問題

$2^a+3^b+1=6^c$ を満たす自然数$(a,b,c)$ の組を全て求めよ

解答と,解答に至るまでの考え方を詳しく解説します。

不定方程式を見たときに必ずすること

すぐに方針が立つような定番のパターンならよいのですが,数学オリンピックや超難関大学で出題される不定方程式はなかなか方針が思い浮かびません。

そこで,そのような問題に対しては必ず以下の2つを試しましょう。 5分程度でできることです。
基本方針1:$\:\mathrm{mod}\:2,\:\mathrm{mod}\:3$ で考えた時に情報が得られないか確認する
基本方針2:数字が小さい場合について実験する

基本方針を例題に適用する

$2^a+3^b+1=6^c$
基本方針1:
・ $2$ で割った余り
左辺も右辺も偶数になるので絞ることはできません。

・ $3$ で割った余り
$2^a+1$ が $3$ の倍数になることから $a$ が奇数であることが分かりました。一歩前進です。(この情報が有用かどうかはこの段階では分かりません)


基本方針2:
・ $c=1,2,3,4$ のとき具体的に解を探してみます。しらみつぶしに調べると,以下のような解を発見することができます:
$(a,b,c)=(1,1,1), (3,3,2), (5,1,2)$
$c=3,4$ のときに解が発見できないということはおそらく $c\geq 3$ のときには解がないのだろうと予想できます。

では $c\geq 3$ のとき解がないことを示すにはどうすればよいか?
解がないことを示すには,
不等式でおさえるor何かで割ったあまりを考える
ことでほぼ解決します。しかし $\:\mathrm{mod}\:2\:\mathrm{mod}\:3$ では大した情報は得られませんでした。

そこで,もう少し大きめの $n$ に対して $\:\mathrm{mod}\:n$ を考えてみよう!と思います。すると $\:\mathrm{mod}\:8$ でうまくいくことが分かります。

以上を踏まえて解答

$8$ で割った余りに着目できればあとは簡単です。

解答

$c\leq 2$ の場合についてはしらみつぶしに調べると,$(a,b,c)=(1,1,1), (3,3,2), (5,1,2)$ が解であることが分かる。
以下 $c\geq 3$ の場合について考える。 $6^c$ は $8$ の倍数なので,$2^a+3^b+1$ も $8$ の倍数となる。
・ $a\geq 3$ のとき,
$2^a$ も $8$ の倍数なので $3^b+1$ も $8$ の倍数。しかし,$3^b$ を $8$ で割った余りは $3$ か $1$ となるので矛盾。
・ $a=2$ のとき,
先ほどの基本方針1により $a$ は奇数なので矛盾。
・ $a=1$ のとき,
$3+3^b=6^c$
右辺は $9$ の倍数。 $b\geq 2$ のとき左辺は $9$ で割って $3$ 余るので矛盾。(もちろん $b=1$ でもダメ)

以上から,最初に挙げた3つのみが解であることが分かる。

今回の問題で得られた教訓です:

$\:\mathrm{mod}\:2$ や $\:\mathrm{mod}\:3$ で情報が得られなくても $\:\mathrm{mod}\:8, \:\mathrm{mod}\:9$ など大きな数字で考えると新たな情報を得られることもある

実際,不定方程式の難問はこのパターンが多いです。時間がたっぷりとれる問題なら $\:\mathrm{mod}\:2$ から $\:\mathrm{mod}\:11$ くらいまで全て調べて情報を取り出すとよいでしょう。

不定方程式は非常に奥が深いです。

Tag: 不定方程式の解き方6パターン
Tag: 各地の数オリの過去問

分野: 難問・良問  レベル: 数学オリンピック