マスターデーモンを解いてみたら、超短くて簡単な解答を見つけた話。
Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴
追記：証明に間違いがあるのに気づいたので、いくらか修正が必要です。
追記(2018/07/23):やっと自分なりの方法で解けたので、解答は次の記事を見てください。
追記(2018/07/28):一般化されたマスターデーモンの解を与えるアルゴリズムを作りました。興味がある方は以下の記事を参考にしてください。
この記事自体は間違ってこそいますが、ちょっとした「思い出」として残しておきます。
マスターデーモンとの出会い
昨日の深夜のことだ。ちょっとインパクトのある記事を何か書いてみたいと思って、整数論の少し難しめの問題を探していた。
そして、数オリの整数論の過去問を探していたら、下記のサイトに流れ着いた。
そこで、数学には一見似つかわしくない文字列を見つけた。
「マスターデーモン」
マスターとついてはいるが、ポケモンマスターとはもちろん何の関係もない。
さらに、デーモンと呼ばれているがLinuxのプロセスとも十中八九関係ない。
マスターデーモンとは、1990年IMO中国大会の第3問として出題された次の数学の問題である。
「 以上の整数
で
が整数となるものを全て求めよ。」
取りかかると没頭できて、素敵な時間が過ごせる、あの整数問題である。
これが非常に難しいとのことだが、
第一感、半日もあれば解けそうだなと思ったので挑戦してみることにした。
夜が明けて
結論から言うと、始めたのが深夜だというのが大悪手だったのだろう。
心地よい眠りを求めつつ、解も求めるのは無理があったようだ。
二兎を追うものなんとやらである。
初日、深夜に始まったデーモンとの闘いは、決着つかずで一時休戦となった。
しかし、何も得なかったわけではない。
ドラクエで竜王の城に忍び込めば伝説の剣が手に入るのと同様、初等整数論について調べているうちに、いろいろな武器を手に入れた*1。
フェルマーの小定理、オイラーの定理、オイラー関数、メビウス関数、位数、その他を使ういくつかのテクニックなどである。
いまいち使い心地が良く分からなかったものが、マスターデーモンと戦っている内に大分使い勝手が分かってきたのだ。
そんなわけで、マスターデーモンと自力で戦うだけで、初等整数論のジョブ経験値をかなり稼げることを注意しておく。
ついでに、自力で解いた暁にデーモンマスターを名乗る機会*2を失うことになります。
以下でネタバレしてあるので、これ以上読むと上記の機会を失うことになりかねないので注意。
「それでも構わんよ」という人だけ続きをお読みください。
ネットで手に入る解答
証明が正しいかちゃんと読んではいないが、ネットで公開されている解答が既に２つあったので言及しておく。
１つは、Yahoo知恵袋にあるもので
もう１つは、灘高数学研究部の2008年度部誌
に乗っている。
Yahooのものは、数式が読みずらく式を全く読まなかったので、正しいかわかりません。
灘高のものは、高校生の時の自分だと到底理解できなかっただろう内容で、そのレベルの高さに驚愕した。こちらは、丁寧に書いてあったけど、少し長かったので、一部しか読んでません。
マスターデーモンの難しさ
自分でマスターデーモンに取り組んでみて、その難しさの要因の１つは、分子に冪が入っているところにあるんじゃないかと思った。
こがマスターデーモンの防御力を上げていて、いろんなアプローチが”はじかれた”感じがする。
例えば不等式やを使って何かしようとすると、すぐに分子が大きな数となり、分母との比較かやりずらくなってしまう。次のような感じだ。
を使っていただけに、ひとつ指数が増える度に時計の音がカチコチなるような印象を受けるが、時計版を見ると１回ごとにありえないくらい針が回っている。
「ちょ、ちょう待って。ホンマちょう待ってくれ。」と言っても待ってくれなくて、大分ワタワタさせられた。
そんなこんなで規則性がつかめず、かなり悩まされた。
と、まあ、こんな感じだ。
あっけない幕切れ（解答と解説）
さて、自分がたどりついた解答をお見せする。
自分でも戸惑うくらいあっけなく、本当にあっけなく、突然解けてしまった。
どうやらマスターデーモンの弱点属性で攻撃してしまったらしい*3。
闇属性だったのだろうか、昼間に考えて、元気を出そうと焼き塩鯖*4を食べてから１時間くらいで解けてしまった。
今までのアプローチの数々はなんだったんだろうか。
あっけなさ過ぎて不安になるレベルなので、もし間違っていたらどうか教えてほしい 。
以下、解答および解説。
まず、必要条件からの候補を絞りこむ。
が
で割り切れたと仮定する。
仮定より、は
で割り切れる。
つまり、
①
ここで、 ②
追記: ②式はが素数の時以外は自明ではないので、この部分をもう少し細かく調べる必要があります。
よって、①、②式より、
であるが、これを満たす以上の自然数
は、
のみである。
残すは十分条件のチェックで、のとき、
となり、のとき題意を満たすをことがわかった。
よって、マスターデーモンの答えは、のみである。
最後に
ネットで日本語サイトのみ調べた限り、ここに書いた解答が今のところ最短かつ簡単なんじゃないかと思ってます。(違ってたらゴメンなさい。)
結局、予想以上に簡単な解があったので、デーモンというよりむしろ、かなりヤバめのヒヨコだったという印象だ。
なんだか超うれしいので、今の喜びを記録しておく。
わほーい。わわっほーい。どぅえっしゃー。
ではでは。
一分後の自分は何を考えているか？求めよ。
Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴
はじめに
「自分は、自分だ。」（wikipedia:トートロジー）
人が考えることには、自分がまだ意識できてないレベルで、法則みたいなのがあるように思える。
例えば、
１．ふと思いついたわりと意味不明なことをネットで調べてみてたら、同じことを誰かが書いていたり。(らっきょうグラタン、ミジンコのみじん切り、その他ホントにどうでもいいこと……など。)
２．ネット将棋で観戦してみたら、自分の考えてるのと同じ手が5~6手くらい連続して指されて、なんだかぞわっとしたり。
３．映画や本の感想だと、なんとなく自分の思ってたことが、amazonのレビュー欄なんかで既に文章化してあったり。
４．数学のテストや勉強で間違えやすいポイントがあると、教えられたわけでもないのに同じ間違え方をしたりする。それも結構な人数が。
なんとなく、思考の”素因数”みたいなものがあるような気がしてくる。
そして、おそらく普段意識してできている思考なんかはきっと、これらの”素因数”を掛け合わせた合成数なんだろう等と空想を進める。
あなたとわたしの素因数分解
例えば、この思考の素因数描像を受け入れて、自分と違うタイプに出会ったときの対応を分類してみる。
１．最大公約数をとるパターン
２．最少公倍数をとるパターン
３．互いに素
基本的なパターンとしてこの３つがあり、１は自分を削ってでも相手に合わせ、２はお互いを受け入れあっていき、３は我が道を行く。
(ここで、３だけが変化・成長しないわけではいことを注意しておく。時刻での太郎君と剛君の思考を自然数
と同一視すると、
が互いに素であるような時間発展が存在するからだ。)
いつかの未来に超賢くなった人類が、超スゴイ人工知能を作って、人間の思考を”素因数分解”して完全解析……なんてできてしまうんだろうか？
適当なことを言うと、後3000年くらいはできそうにない技術な気がするので、自分には関係の無い話だろうが。
まー、こんないらんことを考えてしまうのは、一時期ＳＦばっかり読んでたせいだろう。
まとめ、そしてこのブログについて
少なくとも今は、次の瞬間自分が何を考えているかなんてわからない。
数式にどっぷり浸かって遊んでると、少し前の自分が思い持つかなかったことが隅から隅まで見通せる瞬間があったりする。
そんなとき、数式はただの文字列ではなくなって、自分の内側に少し溶け込んでくる。
そうすると、少し目が覚めたような感覚もする。
まるで少し前の自分が寝ぼけていたんじゃないかって思えるくらいに、少し世界が違って見える。
逆に言えば、起きた直後は覚えていた夢を全く思い出せなくなるみたいなこともある。
そうやって、昨日考えていたや今考えていることも忘れていくんだろう。
（昔は微分積分がなかなかわからなかった自分も、今では何でわからなかったのかすらわからなくなっている。「何かが得意な人が、教えるのが上手とは限らない」。その一般的な原因の１つがここにあるんだろう。）
寝ぼけていろいろ書いたが、日々変わっていく思考に切なくなったようなので、今の自分が考えてることのスナップショットを時々残してみようかと思う。
雑感、考えたこと、数学、その他いろいろなことなんかを。
