流れる空の中で数学を。

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

【割り算ネタ】2から11までの数で割れ切れるか、簡単に判定する方法

数学 プチ研究 オリジナル

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

はじめに

『私は計算が苦手だ』

そんなあなたに、今回は割り算のちょっとした裏技を紹介しようと思う。
もちろん、計算が得意な人も、知ってるとさらに得すると思う。

今回紹介するのは、ある自然数が2,3,4,5,6,7,8,9,10,11の数で割り切れるか楽に判定する方法だ。「楽に」というのは、なるべく計算する量を減らすという意味だ。例えば、3や9で割れるか調べたい場合には、とある足し算を繰り返すだけでいいし、2,4,5,8,10の場合は、ある桁数より上の桁の数は無視して調べられるといった具合だ。

たいていの人は小学校で、2,5,10で割り切れるか判定する方法を聞いたことがあるだろう。2,5,10で割り切れるか調べる方法が一番知られているとして、知名度順に割る数を並べると、おそらく、

　 \{ 2,5,10 \} \gt \{ 4,8 \} \gt \{ 3,9 \} \gt \{ 11 \} \gt \{ 7 \}

という順番になると思う。特に、7で割り切れるかの判定方法は、本で見たことなかったので、今回の記事のために作ってみた。便利さはともかくとして、そこそこレアな方法だと思う。
今回の記事では、割る数が2から11のすべての場合の判定方法を紹介するので、なんとなく素因数分解したくなったときには、ぜひ試してほしい。
そして、この記事を読み終えるころには、整数問題のちょっとした問題とかも作れたりするようになるだろう。

２、４、５、８、１０で割り切れるか判定する方法

ある自然数があったとき、2,4,5,8,10のどれかで割れるか調べたいとする。
これらの数は共通して、割られる数の下1桁~下3桁までを調べればいい。

 　2で割り切れる　⇔　１の位が0,2,4,6,8
 　4で割り切れる　⇔　下2桁が4で割り切れる
 　5で割り切れる　⇔　1の位が0か5
 　8で割り切れる　⇔ 　下3桁が8で割り切れる
　10で割り切れる　⇔ 　1の位が0

これらを証明してみよう。
まず、割られる自然数Nを1の位とそれ以外に分けて
　N=10a+b
と表す。ここで、a,bは0以上の整数で、bは0から9のいずれか。
　N=2×5a+b
より、第一項が2の倍数なので、後は、1の位の数であるbが2で割り切れれば（つまり、1の位が0,2,4,6,8ならば）、自然数Nも2で割り切れる。
同様に、5で割り切れるかどうか調べたいときも、
　N=5×2a+b
より、bが5の倍数（つまり、1の位が0,5ならば）、自然数Nは5で割り切れる。
ここまでの証明のポイントになっているのは、10=2×5と分解できることだ。そのため、2か5で割れ切れるか調べたいときは、10の位より上の桁は計算に無視していい。

次に、4で割れ切れるか調べる方法について説明する。この場合は、下2桁を調べる必要がある。それは、2や5のときと事情が違って、10は4で割り切れないからだ。ここでは、10の代わりに100の分解を使うことになる。つまり、
　100=10×10=(2×5)×(2×5)=4×25
と表せることに注目する。割られる数Nを1の位と10の位とそれ以外に分けて、
　N=100a+10b+c
と表す。ここで、a,b,cは0以上の整数で、b,cは0~9のいずれか。100=4×25より、
　N=4×25a+10b+c
と表せることより、第1項は4の倍数なので、10b+cが4で割り切れればNも4で割り切れる。つまり、自然数Nの下2桁が4で割り切れれば、Nも4で割り切れる。

8で割り切れるかどうかを調べる場合は、4で割り切れるかどうかを調べたときと同様にして、1000の分解(1000=10×100=(2×5)×(4×25)=8×125)を使って証明できる。

最後に、ある自然数Nが10(=2×5)で割り切れるかを調べるには、1の位が0の場合に限る。10で割り切れるには、2でも5でも割り切れる必要があるので、これら両方の場合に許される1の位の数は0に限られるからだ。

３、９で割り切れるか判定する方法

3,9で割り切れるか判定する方法は次の通り。

　3で割りきれる　⇔　各位の数の和が3で割り切れる
　9で割り切れる　⇔　各位の数の和が9で割り切れる

試しに、171が9で割り切れるかやってみる。このとき、各位の和は
　1+7+1=9
と9の倍数になるので、3でも9でも割り切れる。(実際、171=19×9となる。)
もう少し大きな数の例で、12345の場合は、
　1+2+3+4+5=15
　1+5=6
より、3で割り切れる。(実際、12345=3×4115=3×5×823)

まず、3で割り切れるかどうかの判定方法から証明してみよう。2,4,5,8,10で割り切れるかどうかを調べた時のことを振り返ると、1,10,100,1000,……という「単位」が2,4,5,8で割り切れるかどうかがポイントになっていた。
そこで、1,10,100,1000,……を3で割ってみた場合を調べることから始める。すると、
　1=3×0+1
　10=9+1=3×3+1
　100=99+1=3×33+1
　1000=999+1=3×333+1
　……
となる。つまり、10のべき乗(10^n)は3で割ると、1余る数になっている。
そこで、あるn+1桁の自然数Nを
　N=a_n×10^n+a_{n-1}×10^{n-1}+……+a_1×10^1+a_0
と表す。ここで、整数a_jは0から9のいずれか。ここで、100=3×33+1等を使うと、
　N=3×(33…3×a_n+3……3×a_{n-1}+……+3×a_1)+(a_n+a_{n-1}+……+a_0)
と表せる。ここで、第一項は3の倍数なので、残りのa_n+a_n-1+……+a_0が3で割り切れれば自然数Nも3で割り切れる。つまり、自然数Nの各位の数の和が3の倍数ならば、自然数Nも3の倍数になる。

同様に、9で割れるかどうか判定する場合は、
　1=9×0+1
　10=9+1
　100=99+1=9×11+1
　1000=999+1=9×111+1
　……
を用いて、
　N=a_n×10^n+a_{n-1}×10^{n-1}+……+a_1×10^1+a_0
　  =9×(11…1×a_n+1……1×a_{n-1}+……+1×a_1)+(a_n+a_n-1+……+a_0)
より、第1項が9の倍数なので、残りのa_n+a_n-1+……+a_1が9で割り切れればNも9で割り切れる。つまり、自然数Nの各位の数の和が9の倍数ならば、自然数Nも9の倍数になる。

１１で割り切れるか判定する方法

11で割り切れるか判定する方法も、3や9の場合とそこそこ似ている。

　11で割り切れる　⇔　「奇数桁の数の和」ー「偶数桁の数の和」が11で割り切れる

試しに、9185の場合だと、
　(5+1)-(9+8)=6-17=-11
より、9185は11で割り切れる。(実際、9185=5×11×167)
応用問題を1つやってみよう。


【問題】下3桁が321の自然数で、11で割り切れる最小の数は何か。
【回答】321は11の倍数でないので、4桁の数を調べればいい。
千の位をxとして、奇数桁の和ー偶数桁の和が11の倍数となればいいので、
　(1+3)-(x+2)=2-x=0
よって、2321が答え。(実際、2321=11×211。)

さて、この判定方法を証明してみよう。1,10,100,……を11の倍数を使って表してみる。
      1=1
    10=11-1
  100=10×10=(11-1)×(11-1)
        =11の倍数+1
1000=100×10=(11の倍数+1)×(11の倍数-1)
        =11の倍数-1
10000=1000×10
        =11の倍数+1
という風に、10^nは、
　10^n= 11の倍数+1 (nが偶数の時)
    10^n=11の倍数-1 (nが奇数の時)
となる。よって、n+1桁の自然数Nは、
　N=a_n×10^n+a_{n-1}×10^{n-1}+……+a_1×10^1+a_0
　   =11の倍数+( (-1)^n×a_n+(-1)^{n-1}×a_{n-1}+……-a_1+a_0 )
　   =11の倍数+( a_0+a_2+……) - (a_1+a_3+…)
より、( a_0+a_2+……) - (a_1+a_3+…)が11で割り切れれば、Nも11で割り切れる。つまり、自然数Nについて、「奇数桁の数の和」ー「偶数桁の数の和」が11で割り切れれば、自然数Nも11で割り切れる。

７で割り切れるか判定する方法

さて、ここまでで７を除いて、2から11までの数で割りきれるかの判定方法を紹介した。なぜ7を一番最後に持ってきたかというと、他の数ほど分かりやすい判定方法でないからだ。

　７で割り切れる　⇔　下の位から順番に1,3,2,-1,-3,-2を繰り返しかけて足したものが７で割り切れる

例えば、2317の場合、
　7×1+1×3+3×2-2×1=7+3+6-2=14=7×2
より、7で割り切れる。この例だとあまり計算が楽になった感じがしないかもしれないが、
239239や456456のように、3桁ごとに繰り返す６桁の数が7で割り切れることなんかは、この判定方法を使うとすぐに分かる。
ついでに、ちょっとした応用問題も作ってみる。

【問題】下から1,7,14桁目以外が0であるような14桁の自然数で、7で割り切れるもののうち、最小のものを求めよ。
【回答】
下から1,7,14桁目の数をa_{1},a_{7},a_{14}とすると、題位の自然数が7で割り切れるには、上に書いた判定方法より、
　a_1+a_7+a_{14}
が7で割り切れればいい。a_1,a_7,a_{14}をできるだけ小さくとるには、
　a_1+a_7+a_{14}=7
の場合を考えればよく、これを満たす自然数[tex:a_1,a_7,a_{14}]で題位の自然数を最小にするものは、a_{14}=1,a_7=0,a_1=6。([tex:10000000000006]は7で割り切れる。ここで、0は12個並んでいる。)

応用問題を作ったせいで、脇道にそれたが、判定方法の証明をやってみる。他の数で割れるか調べた時と同様に、1,10,100,1000,……を7の倍数を使って表してみる。結果だけを書いておくと、

           1=1
          10=7×1+3
        100=7の倍数+2
      1000=7の倍数-1
    10000=7の倍数-3
  100000=7の倍数-2
1000000=7の倍数+1

となり、以下、7の倍数に1,3,2,-1,-3,-2と繰り返す。
よって、n+1桁の自然数Nは、
　N=a_n×10^n+a_{n-1}×10^{n-1}+……+a_1×10^1+a_0
      =7の倍数+(a_0+3a_1+2a_2-a_3-3a_4-2a_5+……)
より、Nが７で割り切れるためには、a_0+3a_1+2a_2-a_3-3a_4-2a_5+……が7で割り切れればいい。つまり、下の位の数から順に、1,3,2,-1,-3,-2と繰り返しかけて足したものが7で割り切れるとき、元の数も7で割り切れる。

【マトリックス】変数aとbを入れ替えるのに、cは要るのか問題!?【増殖するb】

プログラミング 数学 オリジナル

プログラミング関連の絶版本・品切れ本をコチラから購入できます！

変数aとbの入れ替えとエージェントスミスについて

　変数aとbに異なる値が入っていて、それを入れ替えるアルゴリズムを書きましょう……というのは、プログラミングの入門書にありがちな問題で、ついさっきあるプログラミング言語の本を見ていたら、また書いてあった。

では、この問題の模範的な"間違え方"から紹介しよう。それが、
　①aとbに値を入力
　②a=b
　③b=a
　④aとbを出力
という解答*1。この間違え方をすると、本の著者や解答を知っている人にニヤニヤされるかもしれないので要注意だ！
　落とし穴は②でaにbの値を代入しているところで、代入した瞬間にaもbも全部bの値になってしまい、aの値が跡形もなくなっている。いわば、このbがマトリックスのエージェントスミスなのだ。
　このようなスミスの無限増殖を防ぐ方法として、たぶん一番よく書いてある解法は、余分な変数cを用意して、
　①aとbに値を入力
　②c=a
　③a=b
　④b=c
　⑤aとbを出力
として、aの値が上書きされる前にcに避けておけばいい。要は、cがネオである。
さて、このcないしネオは常に必要なのだろうか？そんなことを何となく考えていたら、cを使わない第2の解答が存在することに気づいた。ただし、a,bが整数や実数等の数値である場合に限るけど。この解答は、厚めの本とか開けるとたぶん書いてありそうだけど……あえて紹介してみる！

cを使わない解法とネオの休日

cを使わないでaとbを入れ替えるには、どうしたらいいか？
それには、aを完全にbに置き換えるのではなく、aとbの両方の情報を持つようにしておけばいい。つまり、aに半分だけスミス分bを入れる。
　a=a+b
ここまで来ればもう簡単なので、解答を書いてみる。わかりやすくするため、aとbに最初に入っている値をA,Bとして、各ステップでa,bに入っている値もカッコで囲って書いておく。
　①a(=A),  b(=B)
　②a=a+b(=A+B),  b(=B)
　③a(=A+B),  b=a-b(=A+B-B =A)
　④a=a-b(=A+B-A =B),  b(=A)
　⑤aとbを出力
という風に、変数c(ネオ)が休んでいても、aとbの値は無事に入れ替えられた(Mission complete!)

*1:プログラミングで=は左辺の変数に右辺の変数の値を代入するという意味。

【ダイジェスト版】 2015東大理系 数学 第５問の解法 【2進法】

数学 Youtube

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

前回の記事……なんか長いっ！

　1つ前の記事で、2015東大理系数学第5問を2進法を使ってガンガン解いた。

sky-time-math.hatenablog.jp

 　ただ、この記事はたくさん寄り道していて、問題を解きたいだけの人には、余計な情報*1が多い。そんなわけで、なるべく最短ルートで解けるように書き直してみた。

表記法の約束

解法に入る前に、2進法の表記について約束事をしておく。
前回の記事で、11111011111と数字が続き過ぎて見づらかったのを反省した。
では、約束事。

「2進法で同じ数字xがk回続くときは、指数を使ってx^kと表す」

例えば、11111011111は1^5 0 1^5のように表す。
計算しやすさ優先で、1^6=1^5 1みたいに書いたりもするけど、意味は同じ。
最後に、指数が0のときは、その桁が存在しないことにする*2。

なお、この表記法を他の人が使ってるかどうかは良く知らないし、面倒なので調べない。これは、「少なくともこのブログ内で使っている表記法」だ。

できるだけ最短ルートな解法

2016を2進法で表すと、1^6 0^5となる*3。

①m \lt 2^5の場合、
　mを2進法で表すと、その下k+1桁が1 0^kとなるような自然数k \lt 5が明らかに存在する*4。また、2015-m+1を2進法で表したときの下k+1桁は、
　 0^{k+1} - 1 0^k =1 0^k
となるので、mのものと一致する。
　従って、任意の自然数m (\lt 2^5)に対して、2015-m+1とmの素因数2の個数は等しい。また、
　{}_{2015} C_m= \frac{2015 \cdots(2015-m+1)}{m!}
　　　　= \frac{2015-m+1}{m} \cdot \frac{2015-m+2}{m-1} \cdots \frac{2015}{1}
と表せるので、m \lt 2^5のときは、{}_{2015} C_mは奇数。


②m=2^5の場合、
2015-m+1を2進法で表すと、
　1^5 0 1^5 - 1 0^5 +1 = 1^5 1 0^5 -1 0^5 =1^5 0^6
なので、 2015-m+1は2で6回まで割り切れる。従って、\frac{2015-2^5+1}{2^5}は偶数。
ここで①の結果より、{}_{2015} C_{2^5-1}は奇数なので、
　{}_{2015} C_{2^5}={}_{2015} C_{2^5-1} \frac{2015-2^5+1}{2^5}
は偶数となる。

よって、{}_{2015} C_mが偶数となる最小の自然数mは2^5■

以上！終わり！

*1:一般化ができるくらいには情報盛りだくさんで、これはこれで面白いと思うけど。{}_{31} C_mの偶奇と{}_{2015} C_mの偶奇が一致する話とかは、結構お気に入り。

*2:例えば、1^3 0^0 =1^3 =111

*3:今年はまだギリギリ2016年だから、覚えておくと豆知識として使えるかも。

*4:0も自然数とする。

「2015東大理系 第５問」を２進法でガンガン解こうぜ！！ ～ついでに一般化できたかも？～

数学 プチ研究 Youtube

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

Youtubeを散歩してたら……

　なんとなくオシャレ、かつあんまし時間のかからなそうな整数論の問題をYoutubeで見かけた*1。

【話題の一行問題】東大数学2015第5問【2015Cmが偶数】 - YouTube

というわけで、久々に更新。
　サクサクのおやつみたいに手軽に楽しめる問題なので、遊びたい人は自分でチャレンジしてみてください。ちょっとした気分転換になると思うよ！

2015東大理系　第5問

　問題は次の通り、

『 mを2015以下の正の整数とする。 {}_{2015} C_{m}が偶数となる最小の mを求めよ。』

　これを気楽に解いてみた*2。
　２進法を使って解いてみたのが、結構気に入ったので公開してみる。そう、２進法でガンガンいってるので、受験生は真似しない方がいいかも*3……
　要は、どこかの数学好きが、少しでも楽しくなればOKというスタンスなのだ。

今回のあらすじ

　ステップ１：m=2^nの場合にm!を調べてみた。これは寄り道。
　ステップ２：2進法を使う解き方の始まり～。そして、怪し過ぎる数を見つける！
　ステップ３： {}_{2015} C_{m}が奇数であり続ける、そのギリギリまで一掃する！
　ステップ４： {}_{2015} C_{m}がついに偶数に！ついでに一般化も？

ステップ１(寄り道): m=2^nのとき、m!は2で最大何回割れるか？

　最初にやった実験を紹介してみる。けど、この方針は途中で面倒になって放棄したので、興味ない人や解法だけ知りたい人はステップ２から読んだ方が良いです。
整数問題が苦手な人が、この問題を考える練習くらいにはなってるかも？*4

　 {}_{2015} C_{m}=\frac{2015\cdots(2015-m+1)}{m!}

が偶数かどうかを考えたいから、分子分母が2で何回割り切れるかを調べるのが基本方針になる。

　そこで、分母に現れるmが2でぴったりn回割り切れるm=2^n (n \in \mathbb{N})と表せる場合から考えてみる。
このとき、 m! = (2^n)! は2で最大何回まで割り切れるか？(素因数2の個数)

これを知りたくなって、冪のリズムに合わせて、

　 m! = (2^4)! =1 \times 2 \times (3 \cdot 4) \times (5 \cdot 6 \cdot 7 \cdot 8) \times (9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15 \cdot 16)

とかテンポ良く書いてみた。

それで、この式をちょっと観察すると、

「 (2^n +1) (2^n +2) \cdots (2^{n+1})に含まれる偶数は、 (2^{n-1} +1) (2^{n-1} +2) \cdots (2^{n})に現れる数1つ1つに2をかけたものに一致する」

と気づく。逆に言うと、
「 (2^n +1) (2^n +2) \cdots (2^{n+1})に含まれる偶数を全て取り出し、それぞれ2で割ってから、もう一度かけ直すと、 (2^{n-1} +1) (2^{n-1} +2) \cdots (2^{n})にピッタリ一致する*5。」

　この観察結果から、 (2^{n-1} +1) (2^{n-1} +2) \cdots (2^{n})に含まれる素因数2の個数をa_{n}とおいて考えてみる。まず、2^1は2で1回だけ割れるからa_{1}=1だ。一般のnのときは、上に書いた観察から、

　 a_{n+1}=a_{n}+2^{n}-2^{n-1}
と書けることが明らかなので、少し式変形して、
　a_{n+1}-2^{n}=a_{n}-2^{n-1}=\cdots=a_{1}-2^{0}=0
\iff a_{n}=2^{n-1}
つまり、 (2^n +1) (2^n +2) \cdots (2^{n})は2で、最大2^{n-1}回割れる。
よって、

『定理１: m! = (2^n)! は2で、最大2^{n}-1(=1+2+\cdots+2^{n-1})回割れる。』

と分かる。これを使うと、1から1024=2^{10}までの数を１つずつかけた数は、2で1023(=2^{10}-1)回割れるとかすぐにわかる*6。

ステップ２: 2015を2の冪を使って表してみたくなる。そして、2進法へ……

　分母に現れるmが2の冪の場合は、ステップ１で調べた。
次は分子だが、2015は偶数じゃない。けど、2の冪を使う方針を押し通したい。そんな理由で、2進法を使ってみることにした。

すると、驚愕の事実が分かった!

　『驚愕の事実１: 2015は2進法で11111011111_2と表せる』

これは、
　2015=2^{10}+2^9+2^8+2^7+2^6+2^4+2^3+2^2+2^1+2^0
と表せるということなので、あからさまに2^5が怪しい*7。
推理小説にしたら、「犯人臭」出し過ぎもいいところじゃないか～
これで、2^5が犯人(正解)だったら、推理小説としては残念なレベル……
初見で感じた「オシャレ感」も３割りくらい引っ込めたい気持ちに*8……
一応結末は、この記事の最後ということで……


　さて、計算結果１を改めて見つめて、桁の小さい方から大きい方へと指でなぞってやる。すると、ちょうど真ん中にある0が「壁になってる感」がある。
そこで少し観察をして、2進法の定義に立ち返りつつ進むことにした。

突然だが、ここで以下の数々を見比べていただきたい。
　11111011111_2と11111_2
　11111011011_2と11011_2
　11111010100_2と10100_2
さて、右と左の数の関係は何か?

　答えは、「右に書いてある数は、左に書いてある数において、中央にある0より右側の数字だけを取り出したもの」でした。言ってみると、右の数は「0の壁のこちら側」の世界である。

なぜ、「0の壁のあちら側*9」を捨てたのか?

答えは、割りとシンプルで、2で割れる回数が等しいからだ。つまり、

「x_i =0,1 (i=0,1,2,3,4)とし、x_4 x_3 x_2 x_1 x_0が0でないとする。
このとき、
X=111110 x_4 x_3 x_2 x_1 x_0
という２進数Xを考えると、Xを2で割れる最大回数は、x_4 x_3 x_2 x_1 x_0に一致する。」

　このことがすぐわからない時は、10進数の場合を考えるといいかも。
例えば、10進数で11111038400と数を考えると、
　32741038400=32741000000+38400
なので、32741038400と38400は10で割れる回数は等しい。
と、こんな感じだ。


以上をまとめて、

『定理２:２進法において、x_4 x_3 x_2 x_1 x_0を0でない自然数とする。このとき、x_N \cdots x_6 0 x_4 x_3 x_2 x_1 x_0*10を2で割り切れる最大回数は、x_4 x_3 x_2 x_1 x_0のものと一致する。』

と分かった！

　これを応用すると、2015から2015-2^5+1までの数に含まれる素因数2の個数が知りたいときは、
　2015=11111011111_2と31=11111_2
　2014=11111011110_2と30=11110_2

　　　　　　　　 \cdots

　2015-2^5+1=11111000001_2と1=1_2

と置き換えて調べればいいと言える。このことから、m \lt 2^5ならば、 {}_{2015} C_{m}=\frac{2015\cdots(2015-m+1)}{m!}の偶奇と、 {}_{31} C_{m}=\frac{31\cdots(31-m+1)}{m!}の偶奇は一致していると分かる。
というわけで、m \lt 2^5の場合は簡単に調べられるので、ステップ３へGO!

ステップ３：解法（m \lt 2^5のとき、 {}_{2015} C_{m}が奇数であること）

　m \lt 2^5の場合、定理２より、
2015\cdots(2015-m+1)と31\cdots(31-m+1)は、2で割り切れる回数が等しい*11。
　よって、mが1から31までの{}_{31} C_{m}の偶奇を調べれば、この問題はほとんど解けたようなものと言えるだろう。実際は、{}_{31} C_{m}={}_{31} C_{31-m}なので、mは折り返し地点までの16まで調べれば十分十分！そこで、以下、m\leq16とする。

ここで、31が2進法で11111_2と表せることにジッと注目した。
mは仮定より、2進法で x_4 x_3 x_2 x_1 x_0と表せる。
後は、11111_2-m+1とmが２で割り切れる回数が等しいことを示せば良さそうだ。もうほとんど自明かもしれないけど、一応計算をつけておく。

mを2で割れる最大の回数がkの場合、x_0=x_1=\cdots x_{k-1}=0かつx_k=1なので、

　11111_2-m+1

=11111_2-(m-1)

=11111_2-(x_4 \cdots x_{k+1} 1 0 \cdots 0_2 -1_2)

=11111_2-x_4 \cdots x_{k+1} 0 1 \cdots 1_2

 

この計算から、11111_2-m+1は2進数で表すと、その下k桁は1 0 \cdots 0に一致する。
　従って、11111_2-m+1とmが2で割り切れる最大の回数は等しい。
これより、31\cdots(31-m+1)が2で割り切れる最大の回数はm!と等しいので、

　　{}_{31} C_{m}が奇数であることがわかる。

ここまでの話は、そのまま一般化できて、次の定理が成り立つ。

『定理３:自然数nが2進法で11\cdots1_2と1のみで表せるとき、k=0,1,2,\cdots,nに対して、{}_{n} C_{k}は奇数。』

ステップ４：解法（ {}_{2015} C_{2^5}が偶数であること）

残すは、m=2^5の場合に、 {}_{2015} C_{m}が偶数になることを示したら終わりだ。これも2進法を使うとかなり楽。

ステップ２で示したように、k \lt 2^5までは2015\cdots(2015-k+1)と31\cdots(31-k+1)は、2で割り切れる回数が等しい。
そこで、
　{}_{2015} C_{m}=\frac{2015\cdots(2015-m+1)}{m!}
　　　　=\frac{2015\cdots(2015-m+2)}{(m-1)!} \cdot \frac{m}{2015-m+1}
と分解する。\frac{2015\cdots(2015-m+2)}{(m-1)!}はステップ３の結果より奇数なので、mと2015-m+1に含まれる素因数2の個数を比較すれば終わりである*12。

仮定より、m=2^5は2でちょうど5回割れる。次に、
　2015-m+1

=11111011111_2-100000_2+1_2

=11111100000_2-100000_2

=11111000000_2
となるので、2015-m+1は2で6回割り切れる。
従って、{}_{2015} C_{2^5}は２で１回割り切れるので偶数。

ステップ３の結果と合わせて、 {}_{2015} C_{m}が偶数となる最小の mは2^5であることが示せた！
というわけで、なんと……最初から最後まで2進法のターンでした！

ステップ４での結果も、ステップ３と同様にそのまま一般化できる気がしている*13。つまり、

『予想１:任意の自然数nが、2進法で x_N \cdots x_{k+2} x_{k+1} 0 1\cdots 1_2と表せるとする*14*15、{}_{n} C_{m}が偶数となる最少のmは2^{k-1}。』

正しかったら、これで完全な一般化になっているはず！
合ってたら超嬉しい！やほーーい！

 

*1:自分で解きたくなったから、途中までしか見てません。もし解法かぶりすぎてたら、動画をupした方、ごめんなさい。

*2:あくまで、数学は趣味と気分転換を兼ねてやってます。解けなくても、あんまり気にしないスタイル。

*3:私のときは、高校で２進法習った覚えがない

*4:と言いつつも、ステップ１の半分くらいは、自分用のメモor思考のスナップショットのつもり。

*5:それはもう、シャキーンと音が聞こえそうなくらいに、ピッタリと一致している。

*6:なんも知らない人の前でやると、「計算はえ～」という感嘆、または宇宙人を見たときのような驚き、どっちかの反応をされるかもしれません。なお、むやみに人を驚かすのは推奨してませんよ～

*7:単に怪しいとかいうレベルじゃなくて、「怪しい」。そう、「怪しい」のだ。

*8:それでも、残り７割残してるのは、11111011111が0に対して対称的だから。やっぱり、それなりにオシャレなのかもしれない。

*9:2015の0の壁の左側の数のこと

*10:Nはある自然数

*11:含まれる素因数2の個数が等しいと、すっきり言ってもいい。

*12:ここで、\frac{m}{2015-m+1}が自然数ではないじゃないかと一瞬気になるかもしれませんが、素因数として含まれる2の個数だけを取り扱っているので問題にはなりません。おまけに、{}_{2015} C_{m}は「組み合わせの数」を表してるので、全てかけ合わせれば必ず自然数になる。

*13:眠いのと、疲れてきたのとで、また今度確認にするかも。気が向いたら、更新します。

*14:k桁目に始めて0が現れるとする

*15:Nはある自然数

マスターデーモンの一般化、解の個数を調べてみた。

数学 数学オリンピック プチ研究 追記あり、一部未完成

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

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

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

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

sky-time-math.hatenablog.jp

 

はじめに

前回の記事で、マスターデーモンを簡単に解く方法を紹介した。

sky-time-math.hatenablog.jp

ついでといってはなんだが、灘高の部誌(2008年度)で取り扱われていた一般化について少し考えてみたので書いておく。
なお、部誌の一般化のところはざっと目を通しただけでちゃんと読めてないので、細かいことを言われてもわかりません。（ごめんなさい。）

 

部誌に書いてあったマスターデーモンの一般化は次の通り。 

「一般の自然数rに対して、\frac{r^n+1}{n^2}\in \mathbb{Z}を満たす1より大きい自然数nを求めよ。」

というわけで、デーモンの2がrになっている模様。 

 

また、同部誌では

「一般のrに対してこのようなnが無数に存在するか。」

が未解決問題として提示してあった。
ここでは、２番目の問題に答えてみる。
 

それでは、やってみる。

 

一般の自然数rの場合の解の個数

n=1の場合は自明なので、以下n \ge 2の場合のみ考える。

 

まず、r=2の場合にならって、r^n+1がn^2で割り切れると仮定する。
仮定より、 r^n+1がnが割り切れるので、

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

 
次に、前回の記事と同様に計算することで

　r^n+1
　　 \equiv (r-1)^n+1+1 \pmod{n}
　　 \equiv (r-2)^n+1+1+1 \pmod{n}
　　 \cdots
　　 \equiv r+1 \pmod{n} \cdots②
となる。 
 

よって、①②式より、

　 r+1\equiv 0  \pmod{n} \cdots③

となり、なんだかかなり一般的式が得られるが、③式がnが満たすべき必要条件である。
そして、この式により、灘高の部誌で未解決とされていた二番目の問題が解決している！

 

すなわち、 n \gt r+1の場合を考えると、明らかに③式は成り立たたない。
よって、

　n \le r+1

となり、一般のrの場合のマスターデーモンの解は有限であることが言えた。

 

より詳細には、r+1が素数p_1,p_2,\cdots, p_mを用いて、

r+1= p_1^{e_1} p_2^{e_2} \cdots p_{m}^{e_m}

と素因数分解できた*1として調べればいい*2。

 

このとき、③式から導かれるnの候補は、

　n=p_1^{k_1} p_2^{k_2} \cdots p_{m}^{k_m}

ここで、任意の組(k_1,k_2,\cdots,k_m)は、k_j=0,1,2,\cdots,e_jの値をとり得る。

 

従って、一般のrの場合のマスターデーモンの解の個数は、同じものを含む組み合わせの場合の数の問題を解けばわかります*3。

 

特に、pを任意の素数として、r=p-1の場合は、③式を満たす2以上の自然数nは n=p のみである。
一般解についても調べてみようかと思ったけど、かなり大変そうなので少し疲れてきたので、ひとまずここまでということで。

*1:mは適当な0以上の整数

*2:e_1,e_2,\cdots, e_mは適当な0以上の整数。

*3:少し面倒なので、今はやりません。

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

追記あり、一部未完成 数学 数学オリンピック

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:非常においしかったです。ちなみに文字を並びかえると、「塩焼きそば」になりそうでならない。

一分後の自分は何を考えているか？求めよ。

数学 雑感

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

はじめに

「自分は、自分だ。」（wikipedia:トートロジー）

人が考えることには、自分がまだ意識できてないレベルで、法則みたいなのがあるように思える。
 

例えば、 

１．ふと思いついたわりと意味不明なことをネットで調べてみてたら、同じことを誰かが書いていたり。(らっきょうグラタン、ミジンコのみじん切り、その他ホントにどうでもいいこと……など。)

２．ネット将棋で観戦してみたら、自分の考えてるのと同じ手が5~6手くらい連続して指されて、なんだかぞわっとしたり。

３．映画や本の感想だと、なんとなく自分の思ってたことが、amazonのレビュー欄なんかで既に文章化してあったり。

４．数学のテストや勉強で間違えやすいポイントがあると、教えられたわけでもないのに同じ間違え方をしたりする。それも結構な人数が。

 

なんとなく、思考の”素因数”みたいなものがあるような気がしてくる。
そして、おそらく普段意識してできている思考なんかはきっと、これらの”素因数”を掛け合わせた合成数なんだろう等と空想を進める。

 

あなたとわたしの素因数分解 

例えば、この思考の素因数描像を受け入れて、自分と違うタイプに出会ったときの対応を分類してみる。

　１．最大公約数をとるパターン

　２．最少公倍数をとるパターン

　３．互いに素

基本的なパターンとしてこの３つがあり、１は自分を削ってでも相手に合わせ、２はお互いを受け入れあっていき、３は我が道を行く。
(ここで、３だけが変化・成長しないわけではいことを注意しておく。時刻tでの太郎君と剛君の思考を自然数m(t), n(t)と同一視すると、m(t), n(t)が互いに素であるような時間発展が存在するからだ。)

 

いつかの未来に超賢くなった人類が、超スゴイ人工知能を作って、人間の思考を”素因数分解”して完全解析……なんてできてしまうんだろうか？
適当なことを言うと、後3000年くらいはできそうにない技術な気がするので、自分には関係の無い話だろうが。
まー、こんないらんことを考えてしまうのは、一時期ＳＦばっかり読んでたせいだろう。

 

まとめ、そしてこのブログについて

少なくとも今は、次の瞬間自分が何を考えているかなんてわからない。
数式にどっぷり浸かって遊んでると、少し前の自分が思い持つかなかったことが隅から隅まで見通せる瞬間があったりする。
そんなとき、数式はただの文字列ではなくなって、自分の内側に少し溶け込んでくる。
そうすると、少し目が覚めたような感覚もする。
まるで少し前の自分が寝ぼけていたんじゃないかって思えるくらいに、少し世界が違って見える。

 

逆に言えば、起きた直後は覚えていた夢を全く思い出せなくなるみたいなこともある。
そうやって、昨日考えていたや今考えていることも忘れていくんだろう。
（昔は微分積分がなかなかわからなかった自分も、今では何でわからなかったのかすらわからなくなっている。「何かが得意な人が、教えるのが上手とは限らない」。その一般的な原因の１つがここにあるんだろう。）
 

寝ぼけていろいろ書いたが、日々変わっていく思考に切なくなったようなので、今の自分が考えてることのスナップショットを時々残してみようかと思う。
 

雑感、考えたこと、数学、その他いろいろなことなんかを。