【IMO2017】2017年国際数学オリンピックの問題1【解答・解説】
2017年国際数学オリンピック(IMO2017)の問題1
なんとなく数学オリンピックの今年の問題を解いてみたくなったので挑戦してみた。問題は、数学オリンピック財団のサイト(http://www.imojp.org/challenge/)を参照しました。今回は、問題1の解答と解説をしていく。もし間違えていたら、優しく指摘してれると助かります。それと、もっと良い解法を教えてくれたら喜びます。
では、問題を見てみましょう。
問題1. をみたすような各整数に対して、数列を以下のように定める:
このとき、あるが存在してをみたすが無数にあるようなをすべて求めよ。
まずは観察と場合わけから
問題の数列の作り方は、平方数になったときだけルートをとり、それ以外は3を足していくことで作られている。慣れるために、いくつかの例でためしてみよう。
のとき、
のとき、
のとき、
のとき、
のとき、
という具合になる。3ずつ増えていくという特徴を活かすために、まずはをを法として分類してみる。
あるでとなる場合
まずは、平方数を調べる。
より、となる平方数は存在しないことがわかる。そのため、一旦あるでとなると、それ以降この数列に平方数は現れない。したがって、より後はすべて単調増加となるので、明らかに題意を満たさない。この観察結果から、がを法としたときに、どのグループに属するかを考えていけばよさそうだと指針がたてられる。
の場合
次は、の場合を考える。この場合は、任意のに対してであることが示せる。
実際、が3の倍数なら、も3の倍数である。
また、が平方数の場合は、を自然数としてとおくと、素因数分解の一意性からある自然数を用いてと表せる。したがって、この場合もとなる。
の場合は、の場合とは異なり、数列には明らかな上限が存在する。*1
正の整数列に上限と下限が存在するので、鳩ノ巣原理より少なくとも1つの自然数が存在して、となるが無数に存在する。
以上より、が3の倍数の場合は題意を満たす。
の場合
最後に、の場合を考える。数列を順番に作っていき、あるでとなれば、上に書いた証明から題意を満たさない。
そこで、すべてのについて、となるが存在すると仮定する。(以下でこの仮定から矛盾を導き、背理法により、いつか必ずあるでとなることを証明する。)
今回は、平方数の最小性に着目した証明方法をとることにした。
まずの内、最小の平方数をとおく。より小さな平方数は存在しないので、数列の定義から、の次の数列であるがの最小値となる。ここで、の最小性から、との間に、であるような数は存在しないはずである。ところが、次に示すように、そのような数を構成することができてしまうのだ。
仮定より、はある自然数を用いてと表せる。*2ここで、以下に定義する平方数を考える。
この平方数は、明らかにより小さい。また、
より、であるから、平方数は
を満たすが、このことは、が最小の平方数であることに反する。
よって、背理法により、の場合、あるでとなるので、題意を満たさない。
解答
以上をまとめて、題意を満たすは『3の倍数』である。
【極限!?】2次方程式の解の公式と1次方程式の解
今日もどこかで『にーえーぶんの……』
今日も誰かがどこかで、
『にーえーぶんのまいなすびー、ぷらすまいなするーとびーじじょうまいなすよんえーしー』
と呪文のように口ずさむ。聞き覚えのある数学フレーズ、そんな2次方程式の解の公式にまつわる話を今回はしてみよう。
何はともあれ、2次方程式は、
という方程式のことで、の場合のものを指す。
このというのがさり気ない条件に聞こえるが、とっても大切だ。
冒頭で唱えた解の公式
も、うっかりとしてみると、『で割る』というタブーを冒してしまう。
ここで、1つの疑問が浮かんだ人もいるだろう。そう、
『の極限をとったとき、解の公式はどうなる?』
という疑問だ。
ヤフー知恵袋にて
この「解の公式の極限問題」は、やはりというかネットで質問している人がいた。
それが、ヤフー知恵袋における次の質問だ。
問題こそ解決ずみになっているが、そのベストアンサーが、私にはなんともスッキリしないものに感じられた。そこで、今回の記事では、この疑問に真正面から立ち向かう。
といっても、ちょっとした計算をするだけれど……
1次方程式へ向かって
の極限をとると、もともとの2次方程式は、
となる。ここで、場合を考えることにすると、これは1次方程式になる。
もちろんその解は、
だ。したがって、2次方程式の解の公式
での極限をとると、その内1つはになると期待できる。
ここで、本当に答えるべき質問は、
①2次方程式の解の公式の極限をどうやってとるか?
②2つあった解の内、もう1つはどうなるか?
の2つだろう。しかし、極限をとるにしても、解の公式の分母にが残ったままではやりづらそうだ。そこで、ちょっと意外なテクニックが使えることに気づいたので紹介したいと思う。それは、いわば、
『分子の有理化』
とでも言えるテクニックである。
「分子の有理化」と「解の公式の極限」
普通学校では、「分母を有理化せよ」と問題に出される。今回は、あえてその逆である「分子」を有理化していく。何が起こるかは、下の計算を少し追ってみてほしい。(以下、複号同順。)一行ずつ丁寧にやっていく。
ここで、なんと、分母と分子の両方が表れているので「約分」できてしまうのだ。「約分」すると、
となる。「分母にルートタイプ」の解の公式である。覚えるには、
『にーしーわる、まいなすびー、まいなすぷらするーとびーじじょうよんえーしー』
と唱えればいい。
とにかく、こうなってしまえば、後はの極限をとるだけだ。
の絶対値を外すと、かのいずれかなので、結局、解の公式に現れる2つの解の極限は、
つまり、
となる。*1
以上のようにして、2次方程式の「解の公式の極限問題」は、「分子の有理化」というちょっと予想外のテクニックによって解決したのであった。
え……?
『3次方程式の解の公式の極限がどうなるか』って?
気が向いたらやるかもしれませんし、面倒そうなのでやらないかもしれません。
それでは、また次の更新でお会いしましょう。
【割り算ネタ】2から11までの数で割れ切れるか、簡単に判定する方法
はじめに
『私は計算が苦手だ』
そんなあなたに、今回は割り算のちょっとした裏技を紹介しようと思う。
もちろん、計算が得意な人も、知ってるとさらに得すると思う。
今回紹介するのは、ある自然数がの数で割り切れるか楽に判定する方法だ。「楽に」というのは、なるべく計算する量を減らすという意味だ。例えば、やで割れるか調べたい場合には、とある足し算を繰り返すだけでいいし、の場合は、ある桁数より上の桁の数は無視して調べられるといった具合だ。
たいていの人は小学校で、で割り切れるか判定する方法を聞いたことがあるだろう。で割り切れるか調べる方法が一番知られているとして、知名度順に割る数を並べると、おそらく、
という順番になると思う。特に、で割り切れるかの判定方法は、本で見たことなかったので、今回の記事のために作ってみた。便利さはともかくとして、そこそこレアな方法だと思う。
今回の記事では、割る数がからのすべての場合の判定方法を紹介するので、なんとなく素因数分解したくなったときには、ぜひ試してほしい。
そして、この記事を読み終えるころには、整数問題のちょっとした問題とかも作れたりするようになるだろう。
2、4、5、8、10で割り切れるか判定する方法
ある自然数があったとき、のどれかで割れるか調べたいとする。
これらの数は共通して、割られる数の下桁~下桁までを調べればいい。
で割り切れる ⇔ の位が
で割り切れる ⇔ 下桁がで割り切れる
で割り切れる ⇔ の位がか
で割り切れる ⇔ 下桁がで割り切れる
で割り切れる ⇔ の位が
これらを証明してみよう。
まず、割られる自然数をの位とそれ以外に分けて
と表す。ここで、は以上の整数で、はからのいずれか。
より、第一項がの倍数なので、後は、の位の数であるがで割り切れれば(つまり、の位がならば)、自然数もで割り切れる。
同様に、で割り切れるかどうか調べたいときも、
より、がの倍数(つまり、の位がならば)、自然数はで割り切れる。
ここまでの証明のポイントになっているのは、と分解できることだ。そのため、かで割れ切れるか調べたいときは、の位より上の桁は計算に無視していい。
次に、で割れ切れるか調べる方法について説明する。この場合は、下桁を調べる必要がある。それは、やのときと事情が違って、はで割り切れないからだ。ここでは、の代わりにの分解を使うことになる。つまり、
と表せることに注目する。割られる数をの位との位とそれ以外に分けて、
と表す。ここで、は以上の整数で、はのいずれか。より、
と表せることより、第項はの倍数なので、がで割り切れればもで割り切れる。つまり、自然数の下桁がで割り切れれば、もで割り切れる。
で割り切れるかどうかを調べる場合は、で割り切れるかどうかを調べたときと同様にして、の分解()を使って証明できる。
最後に、ある自然数がで割り切れるかを調べるには、の位がの場合に限る。で割り切れるには、でもでも割り切れる必要があるので、これら両方の場合に許されるの位の数はに限られるからだ。
3、9で割り切れるか判定する方法
で割り切れるか判定する方法は次の通り。
で割りきれる ⇔ 各位の数の和がで割り切れる
で割り切れる ⇔ 各位の数の和がで割り切れる
試しに、がで割り切れるかやってみる。このとき、各位の和は
との倍数になるので、でもでも割り切れる。(実際、となる。)
もう少し大きな数の例で、の場合は、
より、で割り切れる。(実際、)
まず、で割り切れるかどうかの判定方法から証明してみよう。で割り切れるかどうかを調べた時のことを振り返ると、という「単位」がで割り切れるかどうかがポイントになっていた。
そこで、をで割ってみた場合を調べることから始める。すると、
となる。つまり、のべき乗はで割ると、余る数になっている。
そこで、ある桁の自然数を
と表す。ここで、整数はからのいずれか。ここで、等を使うと、
と表せる。ここで、第一項はの倍数なので、残りのがで割り切れれば自然数もで割り切れる。つまり、自然数の各位の数の和がの倍数ならば、自然数もの倍数になる。
同様に、で割れるかどうか判定する場合は、
を用いて、
より、第項がの倍数なので、残りのがで割り切れればもで割り切れる。つまり、自然数Nの各位の数の和がの倍数ならば、自然数もの倍数になる。
11で割り切れるか判定する方法
で割り切れるか判定する方法も、やの場合とそこそこ似ている。
で割り切れる ⇔ 「奇数桁の数の和」ー「偶数桁の数の和」がで割り切れる
試しに、の場合だと、
より、はで割り切れる。(実際、)
応用問題をつやってみよう。
【問題】下桁がの自然数で、で割り切れる最小の数は何か。
【回答】はの倍数でないので、桁の数を調べればいい。
千の位をとして、奇数桁の和ー偶数桁の和がの倍数となればいいので、
よって、が答え。(実際、。)
さて、この判定方法を証明してみよう。をの倍数を使って表してみる。
という風に、は、
となる。よって、桁の自然数は、
より、がで割り切れれば、もで割り切れる。つまり、自然数について、「奇数桁の数の和」ー「偶数桁の数の和」がで割り切れれば、自然数もで割り切れる。
7で割り切れるか判定する方法
さて、ここまででを除いて、からまでの数で割りきれるかの判定方法を紹介した。なぜを一番最後に持ってきたかというと、他の数ほど分かりやすい判定方法でないからだ。
で割り切れる ⇔ 下の位から順番にを繰り返しかけて足したものがで割り切れる
例えば、の場合、
より、で割り切れる。この例だとあまり計算が楽になった感じがしないかもしれないが、
やのように、3桁ごとに繰り返す6桁の数が7で割り切れることなんかは、この判定方法を使うとすぐに分かる。
ついでに、ちょっとした応用問題も作ってみる。
【問題】下から桁目以外がであるような桁の自然数で、で割り切れるもののうち、最小のものを求めよ。
【回答】
下から桁目の数をとすると、題位の自然数がで割り切れるには、上に書いた判定方法より、
が7で割り切れればいい。をできるだけ小さくとるには、
の場合を考えればよく、これを満たす自然数[tex:a_1,a_7,a_{14}]で題位の自然数を最小にするものは、。([tex:10000000000006]はで割り切れる。ここで、は個並んでいる。)
応用問題を作ったせいで、脇道にそれたが、判定方法の証明をやってみる。他の数で割れるか調べた時と同様に、をの倍数を使って表してみる。結果だけを書いておくと、
となり、以下、の倍数にと繰り返す。
よって、桁の自然数は、
より、がで割り切れるためには、がで割り切れればいい。つまり、下の位の数から順に、と繰り返しかけて足したものがで割り切れるとき、元の数もで割り切れる。
【マトリックス】変数aとbを入れ替えるのに、cは要るのか問題!?【増殖するb】
プログラミング関連の絶版本・品切れ本をコチラから購入できます!
変数との入れ替えとエージェントスミスについて
変数とに異なる値が入っていて、それを入れ替えるアルゴリズムを書きましょう……というのは、プログラミングの入門書にありがちな問題で、ついさっきあるプログラミング言語の本を見ていたら、また書いてあった。
では、この問題の模範的な"間違え方"から紹介しよう。それが、
①とに値を入力
②
③
④とを出力
という解答*1。この間違え方をすると、本の著者や解答を知っている人にニヤニヤされるかもしれないので要注意だ!
落とし穴は②でにの値を代入しているところで、代入した瞬間にもも全部の値になってしまい、の値が跡形もなくなっている。いわば、このがマトリックスのエージェントスミスなのだ。
このようなスミスの無限増殖を防ぐ方法として、たぶん一番よく書いてある解法は、余分な変数を用意して、
①とに値を入力
②
③
④
⑤とを出力
として、の値が上書きされる前にに避けておけばいい。要は、がネオである。
さて、このないしネオは常に必要なのだろうか?そんなことを何となく考えていたら、を使わない第2の解答が存在することに気づいた。ただし、,が整数や実数等の数値である場合に限るけど。この解答は、厚めの本とか開けるとたぶん書いてありそうだけど……あえて紹介してみる!
を使わない解法とネオの休日
を使わないでとを入れ替えるには、どうしたらいいか?
それには、を完全にに置き換えるのではなく、との両方の情報を持つようにしておけばいい。つまり、に半分だけスミス分を入れる。
ここまで来ればもう簡単なので、解答を書いてみる。わかりやすくするため、とに最初に入っている値をとして、各ステップでに入っている値もカッコで囲って書いておく。
①,
②,
③,
④,
⑤とを出力
という風に、変数(ネオ)が休んでいても、との値は無事に入れ替えられた(Mission complete!)
*1:プログラミングでは左辺の変数に右辺の変数の値を代入するという意味。
【ダイジェスト版】 2015東大理系 数学 第5問の解法 【2進法】
前回の記事……なんか長いっ!
1つ前の記事で、2015東大理系数学第5問を2進法を使ってガンガン解いた。
ただ、この記事はたくさん寄り道していて、問題を解きたいだけの人には、余計な情報*1が多い。そんなわけで、なるべく最短ルートで解けるように書き直してみた。
表記法の約束
解法に入る前に、2進法の表記について約束事をしておく。
前回の記事で、と数字が続き過ぎて見づらかったのを反省した。
では、約束事。
「2進法で同じ数字が回続くときは、指数を使ってと表す」
例えば、はのように表す。
計算しやすさ優先で、みたいに書いたりもするけど、意味は同じ。
最後に、指数がのときは、その桁が存在しないことにする*2。
なお、この表記法を他の人が使ってるかどうかは良く知らないし、面倒なので調べない。これは、「少なくともこのブログ内で使っている表記法」だ。
できるだけ最短ルートな解法
を2進法で表すと、となる*3。
①の場合、
を2進法で表すと、その下桁がとなるような自然数が明らかに存在する*4。また、を進法で表したときの下は、
となるので、のものと一致する。
従って、任意の自然数に対して、との素因数の個数は等しい。また、
と表せるので、のときは、は奇数。
②の場合、
を2進法で表すと、
なので、 はで回まで割り切れる。従って、は偶数。
ここで①の結果より、は奇数なので、
は偶数となる。
よって、が偶数となる最小の自然数は■
以上!終わり!
「2015東大理系 第5問」を2進法でガンガン解こうぜ!! ~ついでに一般化できたかも?~
Youtubeを散歩してたら……
なんとなくオシャレ、かつあんまし時間のかからなそうな整数論の問題をYoutubeで見かけた*1。
【話題の一行問題】東大数学2015第5問【2015Cmが偶数】 - YouTube
というわけで、久々に更新。
サクサクのおやつみたいに手軽に楽しめる問題なので、遊びたい人は自分でチャレンジしてみてください。ちょっとした気分転換になると思うよ!
2015東大理系 第5問
問題は次の通り、
『を以下の正の整数とする。が偶数となる最小のを求めよ。』
これを気楽に解いてみた*2。
2進法を使って解いてみたのが、結構気に入ったので公開してみる。そう、2進法でガンガンいってるので、受験生は真似しない方がいいかも*3……
要は、どこかの数学好きが、少しでも楽しくなればOKというスタンスなのだ。
今回のあらすじ
ステップ1:の場合にを調べてみた。これは寄り道。
ステップ2:進法を使う解き方の始まり~。そして、怪し過ぎる数を見つける!
ステップ3:が奇数であり続ける、そのギリギリまで一掃する!
ステップ4:がついに偶数に!ついでに一般化も?
ステップ1(寄り道): のとき、はで最大何回割れるか?
最初にやった実験を紹介してみる。けど、この方針は途中で面倒になって放棄したので、興味ない人や解法だけ知りたい人はステップ2から読んだ方が良いです。
整数問題が苦手な人が、この問題を考える練習くらいにはなってるかも?*4
が偶数かどうかを考えたいから、分子分母がで何回割り切れるかを調べるのが基本方針になる。
そこで、分母に現れるがでぴったり回割り切れると表せる場合から考えてみる。
このとき、はで最大何回まで割り切れるか?(素因数の個数)
これを知りたくなって、冪のリズムに合わせて、
とかテンポ良く書いてみた。
それで、この式をちょっと観察すると、
「に含まれる偶数は、に現れる数1つ1つにをかけたものに一致する」
と気づく。逆に言うと、
「に含まれる偶数を全て取り出し、それぞれで割ってから、もう一度かけ直すと、にピッタリ一致する*5。」
この観察結果から、に含まれる素因数の個数をとおいて考えてみる。まず、はで回だけ割れるからだ。一般ののときは、上に書いた観察から、
と書けることが明らかなので、少し式変形して、
つまり、はで、最大回割れる。
よって、
『定理1: はで、最大回割れる。』
と分かる。これを使うと、からまでの数を1つずつかけた数は、で回割れるとかすぐにわかる*6。
ステップ2: 2015をの冪を使って表してみたくなる。そして、2進法へ……
分母に現れるがの冪の場合は、ステップ1で調べた。
次は分子だが、は偶数じゃない。けど、の冪を使う方針を押し通したい。そんな理由で、進法を使ってみることにした。
すると、驚愕の事実が分かった!
『驚愕の事実1: は2進法でと表せる』
これは、
と表せるということなので、あからさまにが怪しい*7。
推理小説にしたら、「犯人臭」出し過ぎもいいところじゃないか~
これで、が犯人(正解)だったら、推理小説としては残念なレベル……
初見で感じた「オシャレ感」も3割りくらい引っ込めたい気持ちに*8……
一応結末は、この記事の最後ということで……
さて、計算結果1を改めて見つめて、桁の小さい方から大きい方へと指でなぞってやる。すると、ちょうど真ん中にあるが「壁になってる感」がある。
そこで少し観察をして、進法の定義に立ち返りつつ進むことにした。
突然だが、ここで以下の数々を見比べていただきたい。
と
と
と
さて、右と左の数の関係は何か?
答えは、「右に書いてある数は、左に書いてある数において、中央にあるより右側の数字だけを取り出したもの」でした。言ってみると、右の数は「の壁のこちら側」の世界である。
なぜ、「の壁のあちら側*9」を捨てたのか?
答えは、割りとシンプルで、で割れる回数が等しいからだ。つまり、
「とし、がでないとする。
このとき、
という2進数を考えると、をで割れる最大回数は、に一致する。」
このことがすぐわからない時は、進数の場合を考えるといいかも。
例えば、進数でと数を考えると、
なので、とはで割れる回数は等しい。
と、こんな感じだ。
以上をまとめて、
『定理2:進法において、をでない自然数とする。このとき、*10を2で割り切れる最大回数は、のものと一致する。』
と分かった!
これを応用すると、からまでの数に含まれる素因数の個数が知りたいときは、
と
と
と
と置き換えて調べればいいと言える。このことから、ならば、の偶奇と、の偶奇は一致していると分かる。
というわけで、の場合は簡単に調べられるので、ステップ3へGO!
ステップ3:解法(のとき、が奇数であること)
の場合、定理2より、
とは、で割り切れる回数が等しい*11。
よって、が1から31までのの偶奇を調べれば、この問題はほとんど解けたようなものと言えるだろう。実際は、なので、は折り返し地点までのまで調べれば十分十分!そこで、以下、とする。
ここで、が進法でと表せることにジッと注目した。
は仮定より、進法でと表せる。
後は、とが2で割り切れる回数が等しいことを示せば良さそうだ。もうほとんど自明かもしれないけど、一応計算をつけておく。
をで割れる最大の回数がの場合、かつなので、
この計算から、は進数で表すと、その下桁はに一致する。
従って、とがで割り切れる最大の回数は等しい。
これより、がで割り切れる最大の回数はと等しいので、
が奇数であることがわかる。
ここまでの話は、そのまま一般化できて、次の定理が成り立つ。
『定理3:自然数が進法でとのみで表せるとき、に対して、は奇数。』
ステップ4:解法(が偶数であること)
残すは、の場合に、が偶数になることを示したら終わりだ。これも進法を使うとかなり楽。
ステップ2で示したように、まではとは、で割り切れる回数が等しい。
そこで、
と分解する。はステップ3の結果より奇数なので、とに含まれる素因数の個数を比較すれば終わりである*12。
仮定より、はでちょうど回割れる。次に、
となるので、はで回割り切れる。
従って、は2で1回割り切れるので偶数。
ステップ3の結果と合わせて、が偶数となる最小のはであることが示せた!
というわけで、なんと……最初から最後まで進法のターンでした!
ステップ4での結果も、ステップ3と同様にそのまま一般化できる気がしている*13。つまり、
『予想1:任意の自然数が、進法でと表せるとする*14*15、が偶数となる最少のは。』
正しかったら、これで完全な一般化になっているはず!
合ってたら超嬉しい!やほーーい!
*1:自分で解きたくなったから、途中までしか見てません。もし解法かぶりすぎてたら、動画をupした方、ごめんなさい。
*2:あくまで、数学は趣味と気分転換を兼ねてやってます。解けなくても、あんまり気にしないスタイル。
*3:私のときは、高校で2進法習った覚えがない
*4:と言いつつも、ステップ1の半分くらいは、自分用のメモor思考のスナップショットのつもり。
*5:それはもう、シャキーンと音が聞こえそうなくらいに、ピッタリと一致している。
*6:なんも知らない人の前でやると、「計算はえ~」という感嘆、または宇宙人を見たときのような驚き、どっちかの反応をされるかもしれません。なお、むやみに人を驚かすのは推奨してませんよ~
*7:単に怪しいとかいうレベルじゃなくて、「怪しい」。そう、「怪しい」のだ。
*8:それでも、残り7割残してるのは、がに対して対称的だから。やっぱり、それなりにオシャレなのかもしれない。
*9:のの壁の左側の数のこと
*11:含まれる素因数の個数が等しいと、すっきり言ってもいい。
*12:ここで、が自然数ではないじゃないかと一瞬気になるかもしれませんが、素因数として含まれるの個数だけを取り扱っているので問題にはなりません。おまけに、は「組み合わせの数」を表してるので、全てかけ合わせれば必ず自然数になる。
*13:眠いのと、疲れてきたのとで、また今度確認にするかも。気が向いたら、更新します。
*14:桁目に始めてが現れるとする
マスターデーモンの一般化、解の個数を調べてみた。
Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴
追記:証明に間違いがあるのに気づいたので、修正が必要です。
追記(2018/07/28):一般化されたマスターデーモンの解を与えるアルゴリズムができました。興味がある方は以下の記事を参考にしてください。
はじめに
前回の記事で、マスターデーモンを簡単に解く方法を紹介した。
ついでといってはなんだが、灘高の部誌(2008年度)で取り扱われていた一般化について少し考えてみたので書いておく。
なお、部誌の一般化のところはざっと目を通しただけでちゃんと読めてないので、細かいことを言われてもわかりません。(ごめんなさい。)
部誌に書いてあったマスターデーモンの一般化は次の通り。
「一般の自然数に対して、を満たすより大きい自然数を求めよ。」
というわけで、デーモンのがになっている模様。
また、同部誌では
「一般のに対してこのようなが無数に存在するか。」
が未解決問題として提示してあった。
ここでは、2番目の問題に答えてみる。
それでは、やってみる。
一般の自然数の場合の解の個数
の場合は自明なので、以下の場合のみ考える。
まず、の場合にならって、がで割り切れると仮定する。
仮定より、 がが割り切れるので、
①
次に、前回の記事と同様に計算することで
②
となる。
よって、①②式より、
③
となり、なんだかかなり一般的式が得られるが、③式がが満たすべき必要条件である。
そして、この式により、灘高の部誌で未解決とされていた二番目の問題が解決している!
すなわち、の場合を考えると、明らかに③式は成り立たたない。
よって、
となり、一般のの場合のマスターデーモンの解は有限であることが言えた。
より詳細には、が素数を用いて、
このとき、③式から導かれるの候補は、
ここで、任意の組は、の値をとり得る。
従って、一般のの場合のマスターデーモンの解の個数は、同じものを含む組み合わせの場合の数の問題を解けばわかります*3。
特に、を任意の素数として、の場合は、③式を満たす以上の自然数は のみである。
一般解についても調べてみようかと思ったけど、かなり大変そうなので少し疲れてきたので、ひとまずここまでということで。