2017-09-24

【IMO2017】国際数学オリンピックの問題２【解答・解説】

2017年国際数学オリンピック(IMO2017)の問題２

前回に引き続き、問題２に挑戦してみた。問題は、次の通り。(http://www.imojp.org/challenge/から引用。)

$\mathbb{R}$ を実数全体からなる集合とする。関数 $f: \mathbb{R} \rightarrow \mathbb{R}$ であって、任意の実数 $x,y$ に対して
$f(f(x)f(y))+f(x+y)=f(xy)$
が成り立つものをすべて求めよ。

　今回はこの問題に半日くらい粘ってみたが、想像以上に手ごわく、残念ながら完答できなかった。完答できていないのに、なんでこの記事を書いてるんだとツッコミをもらいそうだが、これにはちょっとした事情がある。

日本語の解答・解説を求めて

　なかなか解答の糸口をつかめず、「吸収モード」*1に入っていた私は、ヒントや解説をネットで探していた。ところが、解説が英語のものしか見当たらないのである。英語が得意じゃない私は、解答を理解するまでに必要以上の時間を使ってしまった。そこで今回は、解答・解説を日本語に書き直してまとめておくことにした。これで、英語が苦手なみんなも、気軽に数学オリンピックの問題を楽しめるようになるはずだ。*2

今回の解答・解説は、Youtubeに挙げられている次の２つの動画を参考にした。

www.youtube.com

これらの動画の解説を、私が理解できた範囲で組み合わせ、まとめ直して翻訳してみた。基本的な解答は１つ目の動画、解答の仕上げの部分は２つ目の動画の方法を使わせていただきました。*3もし私の英語力不足で間違い等があったら、やさしく指摘していただけると助かります。それでは、本題へ。

基本的な観察

　まずは、「 $f(x)$ が定数関数であるような解」が存在するか考えてみよう。すべての $x$ に対し、 $f(x)=a \in \mathbb{R}$ とおくと、問題の関数等式より、
$a=f(f(x)f(y))=f(xy)-f(x+y)=a-a=0$
となる。したがって、 $f(x)=0$ は問題の１つの解である。以降、これ以外の解を探すために、 $f(x)$ は恒等的に $0$ でないとする。
　次に、 $x=y=0$ を代入してみる。*4
$f(f(0)f(0))+f(0+0)=f(0 \cdot 0)$
$\Leftrightarrow f(f(0)^2)=0$ ……①
つまり、 $f(0)^2$ という $f(x)$ の零点が存在する。*5
　ここで、 $f(0)=0$ であると仮定すると、面白いことが起きる。問題の関数等式に $y=0$ を代入すると、
$f(f(x)f(0))=f(0)-f(x)$
$\Leftrightarrow f(0)=f(0)-f(x)$
$\Leftrightarrow f(x)=0$
と $f(x)$ が恒等的に $0$ になってしまうのだ。したがって、恒等的に $0$ でない解を探すため、以後 $f(0) \ne 0$ とする。

零点の値を求めて

次に零点の値を調べる。つまり、 $f(r)=0$ となる実数 $r$ の値を求める。関数等式から、
$f(0)=f(f(r)f(x))=f(rx)-f(r+x)$
を得るが、 $f(0)$ は $0$ になってはいけないので、全ての $x$ について
$rx \ne r+x$
$\Leftrightarrow x(r-1) \ne r$
でなければいけない。そして、条件を満たす $r$ は実は $1$ に限る。理由は簡単で、もし $r \ne 1$ なら $x=r/(r-1)$ が上の式の等号を成立させてしまうからだ。
　結局、
$f(r)=0 \Rightarrow r=1$ ……②
であることがわかった。*6ここで、 $f(0)^2$ が零点であったことを思いだして(①式)、
$f(0)^2=1$
$\Leftrightarrow f(0)= \pm 1$
を得る。
　ところで、関数 $f(x)$ が問題の関数等式を満たすなら、 $-f(x)$ も関数等式を満たす。実際、このことは
$f(f(x)f(y))+f(x+y)=f(xy)$
$\Leftrightarrow -f(f(x)f(y))-f(x+y)=-f(xy)$
$\Leftrightarrow -f( [-f(x)][-f(y)])-f(x+y)=-f(xy)$
と確かめられる。そのため、 $f(0)=1$ となる解 $f(x)$ から、 $f(0)=-1$ となる解を構成することができる。そこで、以降は、
$f(0)=1$ ……③
として話を進める。

$f(x)$ の単射性

　 $f(x)$ が単射であることを証明する。ここがこの問題の山場であり、本質をつかなければいけない部分に思える。ここで、紹介する証明は、AoPS forumとかいうところ(?)でdnkywinさんが発表した方法らしい。
　ともかく、 $f(0)=1$ (③式)としたので、関数等式から
$f(f(x)f(1))=f(x)-f(x+1)$
$\Leftrightarrow f(0)=f(x)-f(x+1)$ (①、②式より、 $f(1)=0$ なので)
$\Leftrightarrow 1=f(x)-f(x+1)$
$\Leftrightarrow f(x+1)=f(x)-1$ ……④

という漸化式のような等式を得る。
　 $f(x)$ が単射であるというのは、 $f(a)=f(b)$ ならば $a=b$ であることを指す。
そこで、 $f(a)=f(b)$ とおく。ここで、④式から、 $f(a)=f(b)$ の両辺に $1$ を繰り返し足す（または引く）ことで、 $a \lt 1$ であるようにできるので、以下記号を適当に置き直して $a \lt 1$ とする。
　ここで、(トリッキーだが)２次方程式
$x^2-bx+a-1=0$
を考える！すると、 $a \lt 1$ より、判別式 $D=b^2-4(a-1)$ が正となるので、この２次方程式は２つの実数解 $r,s$ を持つ。*7また、解と係数の関係から、
$r+s=b$
$rs=a-1$ ……⑤
である。これで下準備は終わった。満を持して、問題の関数等式で $x=r,y=s$ を代入する！
$f(f(r)f(s))=f(rs)-f(r+s)$
$=f(a-1)-f(b)$ (⑤式より)
$=f(a)+1-f(b)$ (④式を使った。)
$=1$ (単射性を証明するときの仮定、 $f(a)=f(b)$ より。)
再び、④式を使って、
$f(f(r)f(s)+1)=0$
ここで、②式より、
$f(r)f(s)+1=1$
$\Leftrightarrow f(r)f(s)=0$
を得る。すなわち、
$f(r),f(s)$ の少なくとも一方が $0$
$\Leftrightarrow r,s$ の少なくとも一方が $1$ (②式より)

が言える。ここで、解と係数の関係の式⑤に立ち返ると、
$b=1+s$
$s+1=a$
等から、 $a=b$ を得る*8。よって、 $f(a)=f(b) \Rightarrow a=b$ が言えたので、 $f(x)$ は単射であることが証明された。

最後の仕上げ

最後の仕上げは、冒頭で挙げた２つ目の動画から紹介させていただきます。*9
　問題の関数等式で、 $y=-x$ とおくと、
$f(f(x)f(-x))=f(-x^2)-f(0)$
$\Leftrightarrow f(f(x)f(-x))=f(-x^2)-1$ 　(③式より)
$\Leftrightarrow f(f(x)f(-x))=f(1-x^2)$ 　(④式より)
ここで、関数 $f$ の単射性より、
$f(x)f(-x)=1-x^2$ ……⑥
を得る。
　同様に、問題の関数等式で $y=1-x$ とおくと、
$f(f(x)f(1-x))=f(x(1-x))-f(1)$
$\Leftrightarrow f(f(x)f(1-x))=f(x(1-x))$ 　(①、②式より、 $f(1)=0$ なので)
再び、関数 $f$ の単射性より、
$f(x)f(1-x)=x(1-x)$
$\Leftrightarrow f(x)(f(-x)-1)=x(1-x)$ (④式より)
$\Leftrightarrow f(x)f(-x)-f(x)=x-x^2$
ここで、⑥式を用いると、
$1-x^2-f(x)=x-x^2$
$\Leftrightarrow f(x)=1-x$
を得る。よって、③式の上の方で書いたように、 $f(x)$ が解なら $-f(x)$ も解である。よって、問題の関数等式を満たす解は、
$f(x)=0,1-x,x-1$
の３つである。

*1:問題を完全に見なかったことにして諦めるのではなく、さっさと解答を見て、そこから何かを吸収して成長するモードである。

*2:といっても、日本語に直してもなお、今回の問題は手ごわい。

*3:2つ目の動画は、 $f(x)$ の単射性の証明に飛躍があるように思えたので注意しておきます。

*4:この手の素朴な実験は、問題に取り掛かり始めるときの常套手段だ。

*5:同様に、 $x=y=2$ を代入すると、 $f(2)^2$ も零点であることがわかる。ところが、こちらの零点は、今回の解答では出番がない。

*6:零点が存在することは、①式で証明されているので、逆に $f(1)=0$ であることも当然言える。

*7:ここで、実数であることが重要だ。すぐ後で、関数 $f$ の変数として $r,s$ をとるからだ！

*8: $r=1$ としたが、 $s=1$ としても同様に $a=b$ が示せる。

*9:ここでは、元の動画と異なり、 $f(0)=1$ ととってあるので注意してください。

2017-09-21

【IMO2017】2017年国際数学オリンピックの問題１【解答・解説】

数学数学オリンピック

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

2017年国際数学オリンピック(IMO2017)の問題１

　なんとなく数学オリンピックの今年の問題を解いてみたくなったので挑戦してみた。問題は、数学オリンピック財団のサイト(http://www.imojp.org/challenge/)を参照しました。今回は、問題１の解答と解説をしていく。もし間違えていたら、優しく指摘してれると助かります。それと、もっと良い解法を教えてくれたら喜びます。
　では、問題を見てみましょう。

問題１. $a_0 \gt 1$ をみたすような各整数 $a_0$ に対して、数列 $a_0,a_1,a_2,...$ を以下のように定める:
$a_{n+1}= \{ \sqrt{a_n} 　 \sqrt{a_n}が整数のとき、$
　　　 $\{ a_n+3 　そうでないとき、 n=0,1,2,...$
このとき、ある $A$ が存在して $a_n=A$ をみたす $n$ が無数にあるような $a_0$ をすべて求めよ。

まずは観察と場合わけから

　問題の数列の作り方は、平方数になったときだけルートをとり、それ以外は3を足していくことで作られている。慣れるために、いくつかの例でためしてみよう。

$a_0=2$ のとき、 $2,5,8,11,...$
$a_0=3$ のとき、 $3,6,9,3,...$
$a_0=4$ のとき、 $4,2,5,8,...$
$a_0=5$ のとき、 $5,8,11,14,...$
$a_0=6$ のとき、 $6,9,3,6,...$

という具合になる。3ずつ増えていくという特徴を活かすために、まずは $a_0$ を $3$ を法として分類してみる。

ある $n$ で $a_n \equiv 2(\mod 3)$ となる場合

　まずは、平方数を調べる。
$0^2 \equiv 0 (\mod 3)$
$1^2 \equiv 1 (\mod 3)$
$2^2 =4 \equiv 1 (\mod 3)$
より、 $N \equiv 2(\mod 3)$ となる平方数は存在しないことがわかる。そのため、一旦ある $n$ で $a_n \equiv 2 (\mod 3)$ となると、それ以降この数列に平方数は現れない。したがって、 $a_n$ より後はすべて単調増加となるので、明らかに題意を満たさない。この観察結果から、 $a_n$ が $3$ を法としたときに、どのグループに属するかを考えていけばよさそうだと指針がたてられる。

$a_0 \equiv 0 (\mod 3)$ の場合

　次は、 $a_0 \equiv 0 (\mod 3)$ の場合を考える。この場合は、任意の $n$ に対して $a_n \equiv 0(\mod 3)$ であることが示せる。
　実際、 $a_n$ が3の倍数なら、 $a_n+3$ も3の倍数である。
　また、 $a_n$ が平方数の場合は、 $k$ を自然数として $a_n=k^2$ とおくと、素因数分解の一意性からある自然数 $l$ を用いて $k=3l$ と表せる。したがって、この場合も $a_{n+1}=3l \equiv 0 (\mod 3)$ となる。
　 $a_0 \equiv 0 (\mod 3)$ の場合は、 $a_n \equiv 2 (\mod 3)$ の場合とは異なり、数列 $\{ a_n \}$ には明らかな上限 $a_0^2$ が存在する。*1
　正の整数列に上限と下限が存在するので、鳩ノ巣原理より少なくとも１つの自然数 $A$ が存在して、 $a_n=A$ となる $n$ が無数に存在する。
　以上より、 $a_0$ が３の倍数の場合は題意を満たす。

$a_0 \equiv 1(\mod 3)$ の場合

最後に、 $a_0 \equiv 1(\mod 3)$ の場合を考える。数列を順番に作っていき、ある $n$ で $a_n \equiv 2(\mod 3)$ となれば、上に書いた証明から題意を満たさない。
そこで、すべての $n$ について、 $a_n \equiv 1(\mod 3)$ となる $a_0$ が存在すると仮定する。（以下でこの仮定から矛盾を導き、背理法により、いつか必ずある $n$ で $a_n \equiv 2(\mod 3)$ となることを証明する。）
　今回は、平方数の最小性に着目した証明方法をとることにした。
まず $\{ a_n \}$ の内、最小の平方数を $l^2$ とおく。 $l^2$ より小さな平方数は存在しないので、数列の定義から、 $l^2$ の次の数列である $l$ が $\{ a_n \}$ の最小値となる。ここで、 $l^2$ の最小性から、 $l$ と $l^2$ の間に、 $a_n \equiv 1$ であるような数は存在しないはずである。ところが、次に示すように、そのような数を構成することができてしまうのだ。
　仮定より、 $l$ はある自然数 $m$ を用いて $l=3m+1 (m \ge 2)$ と表せる。*2ここで、以下に定義する平方数 $L$ を考える。

$L:= \{ 3(m-1)+1 \}^2=(3m-2)^2$

この平方数 $L$ は、明らかに $l^2$ より小さい。また、

$L-l=(3m-2)^2-(3m+1)$
$=9m^2-15m+3$
$\gt 9m^2-15m$
$=9m(m-\frac{5}{3})$
より、 $m \ge 2$ であるから、平方数 $L \equiv 1 (\mod 3)$ は

$l \lt L \lt l^2$

を満たすが、このことは、 $l^2$ が最小の平方数であることに反する。
よって、背理法により、 $a_0 \equiv 1(\mod 3)$ の場合、ある $n$ で $a_n \equiv 2(\mod 3)$ となるので、題意を満たさない。

解答

以上をまとめて、題意を満たす $a_0$ は『３の倍数』である。

*1: $a_n$ は $3$ ずつ増加していくため $a_0^2$ を"飛ばして" $a_0^2$ より大きくなることができない。また、 $a_0^2$ まで増加できたとしても、定義より $a_{n+1}$ は $a_n$ より小さくなる。

*2: $l$ が平方数でないことから、 $l=4$ の場合つまり $m=1$ は仮定に反する。

2017-09-21

【極限!?】2次方程式の解の公式と１次方程式の解

数学プチ研究ヤフー知恵袋

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

今日もどこかで『にーえーぶんの……』

今日も誰かがどこかで、

『にーえーぶんのまいなすびー、ぷらすまいなするーとびーじじょうまいなすよんえーしー』

と呪文のように口ずさむ。聞き覚えのある数学フレーズ、そんな２次方程式の解の公式にまつわる話を今回はしてみよう。

何はともあれ、２次方程式は、
$ax^2+bx+c=0$
という方程式のことで、 $a \ne 0$ の場合のものを指す。
この $a \ne 0$ というのがさり気ない条件に聞こえるが、とっても大切だ。

冒頭で唱えた解の公式
$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$
も、うっかり $a=0$ としてみると、『 $0$ で割る』というタブーを冒してしまう。
ここで、1つの疑問が浮かんだ人もいるだろう。そう、

『 $a \rightarrow 0$ の極限をとったとき、解の公式はどうなる？』

という疑問だ。

ヤフー知恵袋にて

この「解の公式の極限問題」は、やはりというかネットで質問している人がいた。
それが、ヤフー知恵袋における次の質問だ。

detail.chiebukuro.yahoo.co.jp

問題こそ解決ずみになっているが、そのベストアンサーが、私にはなんともスッキリしないものに感じられた。そこで、今回の記事では、この疑問に真正面から立ち向かう。
といっても、ちょっとした計算をするだけれど……

１次方程式へ向かって

$a \rightarrow 0$ の極限をとると、もともとの2次方程式は、
$ax^2+bx+c \rightarrow bx+c=0$
となる。ここで、 $b \ne 0$ 場合を考えることにすると、これは1次方程式になる。
もちろんその解は、
$x=- \frac{c}{b}$
だ。したがって、2次方程式の解の公式
$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$
で $a \rightarrow 0$ の極限をとると、その内１つは $-c/b$ になると期待できる。
ここで、本当に答えるべき質問は、

①２次方程式の解の公式の極限をどうやってとるか？
②２つあった解の内、もう１つはどうなるか？

の２つだろう。しかし、極限をとるにしても、解の公式の分母に $a$ が残ったままではやりづらそうだ。そこで、ちょっと意外なテクニックが使えることに気づいたので紹介したいと思う。それは、いわば、

『分子の有理化』

とでも言えるテクニックである。

「分子の有理化」と「解の公式の極限」

普通学校では、「分母を有理化せよ」と問題に出される。今回は、あえてその逆である「分子」を有理化していく。何が起こるかは、下の計算を少し追ってみてほしい。(以下、複号同順。)一行ずつ丁寧にやっていく。
$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$
　 $=\frac{-b \pm \sqrt{b^2-4ac}}{2a}\frac{-b \mp \sqrt{b^2-4ac}}{-b \mp \sqrt{b^2-4ac}}$
　 $=\frac{b^2 - (b^2-4ac)}{2a(-b \mp \sqrt{b^2-4ac})}$
　 $=\frac{4ac}{2a(-b \mp \sqrt{b^2-4ac})}$
ここで、なんと、分母と分子の両方 $a$ が表れているので「約分」できてしまうのだ。「約分」すると、
$x=\frac{2c}{-b \mp \sqrt{b^2-4ac}}$
となる。「分母にルートタイプ」の解の公式である。覚えるには、

『にーしーわる、まいなすびー、まいなすぷらするーとびーじじょうよんえーしー』

と唱えればいい。
とにかく、こうなってしまえば、後は $a \rightarrow 0$ の極限をとるだけだ。
$x \rightarrow \frac{2c}{(-b \mp \sqrt{b^2})}$
　 $= \frac{2c}{-b \mp |b|}$
$|b|$ の絶対値を外すと、 $+b$ か $-b$ のいずれかなので、結局、解の公式に現れる2つの解の極限は、
$x \rightarrow \frac{2c}{-b \pm b}$
つまり、
$x \rightarrow -\frac{c}{b},\infty$
となる。*1
以上のようにして、２次方程式の「解の公式の極限問題」は、「分子の有理化」というちょっと予想外のテクニックによって解決したのであった。

え……？

『3次方程式の解の公式の極限がどうなるか』って？

気が向いたらやるかもしれませんし、面倒そうなのでやらないかもしれません。
それでは、また次の更新でお会いしましょう。

*1:ここで、 $\infty$ と書いたのは、 $c \ne 0$ のとき、分母が $0$ になると発散するという意味で書いた。 $c=0$ の場合は、もちろん「不定」になる。

2017-08-18

【割り算ネタ】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$ で割り切れる。

2017-04-18

【マトリックス】変数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:プログラミングで $=$ は左辺の変数に右辺の変数の値を代入するという意味。

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

2017年国際数学オリンピック(IMO2017)の問題２

日本語の解答・解説を求めて

基本的な観察

零点の値を求めて

の単射性

最後の仕上げ

2017年国際数学オリンピック(IMO2017)の問題１

まずは観察と場合わけから

あるでとなる場合

の場合

の場合

解答

今日もどこかで『にーえーぶんの……』

ヤフー知恵袋にて

１次方程式へ向かって

「分子の有理化」と「解の公式の極限」

はじめに

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

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

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

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

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

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

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

表記法の約束

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

Youtubeを散歩してたら……

2015東大理系 第5問

今回のあらすじ

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

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

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

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

$f(x)$ の単射性

ある $n$ で $a_n \equiv 2(\mod 3)$ となる場合

$a_0 \equiv 0 (\mod 3)$ の場合

$a_0 \equiv 1(\mod 3)$ の場合

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

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

2015東大理系　第5問

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

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

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

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