数学徘徊記

自由な数学ブログ。

半年ぐらい前に考えた問題がやっと解けた。

半年ぐらい前に考えた問題ですが、やっと解けました。
su-hai.hatenablog.com
これです。

解答
任意の奇数について、その倍数で各桁がすべて奇数となるようなものが存在することを示す。

任意の奇数を{a\cdot 5^b}(ただし{a}は5の倍数でない奇数)とおく。

まず、次の補題を示す。
任意の{n}について、すべての桁が奇数となる{k}桁の{5^n}の倍数が存在する。

数学的帰納法で証明する。
{n=1}のとき自明。(5が条件を満たす)
次に、{n=k}のときに命題が成り立つと仮定し、{n=k+1}のときも命題が成り立つことを証明する。
{5^k}の倍数で、各桁が奇数であるものを{m}とおく。
このとき、{1\cdot 10^k+m,3\cdot 10^k+m,5\cdot 10^k+m,7\cdot 10^k+m,9\cdot 10^k+m}はすべて各桁が奇数となる{k+1}桁の数だが、このうち1つは{5^{k+1}}の倍数であることを示す。
{1\cdot 10^k+m,3\cdot 10^k+m,5\cdot 10^k+m,7\cdot 10^k+m,9\cdot 10^k+m}をそれぞれ{5^k}で割ると、{1\cdot 2^k+\frac{m}{5^k},3\cdot 2^k+\frac{m}{5^k},5\cdot 2^k+\frac{m}{5^k},7\cdot 2^k+\frac{m}{5^k},9\cdot 2^k+\frac{m}{5^k}}となるが、{2^k}は5の倍数でないため、これらはそれぞれ5を法として互いに異なる。
よって、{1\cdot 2^k+\frac{m}{5^k},3\cdot 2^k+\frac{m}{5^k},5\cdot 2^k+\frac{m}{5^k},7\cdot 2^k+\frac{m}{5^k},9\cdot 2^k+\frac{m}{5^k}}のなかに5の倍数が存在するため、{1\cdot 10^k+m,3\cdot 10^k+m,5\cdot 10^k+m,7\cdot 10^k+m,9\cdot 10^k+m}のうち1つは{5^{k+1}}の倍数であることが証明された。

そして、すべての桁が奇数となる{a\cdot 5^b}の倍数が存在することを示す。
まず、{5^b}の倍数ですべての桁が奇数となる{b}桁の奇数を{x}とおく。
また、鳩ノ巣原理により、{\{0,1,10^b+1,10^{2b}+10^b+1,\cdots ,10^{(a-1)b}+10^{(a-2)b}+\cdots +1\}}のなかには{a}で割った余りが等しいものが存在し、それぞれの差を{10^{kb}+10^{(k-1)b}+\cdots +10^{lb}}とおけば、これを{10^{lb}}で割ったものは{a}の倍数である({a}は5の倍数でない奇数のため)。それを{y}とおく。
このとき、{xy}は各桁がすべて奇数である。よって証明された。

2017JJMO本選模試を解いてみよう(後半)


では、問4と問5の解答です。

問4

これは、点{X}を置けるかどうかがカギになります。
所見でとれたらスゴいです。

解答

f:id:yootaamath:20161204151909p:plain
対称性より、点{P,A,B}{Q,A,D}はこの順に並ぶと仮定してよい。
{\triangle ABQ}の外接円と直線{PQ}が交わる点を{X}とする。
このとき、{\angle PDA=\angle ABC=\angle AXQ}より、
4点P,D,A,Xは同一円周上にある。
よって、方べきの定理を使って
{
\begin{eqnarray}
PD\cdot PC+QB\cdot QC&=&PA\cdot PB+QA\cdot QD \\
&=& PQ\cdot PX+PQ\cdot QX\\
&=& PQ(PX+XQ)\\
&=& PQ^2
\end{eqnarray}
}
よって示された。

問5

これは、数学セミナーの2015年11月号の「エレガントな解答をもとむ」から出題。
問5らしい問題ではないでしょうか。

解答

「2点間のとりえる距離が2種類になる」という条件を{P}とする。
正五角形の頂点は{P}を満たすので、{n\geq6}のとき{P}を満たす配置は存在しないことを示す。
まず次の補題を示す。
補題. もし{P}を満たす6点からなる配置が存在したとすれば、そのなかに正三角形が含まれる。
証明. 配置の中のある点{X}に注目する。この頂点とほかの5点とのそれぞれの距離は2種類なので、5つの点のなかに、同じ長さの距離をとる3点が存在する。これを{A,B,C}とし、{XA=XB=XC=a}とおく。もし{AB,BC,CA}の中に長さが{a}となるものが存在したとすれば、一辺が{a}の正三角形が含まれる。またそうでないときは、{AB=BC=CA}となるので、{ABC}が正三角形となる。よって示された。

つぎに、正三角形が存在することが分かったので、正三角形に点を追加する方針で考える。
正三角形に点を追加して{P}を満たすようにするとき、新しく点を追加できる位置は下の図のような場所しかない。
f:id:yootaamath:20161204153534p:plain
6点以上追加する場合、正三角形に3点以上追加する必要がある。{P}を満たすためには新しくできる長さを同じにする必要があるため、考えられる配置は次の3つに限られる。
f:id:yootaamath:20161204153549p:plain
しかし、これらはすべて{P}を満たさない。よって6点以上からなる配置は存在しない。

補足

証明で使われた補題は、ラムゼーの定理と呼ばれています。
mathtrain.jp

2017JJMO本選模試を解いてみよう(前半)

というわけで解説します。今日は問1から問3まで。

今思えば少し簡単すぎた…。

問1

2016年の問1は、問1のくせに簡単ではなかったので、その傾向を反映させてみました。

解答

f:id:yootaamath:20161201202931p:plain

図のように、三角形{ADE}{BMC}が合同になるように点{E}をとる。四角形{DCEM}は平行四辺形なので、{\angle DAE=\angle CBM=\angle CDM=\angle DCE}である。従って、4点{A,D,E,C}は同一円周上にある。円周角の定理により{\angle ACD=\angle AED=\angle BCM}である。

問2

そろそろN(整数論)が出るかと思ったので、出してみました。
(といってもC(組合せ)やA(代数)の要素も強い)

解答

等式\(ab+a+b=(a+1)(b+1)-1\)より、この黒板Xに書くことのできる数に1を加えた数の全体は、別の黒板Yに次の規則のもとで書くことのできる数の全体に一致する。
 始めに2,3が書かれている。
 黒板にすでに書かれている二つの数の積を書き加えることができる。
このとき、黒板Yに書くことのできる整数は、\(2^n\cdot 3^m\)の形の数であり、\(13121+1=2\cdot 3^8\),\(12131+1=2^2 \cdot 3^2 \cdot 337\)だから、13122を黒板Yに書くことはできるが、12132を書くことはできない。よって、13121を黒板Xに書くことはできるが、12131を書くことはできない。

問3

ちょっとこれは簡単すぎちゃうか?

\[\frac{1}{2}(a+b)^2+\frac{1}{4}(a+b)\geq a\sqrt{b}+b\sqrt{a}\]

まず左辺は\(\frac{1}{2}(a+b)\)でくくれます。

しかも右辺は\(\sqrt{ab}\)でくくれます。

これは相加相乗平均の不等式しかない!

証明

相加相乗平均の不等式より、
\[\frac{1}{2}(a+b)\geq \sqrt{ab} \hspace{3.5em} \cdots①\]
また、
\[\left( \sqrt{a}-\frac{1}{2}\right) ^2+\left( \sqrt{b}-\frac{1}{2}\right)^2 \geq 0\]
より
\[a+b+\frac{1}{2} \geq \sqrt{a}+\sqrt{b}\hspace{3.5em} \cdots②\]
よって、①と②を辺々掛け合わせて結果を得る。

 

問4と問5はもう少し時間がかかるかな?というところです。

特に問5は時間がかかりそう。

ブログ移転しました。

ブログをlivedoorからhatenaに移転しました。
引き続きよろしくお願いします。

問題コーナー(第2回)解答

では解答発表です。
三角形\(ABC\)の外心を\(O\)とし、辺\(BC,CA,AB\)の中点をそれぞれ\(M_A,M_B,M_C\)とする。
このとき三角形\(AOM_A,BOM_B,COM_C\)の外接円は点\(O\)以外の1点で交わることを示せ。
mon2q
円に関する反転を用いた解法です。
mon2

点\(M_A,M_B,M_C\)をそれぞれ三角形\(ABC\)の外接円で反転させます。
このとき、点\(M_A,M_B,M_C\)はそれぞれ図の点\(A',B',C'\)に移ります。
(点\(A',B',C'\)は、直線\(B'C',C'A',A'B'\)がそれぞれ点\(A,B,C\)で三角形\(ABC\)の外接円に接するような点)

なぜなら、たとえば\(M_A\)に注目するとき、
\(\angle OM_AB=\angle OAB\)より\(\triangle OM_AB\simeq \triangle OAB\)だから
\(OM_A\cdot OA'=OB^2\)となるからです。 \(M_A,M_B\)についても同様です。

よって、三角形\(AOM_A,BOM_B,COM_C\)の外接円は、反転によって
それぞれ直線\(AA',BB'CC'\)に移ります。

そして、
\[\frac{A'B}{BB'} \cdot \frac{B'A}{AC'} \cdot \frac{C'C}{CA'} = 1\]
であるので、チェバの定理の逆により、この3つの直線は1点で交わります。 

よって、反転する前の元の図形、三角形\(AOM_A,BOM_B,COM_C\)の外接円は1点で交わります。 

マスターデーモンに挑戦

数学界で「マスターデーモン」というともうあれしかない、恐ろしい奴です。

1990 IMO 問3
\(\cfrac{2^n+1}{n^2}\)が整数となるような1より大きい整数\(n\)をすべて求めよ。

見た目はシンプルで、中学生も簡単に理解できる問題なのに、
世界中の高校生を悩ませた、デーモン的な存在。 

これの攻略をしていきます。 

思考過程

まずは、\(n\)に\(2,3,4,5,\cdots\)と代入していきます。
そうすると、\(n\)が偶数だとダメだということが見えてきます。(分子が奇数、分母が偶数となるため)

 

\(n=15\)くらいまで計算しても、\(n=3\)のときしか整数とならないので、
これが答えかな…?という見当をつけておきます。

 

しかし分母が\(n^2\)というのは考えにくいなあ。。。

 

ここで

su-hai.hatenablog.com

を使うことを考えると、
\(n\)が3の倍数であることを示せばいいのではという見当がつきます。

 

なぜなら、\(n\)は奇数だということが分かっているので、
\(2^n+1=2^n+(-1)^n\)であり、LTE補題を適用するには
\(2-(-1)=3\)の倍数であることが必要だからです。

 

ここから、こういう発想を思いつくことが難しいのですが、
\(n\)の最小の素因数\(p\)を取ります。(\(n\)は奇数なので\(p \geq 3\)です。)

 

このとき、\(\frac{2^n+1}{n^2}\)が整数なので
\(2^n \equiv -1 \pmod p\)、そして
\(4^n \equiv 1 \pmod p\)であることがわかります。

 

\(4^{p-1} \equiv 1 \pmod p\)

 

よって、\(n\)と\(p-1\)の公約数が4の位数となるわけですが、
\(p\)は\(n\)の最小の素因数なので、\(\gcd(n,p-1)=1\)です。

 

ここが少しわかりにくいと思うので、解説します。
もし\(n\)と\(p-1\)が2以上の公約数を持ったとすると、
それは\(p-1\)の約数なので\(p\)より小さいことになりますが、
\(p\)は\(n\)の最小の素因数なので、そんな\(n\)の約数は存在しないからです。

 

したがって\(\gcd(n,p-1)=1\)なので、これが4の位数となり、
すなわち\(4 \equiv 1 \pmod p\)が成り立つので、\(p=3\)です。

 

これで\(n\)が3の倍数であることがいえました。

 

というわけで、LTEの補題を使います。

 

\({\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+{\rm ord}_p n\)

 

LTE補題に、\(p=3,x=2,y=-1\)を代入して
\({\rm ord}_3 (2^n-(-1)^n) = {\rm ord}_3 (2-(-1))+{\rm ord}_3 n\)
\({\rm ord}_3 (2^n+1) = {\rm ord}_3 n + 1\)

 

また、\({\rm ord}_3 n^2 = 2{\rm ord}_3 n\)

 

\(\frac{2^n+1}{n^2}\)が整数なので、
\({\rm ord}_3 (2^n+1) \geq {\rm ord}_3 n^2\)より
\({\rm ord}_3 n + 1 \geq 2{\rm ord}_3 n\)
\(1 \geq {\rm ord}_3 n\)
また\(n\)は3の倍数なので\({\rm ord}_3 n \leq 1\)であることから、
\({\rm ord}_3 n = 1\)がわかります。

 

これで\(n\)に結構な制約ができました。

 

こっからどうすればいいのか、僕は手が止まりましたが…。
同じようなステップを進めてみましょう。

 

\(n=3\)のときは問題の条件を満たすので、\(n>3\)と仮定します。

 

\(n\)の2番目に小さい素因数\(q\)を取ります。\(q \geq 5\)です。

 

\(4^n \equiv 1 \pmod q, 4^{q-1} \equiv 1 \pmod q\)
がそれぞれ成り立ち、\(n\)と\(q-1\)の公約数が4の位数となるわけですが、(\(p=3\)の証明と同様)

 

\(\gcd(n,q-1)=1 or 3\)が成り立ちます。(\(q\)は2番目に小さい\(n\)の素因数なので)

 

しかし\(\gcd(n,q-1)=1\)のときは\(4 \equiv 1 \pmod q\)となり\(q=3\)となってしまい、
これはおかしい。

 

なので\(\gcd(n,q-1)=3\)がわかります。
\(4^3\equiv 1\pmod q\)より\(q\)は63の素因数、このうち\(q>3\)を満たすのは\(q=7\)のみです。

 

しかし\(n\)は3の倍数なので\(p=3k\)(\(k\)は整数)とおけ、
\(2^n+1\equiv 2^{3k}+1 \equiv 8^k+1 \equiv 1+1 \equiv 2 \pmod 7\)
となり、これは\(2^n+1\)が\(n^2\)で割り切れることに矛盾します。

 

よって\(n>3\)という仮定が間違っていることがわかり、背理法
解は\(n=3\)のみということがわかります。


結論。
難しい。

実際、LTE補題を使う問題は中~高難度のものばかりです。
もしあなたが高レベルに到達したいと思っているのならば、
これは知っていて損はありません。 

LTEの補題

更新が遅れました。
学園祭、定期試験などあり、少し忙しかったので。。。すいません。

LTEといっても、Long Term Evolution(携帯電話の通信規格)ではありません。 
Lifting The Exponent Lemmaです。

これは整数論の定理で、痒いところに手が届くような便利な定理です。僕は結構気に入ってます。

整数論はmodulo演算が基本ですが、それだけではやややりにくいことをこの定理はやってくれるので、
知ってると絶対プラスになると思います。(特に数オリ)

1:オーダーについて 

1.1 オーダーの定義

オーダーとは、簡単に言えば「何回割れるか」。しっかり定義を書くと、
0でない整数\(n\)と素数\(p\)に対して、次を見たす非負整数\(d\)が存在する。
\(n\)は\(p^d\)では割り切れるが、\(p^{d+1}\)では割り切れない。
この\(d\)のことを素数\(p\)に関する\(n\)のオーダーといい、\({\rm ord}_p n\)と書く。
というものです。

1.2 オーダーのちょっとした性質

\({\rm ord}_p (mn)={\rm ord}_p m + {\rm ord}_p n\)
\({\rm ord}_p (m+n) \geq \min \{ {\rm ord}_p m, {\rm ord}_p n \}\) 

これが関係してくる問題の場合、普通にmodulo演算で\(\bmod p\)で考えると0になって、何回割れるかわからない…ということが多々あります。

そんなときにLTE補題が使えるかもしれません。

2:LTE補題

定理:
\(p\)を奇素数とする。\(x,y\)を、\(x \equiv y \pmod p\)であるが両方とも\(p\)の倍数ではない整数とする。このとき、正の整数\(n\) に対して、
\({\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+{\rm ord}_p n\)
パッと見では、うーん、というか、だから何?、という感じだと思います。
まあ、今回は紹介だけして、次の記事でバーンと使います。楽しみにしていてください。

3:証明

おもに3ステップで証明します。

3.1 \(n\)が\(p\)で割り切れないとき

\(x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1})\)
因数分解できます。

おっと、\((x-y)\)が出ましたね。LTE補題にするために、その右側について考えます。

\(x \equiv y \pmod p\)なので、
\((x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \equiv ny^{n-1} \pmod p\)
そして、\(n\)も\(y\)も\(p\)で割り切れないので、
\({\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1})=0\)
これで、右側のほうもわかりました。

よって、
\begin{eqnarray}
{\rm ord}_p (x^n-y^n) & = & {\rm ord}_p (x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \\
& = & {\rm ord}_p (x-y) + {\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \\
& = & {\rm ord}_p (x-y) + 0 \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p n 
\end{eqnarray}
が成り立ちます。(最後に、\(n\)が\(p\)で割り切れないことを使いました) 

3.2 \(n=p\)のとき

ここが少し難しい。

3.1と同じようにして、
\(x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1})\) 
因数分解し、\(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}\)について考えます。

で、ここから大変なんですけど、
\(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}\)をむりやり\(x-y\)で割ります。

そうすると
\(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}=(x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})+py^{p-1}\)
となります。 
なぜこうなるのか?これは、自分で展開してみるのが一番早いと思いますが、「右側が1ずつ大きくなっているが、うまく引かれて結局1が残る」という感じです。

\(x \equiv y \pmod p\)より、
\begin{eqnarray}
&& x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2} \\
& \equiv & \{1+2+\cdots +(p-1)\}y^{p-2} \pmod p\\
& = & \frac{p(p-1)}{2}y^{p-2}
\end{eqnarray} 

\(p\)は奇素数なので、\(\cfrac{p-1}{2}\)は整数となり、 \(\cfrac{p(p-1)}{2}y^{p-2}\)は\(p\)の倍数です。

つまり、\(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2}\)は\(p\)の倍数です。

では、 
\(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}=(x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})+py^{p-1}\)
の式に戻りましょう。

\(x \equiv y \pmod p\)より、\(x-y\)は\(p\)の倍数。
また\(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2}\)も\(p\)の倍数なので、
\((x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})\)は\(p^2\)の倍数です。

よって
\begin{eqnarray}
x^{n-1}+x^{n-2}y+\cdots+y^{n-1}&=&(x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})+py^{p-1} \\
& \equiv & py^{p-1} \pmod{p^2}
\end{eqnarray}
となり、\(y^{p-1}\)は\(p\)の倍数ではないので、
\({\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) = 1\)です。

よって
\begin{eqnarray}
{\rm ord}_p (x^n-y^n) & = & {\rm ord}_p (x^p-y^p) \\
& = & {\rm ord}_p (x-y)(x^{p-1}+x^{p-2}y+\cdots+y^{p-1}) \\
& = & {\rm ord}_p (x-y) + {\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \\
& = & {\rm ord}_p (x-y) + 1 \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p p \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p n
\end{eqnarray}

3.3 \(n\)が一般のとき

\({\rm ord}_p n\)で数学的帰納法を使います。

\(n=ap^m\)(ただし、\(a\)は\(p\)で割り切れない整数)とおき、
\({\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+m\)    …①
となることを証明します。(\({\rm ord}_p n=m\)より)

\(n\)が\(p\)で割り切れない場合は3.1で証明したので、
\(m=0\)のとき、①は成り立ちます。

そして、\(m=k\)のとき①が成り立ったら
\(m=k+1\)のときも①が成り立つことを証明します。

\(n=ap^{k+1}\)とおきます。
このとき、
\(x^n-y^n=x^{ap^{k+1}}-y^{ap^{k+1}}=(x^{ap^k})^p-(y^{ap^k})^p\)
です。なんか3.2が使えそうな感じがします。

実際、\(x^k-y^k\)は\(x-y\)で割り切れ、しかも\(x-y\)は\(p\)で割り切れるので、
\(x^k-y^k\)は\(p\)で割り切れます。
これは、3.2が使えることを意味します。

よって、
\begin{eqnarray}
{\rm ord}_p (x^n-y^n) & = & {\rm ord}_p ((x^{ap^k})^p-(y^{ap^k})^p) \\
& = & {\rm ord}_p  (x^{ap^k}-y^{ap^k}) +1\\
& = & {\rm ord}_p (x-y) + {\rm ord}_p k +1\\
& = & {\rm ord}_p (x-y) +k+1 \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p ap^{k+1}\\
& = & {\rm ord}_p (x-y)+{\rm ord}_p n
\end{eqnarray}

となり、(m=k\)のとき①が成り立ったら\(m=k+1\)のときも①が成り立つので
証明が完了しました。 

4 まとめ

けっこう大変だったと思いますが、最後まで読んでいただきありがとうございます。
使用例は次の記事で紹介しようと思っているので楽しみにしてください。