2016-11-24

【ダイジェスト版】 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$ も自然数とする。

2016-11-23

「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$ はある自然数

2016-07-31

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

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

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:少し面倒なので、今はやりません。

2016-07-30

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

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

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

2016-07-29

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

数学雑感

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

はじめに

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

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

例えば、

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

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

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

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

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

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

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

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

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

　３．互いに素

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

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

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

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

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

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

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

流れる空の中で数学を。

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

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

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

表記法の約束

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

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

Youtubeを散歩してたら……

2015東大理系　第5問

今回のあらすじ

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

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

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

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

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

はじめに

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

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

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

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

夜が明けて

ネットで手に入る解答

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

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

最後に

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

はじめに

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

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

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

表記法の約束

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

Youtubeを散歩してたら……

2015東大理系 第5問

今回のあらすじ

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

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

ステップ３：解法（のとき、が奇数であること）

ステップ４：解法（が偶数であること）

はじめに

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

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

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

夜が明けて

ネットで手に入る解答

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

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

最後に

はじめに

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

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

2015東大理系　第5問

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

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

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

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

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