流れる空の中で数学を。

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

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

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

前回に引き続き、問題2に挑戦してみた。問題は、次の通り。(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に挙げられている次の2つの動画を参考にした。

www.youtube.com

www.youtube.com

これらの動画の解説を、私が理解できた範囲で組み合わせ、まとめ直して翻訳してみた。基本的な解答は1つ目の動画、解答の仕上げの部分は2つ目の動画の方法を使わせていただきました。*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は問題の1つの解である。以降、これ以外の解を探すために、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とする。
 ここで、(トリッキーだが)2次方程式
x^2-bx+a-1=0
を考える!すると、a \lt 1より、判別式D=b^2-4(a-1)が正となるので、この2次方程式は2つの実数解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)単射であることが証明された。

最後の仕上げ

最後の仕上げは、冒頭で挙げた2つ目の動画から紹介させていただきます。*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
の3つである。

*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年国際数学オリンピックの問題1【解答・解説】

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

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

問題1. 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_03を法として分類してみる。

あるna_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)となる平方数は存在しないことがわかる。そのため、一旦あるna_n \equiv 2 (\mod 3)となると、それ以降この数列に平方数は現れない。したがって、a_nより後はすべて単調増加となるので、明らかに題意を満たさない。この観察結果から、a_n3を法としたときに、どのグループに属するかを考えていけばよさそうだと指針がたてられる。

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
 正の整数列に上限と下限が存在するので、鳩ノ巣原理より少なくとも1つの自然数Aが存在して、a_n=Aとなるnが無数に存在する。
 以上より、a_0が3の倍数の場合は題意を満たす。

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

最後に、a_0 \equiv 1(\mod 3)の場合を考える。数列を順番に作っていき、あるna_n \equiv 2(\mod 3)となれば、上に書いた証明から題意を満たさない。
そこで、すべてのnについて、a_n \equiv 1(\mod 3)となるa_0が存在すると仮定する。(以下でこの仮定から矛盾を導き、背理法により、いつか必ずあるna_n \equiv 2(\mod 3)となることを証明する。)
 今回は、平方数の最小性に着目した証明方法をとることにした。
まず \{ a_n \}の内、最小の平方数をl^2とおく。l^2より小さな平方数は存在しないので、数列の定義から、l^2の次の数列であるl \{ a_n \}の最小値となる。ここで、l^2の最小性から、ll^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)の場合、あるna_n \equiv 2(\mod 3)となるので、題意を満たさない。

解答

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

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

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

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

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


今日も誰かがどこかで、

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

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


何はともあれ、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


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


1次方程式へ向かって

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の極限をとると、その内1つは-c/bになると期待できる。
ここで、本当に答えるべき質問は、

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

の2つだろう。しかし、極限をとるにしても、解の公式の分母に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
以上のようにして、2次方程式の「解の公式の極限問題」は、「分子の有理化」というちょっと予想外のテクニックによって解決したのであった。

 

え……?

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

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

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

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

はじめに

『私は計算が苦手だ』

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

今回紹介するのは、ある自然数2,3,4,5,6,7,8,9,10,11の数で割り切れるか楽に判定する方法だ。「楽に」というのは、なるべく計算する量を減らすという意味だ。例えば、39で割れるか調べたい場合には、とある足し算を繰り返すだけでいいし、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で割り切れるか判定する方法

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

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

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

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

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

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

3、9で割り切れるか判定する方法

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

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

試しに、1719で割り切れるかやってみる。このとき、各位の和は
 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_j0から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_03で割り切れれば自然数N3で割り切れる。つまり、自然数Nの各位の数の和が3の倍数ならば、自然数N3の倍数になる。

同様に、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_19で割り切れればN9で割り切れる。つまり、自然数Nの各位の数の和が9の倍数ならば、自然数N9の倍数になる。

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

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

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

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


【問題】下3桁が321自然数で、11で割り切れる最小の数は何か。
【回答】32111の倍数でないので、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で割り切れれば、N11で割り切れる。つまり、自然数Nについて、「奇数桁の数の和」ー「偶数桁の数の和」が11で割り切れれば、自然数N11で割り切れる。

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

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

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

例えば、2317の場合、
 7×1+1×3+3×2-2×1=7+3+6-2=14=7×2
より、7で割り切れる。この例だとあまり計算が楽になった感じがしないかもしれないが、
239239456456のように、3桁ごとに繰り返す6桁の数が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で割り切れる。ここで、012個並んでいる。)

応用問題を作ったせいで、脇道にそれたが、判定方法の証明をやってみる。他の数で割れるか調べた時と同様に、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+……)
より、N7で割り切れるためには、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】

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

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

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

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

cを使わないでabを入れ替えるには、どうしたらいいか?
それには、aを完全にbに置き換えるのではなく、abの両方の情報を持つようにしておけばいい。つまり、aに半分だけスミス分bを入れる。
 a=a+b
ここまで来ればもう簡単なので、解答を書いてみる。わかりやすくするため、abに最初に入っている値を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)
 ⑤abを出力
という風に、変数c(ネオ)が休んでいても、abの値は無事に入れ替えられた(Mission complete!)

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

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

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

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

sky-time-math.hatenablog.jp

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

表記法の約束

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

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

例えば、111110111111^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+12進法で表したときの下k+1桁は、
  0^{k+1} - 1 0^k =1 0^k
となるので、mのものと一致する。
 従って、任意の自然数m (\lt 2^5)に対して、2015-m+1mの素因数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+126回まで割り切れる。従って、\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が偶数となる最小の自然数m2^5

以上!終わり!

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

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

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

*4:0自然数とする。

「2015東大理系 第5問」を2進法でガンガン解こうぜ!! ~ついでに一般化できたかも?~

Youtubeを散歩してたら……

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

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

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

2015東大理系 第5問

 問題は次の通り、

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

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

今回のあらすじ

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

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

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

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

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

 そこで、分母に現れるm2でぴったり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^121回だけ割れるから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}回割れる。
よって、

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

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

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

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

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

 『驚愕の事実1:  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が犯人(正解)だったら、推理小説としては残念なレベル……
初見で感じた「オシャレ感」も3割りくらい引っ込めたい気持ちに*8……
一応結末は、この記事の最後ということで……


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

突然だが、ここで以下の数々を見比べていただきたい。
 11111011111_211111_2
 11111011011_211011_2
 11111010100_210100_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_00でないとする。
このとき、
X=111110 x_4 x_3 x_2 x_1 x_0
という2進数Xを考えると、X2で割れる最大回数は、x_4 x_3 x_2 x_1 x_0に一致する。」

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


以上をまとめて、

『定理2:2進法において、x_4 x_3 x_2 x_1 x_00でない自然数とする。このとき、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_231=11111_2
 2014=11111011110_230=11110_2

         \cdots

 2015-2^5+1=11111000001_21=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の場合は簡単に
調べられるので、ステップ3へGO!

ステップ3:解法(m \lt 2^5のとき、 {}_{2015} C_{m}が奇数であること)

 m \lt 2^5の場合、定理2より、
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とする。

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

m2で割れる最大の回数が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+12進数で表すと、その下k桁は1 0 \cdots 0に一致する。
 従って、11111_2-m+1m2で割り切れる最大の回数は等しい。
これより、31\cdots(31-m+1)2で割り切れる最大の回数はm!と等しいので、

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

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

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

ステップ4:解法( {}_{2015} C_{2^5}が偶数であること)

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

ステップ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)!}はステップ3の結果より奇数なので、m2015-m+1に含まれる素因数2の個数を比較すれば終わりである*12

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

=11111011111_2-100000_2+1_2

=11111100000_2-100000_2

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

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

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

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

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

 

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

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

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

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

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

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

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

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

*9:20150の壁の左側の数のこと

*10:Nはある自然数

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

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

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

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

*15:Nはある自然数