マスターデーモンの一般化、解の個数を調べてみた。
Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴
追記:証明に間違いがあるのに気づいたので、修正が必要です。
追記(2018/07/28):一般化されたマスターデーモンの解を与えるアルゴリズムができました。興味がある方は以下の記事を参考にしてください。
はじめに
前回の記事で、マスターデーモンを簡単に解く方法を紹介した。
ついでといってはなんだが、灘高の部誌(2008年度)で取り扱われていた一般化について少し考えてみたので書いておく。
なお、部誌の一般化のところはざっと目を通しただけでちゃんと読めてないので、細かいことを言われてもわかりません。(ごめんなさい。)
部誌に書いてあったマスターデーモンの一般化は次の通り。
「一般の自然数に対して、を満たすより大きい自然数を求めよ。」
というわけで、デーモンのがになっている模様。
また、同部誌では
「一般のに対してこのようなが無数に存在するか。」
が未解決問題として提示してあった。
ここでは、2番目の問題に答えてみる。
それでは、やってみる。
一般の自然数の場合の解の個数
の場合は自明なので、以下の場合のみ考える。
まず、の場合にならって、がで割り切れると仮定する。
仮定より、 がが割り切れるので、
①
次に、前回の記事と同様に計算することで
②
となる。
よって、①②式より、
③
となり、なんだかかなり一般的式が得られるが、③式がが満たすべき必要条件である。
そして、この式により、灘高の部誌で未解決とされていた二番目の問題が解決している!
すなわち、の場合を考えると、明らかに③式は成り立たたない。
よって、
となり、一般のの場合のマスターデーモンの解は有限であることが言えた。
より詳細には、が素数を用いて、
このとき、③式から導かれるの候補は、
ここで、任意の組は、の値をとり得る。
従って、一般のの場合のマスターデーモンの解の個数は、同じものを含む組み合わせの場合の数の問題を解けばわかります*3。
特に、を任意の素数として、の場合は、③式を満たす以上の自然数は のみである。
一般解についても調べてみようかと思ったけど、かなり大変そうなので少し疲れてきたので、ひとまずここまでということで。