問題B.以下の図1B-1のように5頂点A,B,C,D,Eがある。いずれかの動きを等確率で行う。5秒後に点Pが頂点Aにいる確率を求めよ。$<x>$を非負実数$x$の小数部分を表すことにする。以下の広義積分を計算せよ。黒板に1から100までの自然数が一個づつ書かれている。すようにGroupA,GroupBの二つのグループに分類する方法は何通りあるか。GroupA,GroupBの双方に1つ以上の数字が属さなければならない。約数であるような最大の素数を求めよ。\\\\\\問題F.半径1の単位円周上の2点A,Bをランダムに取り,この2点間の距離|AB|をrとおく。1$となる確率を求めよ。(2)rの期待値E(r)を求めよ。(3)rの中央値をM(r)とおく。M(r)とE(r)の大小関係を求めよ。以下の各問いに答えよ。\\\qquad(1)\quad$n$を非負整数とするとき,$3^n$の最高位が9となる確率を求めよ。,$n$は0以上のすべての整数を等確率でとるものとする。\\\qquad(2)\quad$n$を2019以下の非負整数とするとき,$3^n$の最高位が9となる$n$は何通りあるか。,$3^{2019}$は964桁,$3^{2018}$は963桁である。$$従って,全ての正の実数xに関して定義される実関数$f(x)=x^{1/x}$が最大値をとるような実数xを求めればよい$\frac{df}{dx}$を直接求めるのは困難であるので関数$f(x)$の両辺の自然対数をとると,$$log(f(x))=\frac{log(x)}{x}$$この式の両辺をxで微分すると,$$\frac{f'(x)}{f(x)}=\frac{1-log(x)}{x^2}$$従って,$$f'(x)=x^{1/x}*\frac{1-log(x)}{x^2}$$ここで,任意の正の実数xに対して$\frac{x^{1/x}}{x^2}>0$であるから,$f'(x)=0$となるとき,$1-log(x)=0$である。よって,$f'$が0となる唯一の正の実数は$x=e$である。\\また,0<x<eのとき$1>log(x)$,e<xのとき$1<log(x)$であるから,0<x<eのとき,$1-log(x)>0$,e<xのとき$1-log(x)<0$となる。$f'(x)<0$\end{itemize}といえる。xに関する増減表を書くと以下のようになる。f(x)はx=eにおいて定義域内における最大値をとることが分かる。よって,求める正の実数はeである。\\\\\\<補足>:\\なお,$f(x)=x^{1/x}$のグラフは以下の図のようになる。(1)の増減表および$1<2<e<3<4$であることより,$n$を正の整数としたときに$f(n)=n^{1/n}$が最大値をとるようなnの候補は$n=2,3$である(このことは以下の表からも明らかである)。\end{tabular}\end{table}\\ここで,自明な不等式$8<9$を考える。この両辺は正より,$\frac{1}{6}$乗しても大小関係は変わらず,その結果$2^{1/2}<3^{1/3}$を得る。従って,求める答えはn=3である。\\\\\\解答B.\\各行を今Pがいる頂点(上からA,B,C,D,E),各列を1秒後にPがいる頂点(左からA,B,C,D,E)とした,以下のような5×5の行列Mを考える。\right)\]このとき,帰納的に$M^n$はn秒後に点Pがいる頂点の推移を表す(いわゆるマルコフ連鎖である)。ここで,点Pははじめ頂点Aにいることが分かっているので,n秒後に点Pが頂点AにいるPの動き方のパターン総数は,$M^n$の(1,1)成分の値に等しいことが分かる。n秒後の点Pの全ての動き方のパターン総数は$3^n$であり,これらのパターンが全て問う確率で起きるので,求める確率は($M^5$の(1,1)成分)/$3^5$である。\\では,$M^5$の計算に移ろう。\right)\]を得る。ここで,1行目さえ計算してしまえば,5頂点の位置関係の対称性から2行目以降は1行目の5つの数字の順番を変えただけのものになり容易に求められる。\right)\]を得る。\right)\]となるので,答えは,$$\frac{53}{3^5}={\frac{53}{243}}$$である。\\\\<補足>:\\行列のM乗は,C++などのプログラミングで行列の積を定義すれば,理論上$O(log(n))$の計算回数で求めることができる。上記の解答で$M^4=M^2*M^2$と計算したように,nが偶数の時,$M^n=M^{n/2}*M^{n/2}$と計算でき,指数部分を半分に減らせるからである。従って,一般的なPCであれば(1秒間に約$10^8$回の演算ができるので),現実的な時間内で$n=2^{10^8}$秒後といったかなり膨大な数値の場合も計算できる。\\\\\\解答C.\\$[x]$を実数$x$の非負整数$x$の部分とする。\sqrt{x}-[\sqrt{x}]$$が成り立つ。\]式(*)右辺の計算を行うことで,元の積分値を求める。\]また,$g(x)=[\sqrt{x}]$は$\sqrt{x}$の整数部分であるから,以下の図2C-1のように階段状に増加する関数になる。グラフ\\\\高さ($=y$座標)がn(nは非負整数)の階段の横幅($=y$が等しい$x$座標の幅)は,$(n+1)^{2}-n^{2}=2n+1$となるから階段のn段目の面積は,$n*(2n+1)=2n^2+n$である。$x$が[0,100]の値を動くとき,$g(x)$はちょうど階段の0段目から9段目のすべてを含み,10段目を含まない形になる。$(i),(ii)$を$(*)$に代入して,以下に示す答えを得る。=\frac{155}{3}\]\\<補足>:\\なお,$<\sqrt{x}>$のグラフは以下の図2C-2のようになる。グラフ\\\\一見,のこぎり波のように直角三角形を繰り返しているように見えるので,直接$<\sqrt{x}>$の積分を$100*1/2=50$として計算できそうだが,正しい答え$\frac{155}{3}$とは$\frac{5}{3}$だけ絶対誤差がある。実際は$\sqrt{x}$の小数部分は一次関数のように直線状に増加するわけではなく,非線形な増加の仕方をしているためこの誤差が生じる。1$となるから,全ての自然数mについてmの倍数は全て同一グループに含まれなければならない。2の倍数は全て同一のグループに含まれる。50以下のすべての素数pについて,p,2pは同一のグループに含まれる。全て同一グループに含まれるといえる。\\逆に,任意の50より大きい素数(53,59,61,67,71,73,79,83,89,97)の倍数は1以上100以下の自然数の中にその数自身の一つしか存在しないため,これらの数字はGroupA,GroupBのいずれに属してもgcd(A,B)の値に影響しない。1はGroupA,GroupBのいずれに属してもgcd(A,B)の値に影響しない。\\結局,「1,53,59,61,67,71,73,79,83,89,97」の11個の数字(これらの数字の集合をSとする)はGroupA,GroupBのいずれに属してもよく,それ以外の89個の数字は全てA,Bのいずれか一方に含まれなけらばならない。\\Sに含まれない89個の数字がGroupA,GroupBのどちらに属するかで2通りあり,どちらの場合もSに含まれる11個の数字の割り振り方は$2^{11}-1$通りある(100個すべての数字が同一のグループに属してはならないことに注意する)ので,求めるパターン数は,$2*(2^{11}-1)=4094$(通り)である。以下,$A$が$B$の倍数であることを$B|A$と書くことにする。...(*)$$である。...(***)$$$_{2017}C_{1008}=\frac{2017!}{(1008!)*(1009!)}$は整数であるが,この分母は素因数2017を含まず,かつ分子に素因数2017が含まれるので,これは2017の倍数である。従って,$2017|1008_{2017}C_{1008}$である。\\2017は確かに1009以上の素数であるので,(*).(**),(***)の同値関係は成立し,$$2017|2_{2015}C_{1007}+_{2016}C_{1007}$$となる。,$2016_{2015}C_{1007}+1008_{2016}C_{1007}=1008_{2017}C_{1008}$故,$2_{2015}C_{1007}+_{2016}C_{1007}=_{2017}C_{1008}$であり,$_{2017}C_{1008}$は2017より大きい素因数を明らかに持たないので,求める最大の素数は2017である。\\\\<補足>:\\昨年は西暦2017年,平成29年であり,西暦年と平成年が共にピタゴラス素数の年ということで話題になった。ピタゴラス素数とは2つの平方数の和で表せる素数のことであり,例実際,$29=2^2+5^2$,$2017=9^2+44^2$と表せる。次に西暦年が素数となるのは2027年である。\\\\\\解答F:\\(1)2点の距離は一方の点に対するもう一方の位置に依存するので,片方の点Aの位置は以下の図2F-1に示すように固定してよい。従って,|AB|が1以上となるような他方の点Bの位置をのみ考える。ここで,図2F-1に示すような半径1の円に内接する正六角形PQRSTUを考える。図2F-1:単位円に内接する正六角形\\\\この正六角形は図2F-1に示すように6つの合同な正三角形に分割されることから,一辺の長さが1であると分かる。従って,点Aを頂点Pに一致させたとき,点Bが点Q,Uに一致するまたはそれら以上に点Aから離れていることが|AB|が1以上となる必要十分条件であると分かる。$\frac{4\pi/3}{2\pi}=\frac{2}{3}$である。\\\\(2)\quad(1)と同様,片方の点を固定して考えてもよいので,点Aを固定し,円の中心をOとしてAから反時計回りに見た点Bの回転角を$\theta$,三角形ABOの内角AOBを$\phi$とおく(図2F-2参照)。2\pi$のとき$\phi=2\pi-\theta$\end{itemize}であると分かる。0$故,$$r=\sqrt{2}\sqrt{1-cos\phi}$$となる。rの期待値E(r)は$\theta$を0から$2\pi$まで変化させたときのrの$\theta$による積分値を変域幅$2\pi$で割ったものである。,$\theta$を0から$2\pi$まで変化させたときのrの積分値は,先に示した$\theta$と$\phi$の関係式から,$\phi$を0から$\pi$まで変化させたときの$\phi$によるrの積分値を(0から$\pi$までと$\pi$から$2\pi$までの範囲での各積分値は等しいので)2倍したものと一致することが分かる。d\phi=\sqrt{2}[-2cos\frac{\phi}{2}]_0^{\pi}=\sqrt{2}*(0-(-2))=2\sqrt{2}$$以上より,$$E(r)=\frac{1}{2\pi}*2\sqrt{2}*2\sqrt{2}=\frac{8}{2\pi}=\frac{4}{\pi}$$\\\\<補足>:\\C++言語でランダムに単位上の2点を選択しその距離を求めるシミュレーションを行うプログラムを実装した。これを以下の図2F-3に示す。図2F-3:単位円周上の2点の距離期待値を計算するシミュレーションプログラム\\\\このプログラムにより,1000万回の試行を行い2点間の距離の平均値をExとして算出した。Ex及び$\frac{4}{\pi}$を計算して比較できるよう出力した結果を以下の図2F-4に示す。図2F-4:単位円周上の2点の距離期待値を計算するシミュレーション結果\\\\この結果より,確かに$E(r)$は$\frac{4}{\pi}$に近い値をとっていることが分かる。\\\\(3)単位円に内接する正方形を考えると,(1)と同様の方法で点Aを固定したとき$\frac{1}{2}$の確率で$r>$(内接する正方形の一辺の長さ)$=\sqrt{2}$となることが分かる。従って,$M(r)=\frac{1}{2}$である。(2)から$E(r)=\frac{4}{\pi}$であるので,$\sqrt{2}$と$\frac{4}{\pi}$の大小を比較すればよい。2\sqrt{2}<\pi$$の同値関係が成り立つが,実際,$2\sqrt{2}<\sqrt{9}=3<\pi$である(3<$\pi$であることは有名だが,(1)の図2F-1における円周の長さが正六角形の周の長さより長いことから示される)ので$\sqrt{2}>\frac{4}{\pi}$であるといえる。,$M(r)>E(r)$である。(k+1)*10^(M-1)$$の関係式が成り立つ。nlog_{10}3<log_{10}(k+1)+M-1$$となる。\qquad...(*)$$となる。...(**)$である。,$P_k$の値の比は(*)に表される不等式の範囲の比と一致する(∵任意のMに対して$3^n$の最高位がkである範囲は(*)の不等式で表される)ので定数aを用いて,$$P_k=\frac{a}{log_{10}3}(log_{10}(k+1)-log_{10}k)$$と表される。$$\sum_1^9P_k=\frac{a}{log_{10}3}((log_{10}(2)-log_{10}(1))+(log_{10}(3)-log_{10}(2))+...+(log_{10}(10)-log_{10}(9)))=\frac{a}{log_{10}3}$$であるので,(**)より$a=log_{10}3$である。0.0459)$である。\\\\<補足>:C++言語を用いてプログラムを組み,手元で$3^0$から$3^{10000}$までの最高位として現れる各数1から9の割合p[1]からp[9]を計算した。その結果を以下に示す。10000$のときp[9]は確かに理論値約0.0459に近い値を取っていることが分かる。\\なお,一般にM進表記法で最初の桁がnで始まる(nは2桁以上でもよい)数の出現確率は$$log_{M}(n+1)-log_{M}(n)$$となることが示されており,これをベンフォードの法則という。この法則は不正データの検証などに用いられている。\\\\(2)$3^n$と$3^{n+1}$の最高位の数字の関係を考察すると以下の表のような関係が得られる。この表をもとに,最高位がkである状態をノード<k>とし,各ノード<k>から最高位がkである数を3倍したときに取りうる値の割り振られたられたノードへの有向線分(エッジ)を引き,3倍したときに繰り上がりが生じる場合はエッジに+1の重みをつけた状態遷移図を書くと以下の図2G-1のようになる。図中の太い矢印は状態遷移図の開始点を指す($3^0=1$であるので,開始点は1としている)。,(<4>,<5>)と(<7>,<8>)はそれらが含まれる全ての有向線分の始点と終点が同じであるのでグラフにおいて等価なノードとみなし統合している。<4,5>ノードは最高位が4または5であることを意味し,<7,8>ノードは最高位が7または8であることを意味する。\\この図において1本の有向線分を通過して移動できるノードを隣接ノードという。隣接ノードへの移動は元の数を3倍することを意味する。\\このグラフにおける,+1の重みのあるエッジを1回通過するまでのありうるノード間の移動パターンを列挙すると以下のようになる。問題文から$3^{2018}$から$3^{2019}$にかけて繰り上がりが生じていることがわかっているので,$3^0$に2019回3を掛けたとき(=有向線分を通過して2019回ノード間を移動したとき)に最終的に到達するノードは<1>,<2>のいずれかである。,$3^{0}=1$であり,かつ$3^{2019}$は964桁なので,ノード<1>を開始点として+1の重みのあるエッジをちょうど963回通過して<2>ノードに到達するように隣接ノードへの移動を2019回繰り返さなくてはならない。\\ここで,ノード間の移動<1>→<3>→<9>→<2>は3回の移動のうち1回で+1の重みのあるエッジを通過し,それ以外のすべての移動パターン(<1>→<4,5>→<1>,<1>→<3>→<1>,<2>→<7,8>,<2>→<6>→<1>)は2回の移動のうち1回で+1の重みのあるエッジを通過していることが分かる。すべての移動パターンにおいて最後に移動するエッジが+1の重みを有していることから,$3^{2019}$は$3^{2018}$から繰り上がりのあったので,2019回の移動を終えた瞬間にいずれかの移動パターンをちょうど終えていることが分かる(移動パターンの途中で終了していない)。\\よって,<1>→<3>→<9>→<2>の移動パターンが行われた回数をxとおくと,ノード間の移動回数に関する一次方程式$$2(963-x)+3x=2019$$を得る。これを解くと,$x=93$となる。1回の<1>→<3>→<9>→<2>の移動パターンでは必ず1回ノード<9>を通過し,それ以外の移動パターンでは<9>は一度も通過しないので,xの値は$n=0,1,2,...,2019$における$3^{n}$の最高位が9であるものの個数に等しいといえて,求める答えは93通りである。0.0461$となり,(1)で求めた$n$が全ての非負整数をランダムに取る場合の理論値とほとんど一致していることが分かる。