流れる空の中で数学を。

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

(a+b^3)/(ab)が整数となる整数a,bを全て求める

twitter 数学 整数問題bot

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

2015年ヨーロッパ数学オリンピック日本代表一次選抜試験より

久々に更新してみる。
twitterをのぞいてみたら、整数問題botの問題が目に入った。試しに解いてみたところ、読後感ならぬ解後感(?)が結構よかったので紹介してみたい。
下の問題である。

3分問題ということで、カップラーメンが出来上がるのを待っている間に解けるらしい。お手軽そうなのでやってみた。時間は測らなかったが、だいたい5分くらいで解けたような気がする。ちょっとした頭のストレッチになるので、挑戦したい人は以下の解答を見る前に自分でやってみてほしい。

解答

a+b^3がbで割り切れることから、aはある正の整数a_1を用いて、

a=a_1 b

と書ける。*1これを問題の式に代入すると、

\frac{a+b^3}{ab}=\frac{b(a_1+b^2)}{a_1b^2}
=\frac{a_1+b^2}{a_1b}

となる。ここで気づくのが、元の問題の分子に表れていたbの指数3が2に下がっていることだ。さらに、問題の式の形はこの指数の部分を除いて、変わっていない。 そんなわけだから、この置き換えを繰り返し行えば、指数をどんどん減らしていけそうだ。

a_1=a_2 bと置き換えると、*2
\frac{a_1+b^2}{a_1b}=\frac{a_2+b}{a_2b}

a_2=a_3 bと置き換えると、*3
\frac{a_2+b}{a_2b}=\frac{a_3+1}{a_3b} ……(☆)

となり、分子のbは指数が0になってしまい、ついに消えてしまった。

問題の式が整数となるためには、分子の値は分母の値より、大きくないといけない。よって、

a_3+1 \ge a_3b
(b-1)a_3 \le 1……（♪）

b \ge 1なので、この式が成り立つためには、b=1または2でなければならない。

①b=2のとき、

不等式（♪）より、a_3=1なので、
a_2=a_3 b=2
a_1=a_2 b=4
a=a_1 b=8

とa,bの値が2,8と求まる。このとき、

\frac{a+b^3}{ab}=\frac{8+2^3}{8*2}=1

となり、確かに整数になる。

②b=1のとき、

問題の式の値を、正の整数kとおくと、(☆)式より、
\frac{a_3+1}{a_3}=k

この式を変形して、

1=(k-1)a_3

この式を満たす正の整数の組(k,a_3)は明らかに、(2,1)のみである。
よって、

a=a_1=a_2=a_3=1

となり、(a,b)=(1,1)である。このとき、問題の式の値は2となる。

以上をまとめて、求める正の整数の組(a,b)は、

(a,b)=(1,1),(8,2)

の２つだけである■

*1:a+b^3 \equiv a \equiv 0 (\bmod b)より、明らか。

*2:a_2はある正の整数で、bの倍数になることは、aがbの倍数になることと同様に示せる。

*3:a_3はある正の整数で、bの倍数になることは、aがbの倍数になることと同様に示せる。

【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

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ととってあるので注意してください。

【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は仮定に反する。

【極限!?】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の場合は、もちろん「不定」になる。

【割り算ネタ】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も自然数とする。