読者です 読者をやめる 読者になる 読者になる

数学徘徊記

自由な数学ブログ。

最近解いたEGMOの良問(2017年のEGMO日本代表一次選抜試験の問題2)

最近解いた問題で、結構良問だったので紹介します。
2017年のEGMO日本代表一次選抜試験の問題2です。

問題

数列{a_1,a_2,\cdots}{a_1=1,a_{k+1}=a_{k}^2+1(k=1,2,\cdots)}と定める。
このとき、次の条件を満たす素数{p}が無数に存在することを示せ。

条件:{a_1,a_2,\cdots}の中に{p}の倍数が存在する。

問題解説

問題をわかりやすく解説してみます。

数列の各項を具体的に計算してみると、
{a_1=1}
{a_2=2}
{a_3=5}
{a_4=26=2\times 13}
{a_5=677}
{a_6=458330=2\times 5\times 45833}
{a_7=210066388901=41\times 1277\times 4012193}

と続いていきます。

そして、条件を満たす素数{p}というのは、
{p=2,5,13,677,45833,41,1277,4012193,\cdots}
です。

そのような素数が無数に存在することを示せばいいのです。
条件が弱そう。

というか、無数に存在しない、つまり有限個しかないとしたら
逆にびっくりです…。

方針

(解いているときの自分の心の声的な感じで)

数列の一般項をもとめる({a_n}{n}の式で表す)のは難しそう。

一般項を求めなくともわかるこの数列{a_1,a_2,\cdots}の性質を探してみよう。
何か進展がみられそう。やってみよう。

うーん。全然性質が見つからない。
ただ一つ見つかったことといえば、
{a_m \equiv a_n \pmod p \Rightarrow a_{m+1} \equiv a_{n+1} \pmod p}
(ただし、{m,n}自然数{p}素数
ということぐらい。

この見つかった性質からいろいろ進展させてみよう。
{a_m \equiv a_n \pmod p \Rightarrow a_{m+t} \equiv a_{n+t} \pmod p}
(ただしtは正の整数)
がいえる。

ってことは、{n=m+t}のとき、
{a_m \equiv a_{m+t} \pmod p \Rightarrow a_{m+t} \equiv a_{m+2t} \pmod p}
がいえる。
これを繰り返すと、
{a_m \equiv a_{m+t}\equiv a_{m+2t}\equiv a_{m+3t}\equiv \cdots \pmod p}
ということがわかる。
なんか使えそうになってきた。

あ、ひらめいたぞ。
{a_0=0}と拡張すると、{a_0^2+1=a_1}となって自然だ。
{a_0}はどんな数でも割り切れるから、
上の式に{m=0}を代入して
{a_0 \equiv a_{0+t}\equiv a_{0+2t}\equiv a_{0+3t}\equiv \cdots \pmod p}
より
{0 \equiv a_t\equiv a_{2t}\equiv a_{3t}\equiv \cdots \pmod p}
いい感じ。

しかし、条件を満たす素数{p}が無数に存在することをどう証明すればいいのだろう…?

とりあえず、素数が無数に存在することの証明みたいに、背理法を使おう。
条件を満たす素数{p}が無数に存在しないと仮定して、矛盾を導いてみよう。

とりあえず、条件を満たすような素数をそれぞれ{p_1,p_2,\cdots,p_n}とおいてみて…
{p_1,p_2,\cdots,p_n}のどれでも割り切れないような{a_x}はないかなあ。

あ、{a_{x-1}}{p_1,p_2,\cdots,p_n}の全てで割り切れればいいのか。
おっ、これはさっき示したアレが使える…!

よっしゃ、できた。

解答

すいません、長くなりました。解答です。

解答

条件を満たす素数{p}が無数に存在しないと仮定して、矛盾を導く。

ここで数列を{a_0=0,a_{k+1}=a_{k}^2+1(k=0,1,\cdots)}と拡張する。
{a_0^2+1=a_1}より、{a_1}以降の項の値は変わらない。

条件を満たすような素数をそれぞれ{p_1,p_2,\cdots,p_n}とおく。
また、1以上n以下の正の整数{i}に対し、{a_j}{p_i}で割り切れるような最小の正の整数{j}{f(i)}とおく。

このとき、
{a_m \equiv a_n \pmod p}のとき
{a_m^2+1 \equiv a_n^2+1 \pmod p}
{a_{m+1} \equiv a_{n+1} \pmod p}
が成り立つ。
これを繰り返すことにより、
{a_m \equiv a_{m+t}\equiv a_{m+2t}\equiv a_{m+3t}\equiv \cdots \pmod p}
が示される。

よって、{m}に0を代入して、
{0 \equiv a_t\equiv a_{2t}\equiv a_{3t}\equiv \cdots \pmod p}
である。

したがって、
{a_{f(1)f(2)\cdots f(n)}}{a_{f(1)},a_{f(2)},\cdots,a_{f(n)}}で割り切れる。
{f}の定義より、{a_{f(1)f(2)\cdots f(n)}}{p_1,p_2,\cdots,p_n}で割り切れる。

しかし、{a_{f(1)f(2)\cdots f(n)+1}}{a_{f(1)f(2)\cdots f(n)}}と互いに素であるから、これは{p_1,p_2,\cdots,p_n}のどれでも割り切れない。

明らかに{a_{f(1)f(2)\cdots f(n)+1}>1}より、{a_{f(1)f(2)\cdots f(n)+1}}{p_1,p_2,\cdots,p_n}以外に素因数を持つことになり、矛盾。

よって、背理法より、条件を満たす素数{p}が無数に存在することが証明された。
Q.E.D.

あとがき

整数論の問題にしては、面倒くさくなく、また程よい難易度で、かなりの良問だったと思います。こんな問題たくさん解きたい。

arctanの無限和の問題

近畿大学主催の数学コンテストの過去問に,面白いものがあった.
第13回,B-3の問題である.
{\begin{eqnarray}
\sum^\infty_{n=1}\arctan\left(\frac{2}{n^2}\right)=\frac{3\pi}{4}
\end{eqnarray}}
を示せ.

arctanはtanの逆関数のことだが….

arctanのなかに{\frac{2}{n^2}}ってどうやって計算するんだ,て感じである.

この問題を解くために,まずはこのarctanの公式を説明する.
{\arctan a+\arctan b=\arctan\left(\frac{a+b}{1-ab}\right)}
この証明から.
tanの加法定理より
{\tan(\alpha+\beta)=\frac{\tan \alpha+\tan \beta}{1-\tan \alpha\tan \beta}}
ここで{\tan \alpha=a,\tan \beta=b}とおくと
{\begin{eqnarray}
\tan(\alpha+\beta)&=&\frac{a+b}{1-ab} \\
\alpha+\beta&=&\arctan\left(\frac{a+b}{1-ab}\right) \\
\arctan a+\arctan b&=&\arctan\left(\frac{a+b}{1-ab}\right)
\end{eqnarray}}
と目的の式が得られる.

この式をどうやって使うかがカギとなる.
うまい値を代入したらいいのだが….

答えを言うと, {a=1-n,b=1+n}を代入する.
こうすると{\frac{a+b}{1-ab}=\frac{2}{n^2}}より,
{\arctan(1-n)+\arctan(1+n)=\arctan\left(\frac{2}{n^2}\right)}となり,目的の式に近づく.

{n}が大きくなると{1+n}は正の方向に,{1-n}は負の方向に値が変化するので,
しかも{\arctan(-x)=-\arctan(x)}なので,
うまい具合に消えていきそうな気がする.

では解答行こう.

{f(x)=\sum^x_{n=1}\arctan\left(\frac{2}{n^2}\right)}
と定義する.
すると仮定より
{\begin{eqnarray}
f(x)-f(x-1)&=&\arctan\left(\frac{2}{x^2}\right) \\
&=&\arctan(1-x)+\arctan(1+x)
\end{eqnarray}}
である.

まず,次の等式を数学的帰納法により示す.
任意の自然数{x}において,
{f(x)=-\frac{\pi}{4}+\arctan x+\arctan(x+1)\cdots\clubsuit}
{x=1}のとき,
{\begin{eqnarray}
f(1)&=&\arctan 2 \\
&=&\arctan -1+\arctan 1+\arctan2 \\
&=&-\frac{\pi}{4}+\arctan x+\arctan(x+1)
\end{eqnarray}}
より{\clubsuit}の等式を満たす.
x=kのとき{\clubsuit}の等式を満たすと仮定する.このとき
{f(k)=-\frac{\pi}{4}+\arctan k+\arctan(k+1)}
また,
{\begin{eqnarray}
f(k+1)-f(k)&=&\arctan(1-(k+1))+\arctan(1+(k+1))  \\
&=&\arctan(-k)+\arctan(k+2) \\
&=&-\arctan k+\arctan(k+2) 
\end{eqnarray}}
より,
{\begin{eqnarray}
f(k+1)&=&f(k+1)-f(k)+f(k) \\
&=&-\arctan k+\arctan(k+2)+\left(-\frac{\pi}{4}\right)+\arctan k+\arctan(k+1) \\
&=&-\frac{\pi}{4}+\arctan(k+1)+\arctan(k+2)
\end{eqnarray}}
となるので,{x=k+1}のときも等式は成り立つ.
よって数学的帰納法により,{\clubsuit}の等式が成り立つことが証明された.

これができたらもう簡単である.
$\displaystyle \lim_{x \to \infty} f(x)$を求めればいいので,
{\begin{eqnarray}
\lim_{x \to \infty} f(x)&=&\lim_{x \to \infty} -\frac{\pi}{4}+\arctan x+\arctan(x+1) \\
&=&-\frac{\pi}{4}+\frac{\pi}{2}+\frac{\pi}{2} \\
&=&\frac{3\pi}{4}
\end{eqnarray}}
より問題の式が成り立つことが証明された.

なかなか意外性のある面白い問題だと思った.

近畿大学主催の数学コンテストにはほかにも面白い問題が出題されているので,興味のある方は調べてみてはどうかと思う.

2017をn進法で書き表したら各桁の和がn

鯵坂もっちょさんのこのツイートが気になったので、考察してみました。

2017を{n}進法でこう書き表したとします。
{n\geq 2017}のときは自明に成り立つので、{n<2017}とします。)
{2017=a_{m}n^m+a_{m-1}n^{m-1}+\cdots +a_{1}n+a_{0}}
ただし、{a_{m},a_{m-1},\cdots ,a_1,a_0}はそれぞれ0以上{n-1}以下の整数です。

すると各桁の和が{n}になるということなので、
{a_{m}+a_{m-1}+\cdots +a_1+a_0=n}
です。

以上まとめて、
{
  \left\{ \begin{array}{ll}
    a_{m}n^m+a_{m-1}n^{m-1}+\cdots +a_{1}n+a_{0}=2017 & \cdots① \\
    a_{m}+a_{m-1}+\cdots +a_1+a_0=n & \cdots②
  \end{array} \right.
}
となります。

ここで、①から②を引いてみましょう。
{a_{m}(n^m-1)+a_{m-1}(n^{m-1}-1)+\cdots +a_1(n-1)=2017-n}  …③
となります。

この左辺に注目です。

{n^k-1}{k}は正整数)というかたちがたくさんできましたが、
じつはこれらは{n^k-1=(n-1)(n^{k-1}+n^{k-2}+\cdots +1)}という風に因数分解できます。
つまり、{n^k-1}はすべて{n-1}で割り切れます。

なので、左辺は{n-1}で割り切れることが分かります。

③が成り立つためには、{2017-n}{n-1}で割り切れなければいけません。
{2017-n=2016-(n-1)}なので、

{2017-n}{n-1}で割り切れる {\Leftrightarrow} 2016が{n-1}で割り切れる

ということが分かります。

つまり、2017を{n}進法で書き表したら各桁の和が{n}になるとき、
{n-1}が2016の約数である必要があります。

ただし、必ずしも逆は成り立ちません。
{n-1}が2016の約数であっても、2017を{n}進法で書き表したら各桁の和が{n}になるとは限らない)
しかし、{2016=2^5\cdot 3^2\cdot 7}なので、2016の約数はたくさん(36個)あるので、
候補となる{n}はたくさんあり、それだけ条件を満たす{n}は多くなります。

では、2018を{n}進法で書き表したら各桁の和が{n}になるような{n}について考えましょう。
同じような方針で計算していくと、{n-1}が2017の約数である必要があります。

しかし、2017は素数です。n=2しか候補はありません({n<2018}なので)。
2017を2進法で表すと11111100001であり、各桁の和は7なのでこれは条件を満たしません。
というわけで、2018を{n}進法で書き表したら各桁の和が{n}になるような{n}はないのです。


というわけで、2017がこのような性質を持てたのは2016のおかげなんですね。
昨年の2016はいろいろな性質を持っていましたが、今年も「2016+1」としていろいろな性質がありそうです。

#だま氏の謎

来年の年賀状は何か変わったことをしたいなと思い、この企画をしました。
2017年賀状特設ページ!

#だま氏の謎 です。

これは、だま氏が5つの謎を提示し、みんなに集団知で解いてもらうという企画です。

どれだけ早く解かれてしまうか楽しみです。

ルール

  • 相談は自由です。集合知の力を見せてください。
  • その際、このサイトについてつぶやくとき、ハッシュタグ「#だま氏の謎」を必ず入れてください。

問題の発表は、1月1日の午前8時です。

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

半年ぐらい前に考えた問題ですが、やっと解けました。
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は時間がかかりそう。