創作整数問題#5解法＆創作整数問題#6

こんにちは、pencilです。世の中には「マスターデーモン」というおどろおどろしい名の付く問題（1990年IMO中国大会(北京)の第3問）が存在し、数学愛好家や数オリ関係者の間で知名度が高い(？)問題です。前回の問題は若干その問題に似ていますが、素数という条件が強い制約になっており比較的簡単に解くことができます。

---

《問題#6》

$a$、$b$、$c$を互いに異なる正の整数とする。$10$進法で表された$3$桁の整数 $N=\overline{abc}_{(10)}$について $a$、$b$、$c$ はこの順に等比数列を成すという。以下の問いに答えよ。

（１）$5$進法で表すと3桁の整数 $\overline{ccc}_{(5)}$となるような$N$を$10$進法で求めよ。

（２）$a$進法で表すと5桁の整数 $\overline{cbbcc}_{(a)}$となるような$N$を$10$進法で求めよ。

（創作問題）

---

今回の問題はなかなか粋な雰囲気を醸し出していますが、絞り込みにより割と簡単に解決できます。

 

---

創作整数問題#5（解き方）

---

さて、前回の問題は

$\dfrac{2^p+1}{p}$ が整数となるような素数 $p$ をすべて求めよ。

というものでしたが、$p$が素数というのがポイントです。$2^p+1$ を次のように変形します。

$$\begin{align}& \ \ \ \ \ 2^p+1 \\ &=(1+1)^p+1 \\ &=(\color{green}{1}+{}_p \mathrm{C}_1 + {}_p \mathrm{C}_2 + \cdots +{}_p \mathrm{C}_{p-1} +\color{green}{1}) \\ &\ \ \ \ \ +\color{green}{1} \\ &=\color{green}{3}+\sum^{p-1}_{k=1} {}_p \mathrm{C}_k \end{align}$$

二項係数${}_p \mathrm{C}_k$は$p$が素数なので$p$で割り切れるのですが自明とまでは言いにくいので一応証明しておきましょう。証明といっても簡単です。

二項係数${}_p \mathrm{C}_k$は$$\begin{align}{}_p \mathrm{C}_k&=\dfrac{p!}{(p-k)!k!}\\&=p\cdot\dfrac{(p-1)!}{(p-k)!k!}\end{align}$$と表せます。この分母$(p-k)!k!$の素因数には$p$が含まれないので${}_p \mathrm{C}_k$は$p$の倍数となります。よって$$\sum^{p-1}_{k=1} {}_p \mathrm{C}_k=pN \ (N \in \mathbb{N})$$と置けるので、結局$$\begin{align}\dfrac{2^p+1}{p}&=\dfrac{3+pN}{p} \\ &=\dfrac{3}{p}+N \end{align}$$となります。これが整数となるには$p$が$3$の約数でなければなりませんが、そのような素数$p$は$3$のみです。よって$$p=3$$が求める素数となります。

---

（コメント）

今回の問題は簡単でしたが（といっても最近の京大入試よりは難しいかもしれませんが）、冒頭でご紹介した通称マスターデーモンさんは数学オリンピックの数々の難問の中でもかなり手強い問題で、補題を予め幾つか示した上で証明に取り掛からないといけないような So Heavy な問題です。問題は

Determine all integers $n > 1$ such that $\dfrac{2^n+1}{ n^2}$ is an integer.

というもので、要するに$\dfrac{2^n+1}{ n^2}$が整数になるような$1$より大きい整数$n$をすべて求めよ、ということを言っています。この問題では$n$が素数ではないので、もちろん以下のような解答は$0$点です。

《誤答例》

$\dfrac{2^n+1}{ n^2}$が整数になるには少なくとも$\dfrac{2^n+1}{n}$が整数でなければならない。いま

$$\begin{align}\dfrac{2^n+1}{n}&=\dfrac{3+nN}{n} \\ &=\dfrac{3}{n}+N \end{align}$$

となるので、これより $n=1、3$ 。

これは $2^n+1=3+nN$ としている部分に誤りがあります。一般の自然数$n$では${}_n\mathrm{C}_k$が$n$の倍数でないことがあります（例えば$(n,k)=(9,3)$など）。こういう場合を除かない限りこの方法を使うことはできませんが、必要条件から攻めるという点は重要です。なお、IMOの公式解答は $n=3$ に目星を付け、$n$の最小の素因数$p$からアプローチしたやや天下り的な解答ですが、最小の素因数を仮定するという方法はこういった数オリレベルの問題で矛盾を導くときの常套手段です。

数学オリンピックはともかく、入試問題を解くにあたって$2^n$を二項展開する方法は知っておいて損はありません。