マスターデーモンを解いてみたら、超短くて簡単な解答を見つけた話。

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

整数論の絶版本・品切れ本をコチラから購入できます！

追記：証明に間違いがあるのに気づいたので、いくらか修正が必要です。

追記(2018/07/23):やっと自分なりの方法で解けたので、解答は次の記事を見てください。

sky-time-math.hatenablog.jp

追記(2018/07/28):一般化されたマスターデーモンの解を与えるアルゴリズムを作りました。興味がある方は以下の記事を参考にしてください。

sky-time-math.hatenablog.jp

この記事自体は間違ってこそいますが、ちょっとした「思い出」として残しておきます。

マスターデーモンとの出会い

昨日の深夜のことだ。ちょっとインパクトのある記事を何か書いてみたいと思って、整数論の少し難しめの問題を探していた。
そして、数オリの整数論の過去問を探していたら、下記のサイトに流れ着いた。

国際数学オリンピックの超難問３選 | 高校数学の美しい物語

そこで、数学には一見似つかわしくない文字列を見つけた。

「マスターデーモン」

マスターとついてはいるが、ポケモンマスターとはもちろん何の関係もない。
さらに、デーモンと呼ばれているがLinuxのプロセスとも十中八九関係ない。

マスターデーモンとは、1990年IMO中国大会の第3問として出題された次の数学の問題である。

「 $2$ 以上の整数 $n$ で $\frac{2^n +1}{n^2}$ が整数となるものを全て求めよ。」

取りかかると没頭できて、素敵な時間が過ごせる、あの整数問題である。

これが非常に難しいとのことだが、
第一感、半日もあれば解けそうだなと思ったので挑戦してみることにした。

夜が明けて

結論から言うと、始めたのが深夜だというのが大悪手だったのだろう。
心地よい眠りを求めつつ、解も求めるのは無理があったようだ。
二兎を追うものなんとやらである。

初日、深夜に始まったデーモンとの闘いは、決着つかずで一時休戦となった。
しかし、何も得なかったわけではない。
ドラクエで竜王の城に忍び込めば伝説の剣が手に入るのと同様、初等整数論について調べているうちに、いろいろな武器を手に入れた*1。

フェルマーの小定理、オイラーの定理、オイラー関数、メビウス関数、位数、その他 $\mod{}$ を使ういくつかのテクニックなどである。
いまいち使い心地が良く分からなかったものが、マスターデーモンと戦っている内に大分使い勝手が分かってきたのだ。

そんなわけで、マスターデーモンと自力で戦うだけで、初等整数論のジョブ経験値をかなり稼げることを注意しておく。
ついでに、自力で解いた暁にデーモンマスターを名乗る機会*2を失うことになります。

以下でネタバレしてあるので、これ以上読むと上記の機会を失うことになりかねないので注意。
「それでも構わんよ」という人だけ続きをお読みください。

ネットで手に入る解答

証明が正しいかちゃんと読んではいないが、ネットで公開されている解答が既に２つあったので言及しておく。

　１つは、Yahoo知恵袋にあるもので

　もう１つは、灘高数学研究部の2008年度部誌

に乗っている。
Yahooのものは、数式が読みずらく式を全く読まなかったので、正しいかわかりません。
灘高のものは、高校生の時の自分だと到底理解できなかっただろう内容で、そのレベルの高さに驚愕した。こちらは、丁寧に書いてあったけど、少し長かったので、一部しか読んでません。

マスターデーモンの難しさ

自分でマスターデーモンに取り組んでみて、その難しさの要因の１つは、分子に冪が入っているところにあるんじゃないかと思った。
こがマスターデーモンの防御力を上げていて、いろんなアプローチが”はじかれた”感じがする。

例えば不等式や $\mod{}$ を使って何かしようとすると、すぐに分子が大きな数となり、分母との比較かやりずらくなってしまう。次のような感じだ。

$2^1,2^2,2^3,..,2^{10}...2^{15},...,2^{100},... \pmod {n^2}$

$\mod{}$ を使っていただけに、ひとつ指数が増える度に時計の音がカチコチなるような印象を受けるが、時計版を見ると１回ごとにありえないくらい針が回っている。

「ちょ、ちょう待って。ホンマちょう待ってくれ。」と言っても待ってくれなくて、大分ワタワタさせられた。
そんなこんなで規則性がつかめず、かなり悩まされた。
と、まあ、こんな感じだ。

あっけない幕切れ（解答と解説）

さて、自分がたどりついた解答をお見せする。
自分でも戸惑うくらいあっけなく、本当にあっけなく、突然解けてしまった。

どうやらマスターデーモンの弱点属性で攻撃してしまったらしい*3。
闇属性だったのだろうか、昼間に考えて、元気を出そうと焼き塩鯖*4を食べてから１時間くらいで解けてしまった。

今までのアプローチの数々はなんだったんだろうか。
あっけなさ過ぎて不安になるレベルなので、もし間違っていたらどうか教えてほしい。

以下、解答および解説。

まず、必要条件から $n$ の候補を絞りこむ。

$2^n+1$ が $n^2$ で割り切れたと仮定する。
仮定より、 $2^n+1$ は $n$ で割り切れる。
つまり、

$2^n+1 \equiv 0 \pmod{n} \cdots$ ①

ここで、
$2^n+1$
$= (1+1)^n +1$
$= 1+\sum^{n}_{k=0} {}_n C_k$
$\equiv 1+1+1 \pmod{n} \cdots$ ②
追記: ②式は $n$ が素数の時以外は自明ではないので、この部分をもう少し細かく調べる必要があります。

よって、①、②式より、
$3 \equiv 0 \pmod{n}$
であるが、これを満たす $2$ 以上の自然数 $n$ は、 $n=3$ のみである。

残すは十分条件のチェックで、 $n=3$ のとき、
$\frac{2^3+1}{3^2}=1$
となり、 $n=3$ のとき題意を満たすをことがわかった。

よって、マスターデーモンの答えは、 $\underline{n=3}$ のみである。

最後に

ネットで日本語サイトのみ調べた限り、ここに書いた解答が今のところ最短かつ簡単なんじゃないかと思ってます。(違ってたらゴメンなさい。)

結局、予想以上に簡単な解があったので、デーモンというよりむしろ、かなりヤバめのヒヨコだったという印象だ。

なんだか超うれしいので、今の喜びを記録しておく。
わほーい。わわっほーい。どぅえっしゃー。

ではでは。

*1:一部は既に勉強したことがあったので、むしろ、スキル・ジョブ経験値を稼いだというべきかもしれない。

*2:なお、人前で名乗のって生じたいかなる問題についても、当方は一切責任をとりませんよ。

*3:メタル系のモンスターに、クリティカルまたは会心の一撃が入った感じである。

*4:非常においしかったです。ちなみに文字を並びかえると、「塩焼きそば」になりそうでならない。

流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。