計算機概論レポート課題１：数学問題集
作者:
Tobo
最近上传:
6 年前
许可:
LaTeX Project Public License 1.3c
摘要:
高校数学～大学基礎レベルの数学の問題集（解答付き）
Simple math problem set with solution.
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
高校数学～大学基礎レベルの数学の問題集（解答付き）
Simple math problem set with solution.
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
\documentclass[a4paper]{bxjsarticle}
\usepackage{zxjatype}
\usepackage[ipa]{zxjafont}
%% Use packages-----------------
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{url}
\usepackage{here}
\usepackage{hyperref}
\usepackage[margin=5pt]{subcaption}
%%------------------------------
\title{計算機概論レポート課題１：数学問題集}
\author{東方涼介(1w162268-5)}
\date{\today}
\begin{document}
\maketitle
\section{問題}
問題A.\\
(1)正の実数であって,任意の正の実数$y$に対して,
$$y^x \le x^y$$
\qquad となる$x$を求めよ。
\\
(2)正の整数であって,任意の正の整数$m$に対して,
$$m^n \le n^m$$
\qquad となる$n$を求めよ。
\\
\\
\\
\quad 問題B.以下の図1B-1のように5頂点A,B,C,D,Eがある。
\\
$${\centering
\includegraphics[width=3.2cm]{_.png}
}$$
\quad \quad \qquad \qquad \qquad \qquad \qquad \qquad \quad
図1B-1 : 5頂点A,B,C,D,Eの配置
\\
\\
今,動点Pが頂点A上にあり,Pは1秒毎に
\begin{itemize}
\item 今いる頂点に留まる
\item 時計回りに隣接する頂点に移動する
\item 反手計周りに隣接する頂点に移動する
\end{itemize}
\quad のいずれかの動きを等確率で行う。5秒後に点Pが頂点Aにいる確率を求めよ。
\\
\\
\\
\quad 問題C. $<x>$を非負実数$x$の小数部分を表すことにする。以下の広義積分を計算せよ。：\\
\[ \int_0^{100} <\sqrt{x}> dx \]
\\
\\
\\
\quad 問題D. 黒板に1から100までの自然数が一個づつ書かれている。これらの数字を以下の<条件>を満た\\
\quad すようにGroupA,GroupBの二つのグループに分類する方法は何通りあるか。\\ \\
\qquad<条件>:GroupAに属する数字の総積をA,GroupBに属する数字の総積をBとすると$gcd(A,B)=1$\\
\\
\quad ただし、GroupA,GroupBの双方に１つ以上の数字が属さなければならない。
\\
\\
\\
\quad \rm 問題E. \\
$$2_{2015}C_{1007}+_{2016}C_{1007}$$
\qquad \qquad の約数であるような最大の素数を求めよ。
\\
\\
\\
問題F.半径1の単位円周上の2点A,Bをランダムに取り,この2点間の距離|AB|をrとおく。\\
\qquad (1)$r\geq 1$となる確率を求めよ。\\
\qquad (2)rの期待値E(r)を求めよ。\\
\qquad (3)rの中央値をM(r)とおく。M(r)とE(r)の大小関係を求めよ。
\\
\\
\\
\quad 問題G. 以下の各問いに答えよ。\\
\qquad(1)\quad$n$を非負整数とするとき,$3^n$の最高位が9となる確率を求めよ。\\
\qquad \qquad なお,$n$は0以上のすべての整数を等確率でとるものとする。\\
\qquad(2)\quad$n$を2019以下の非負整数とするとき,$3^n$の最高位が9となる$n$は何通りあるか。\\
\qquad \qquad ただし,$3^{2019}$は964桁,$3^{2018}$は963桁である。\\
\\
\\
\\
\\
\relax [以上]
\section{解答}
解答A.\\
(1)$x,y>0$より,$xy \neq 0$であり,両辺を$1/xy$乗しても大小関係は変わらないので, $$ y^x \le x^y \quad \Leftrightarrow \quad y^{1/y} \le x^{1/x} $$
従って,全ての正の実数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$となる。以上から,
\begin{itemize}
\item 0<x<eのとき, $f'(x)=x^{1/x}*\frac{1-log(x)}{x^2}>0$
\item x=eのとき, $f'(x)=0$
\item e<xのとき, $f'(x)<0$
\end{itemize}
といえる。これをもとに $f(x)$ のxに関する増減表を書くと以下のようになる。
\begin{table}[htb]
\centering
\begin{tabular}{|c||c|c|c|c|} \hline
$x$ & 0 & ... & e &... \\ \hline
$f'(x)$ & なし & + & 0 & - \\ \hline
$f(x)$ & なし & $\nearrow$ & $e^{1/e}$ & $\searrow$ \\ \hline
\end{tabular}
\end{table}
以上より, f(x)はx=eにおいて定義域内における最大値をとることが分かる。よって,求める正の実数はeである。
\\
\\
\\
<補足>:
\\なお,$f(x)=x^{1/x}$のグラフは以下の図のようになる。
\\
$$\centering{
\includegraphics[width=10cm]{fx.eps}
}$$
\\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad 図2A-1 : $f(x)=x^{1/x}$のグラフ
\\
\\
(2) (1)の増減表および$1<2<e<3<4$であることより,$n$を正の整数としたときに$f(n)=n^{1/n}$が最大値をとるようなnの候補は$n=2,3$である(このことは以下の表からも明らかである)。\\
\begin{table}[htb]
\centering
\begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline
$x$ & 0 & ...&2&...& e &...&3&... \\ \hline
$f'(x)$ & なし &+&+&+& 0 & -&-&- \\ \hline
$f(x)$ & なし & $\nearrow$& $\nearrow$&$\nearrow$ & $e^{1/e}$ & $\searrow$ & $\searrow$& $\searrow$\\ \hline
\end{tabular}
\end{table}
\\
ここで,自明な不等式$8<9$を考える。この両辺は正より,$\frac{1}{6}$乗しても大小関係は変わらず,その結果$2^{1/2}<3^{1/3}$を得る。従って,求める答えはn=3である。
\\
\\
\\
解答B.\\
各行を今Pがいる頂点(上からA,B,C,D,E),各列を１秒後にPがいる頂点(左からA,B,C,D,E)とした,以下のような5×5の行列Mを考える。
\[
M = \left(
\begin{array}{ccccc}
1 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0\\
0 & 1 & 1 & 1 & 0\\
0 & 0 & 1 & 1 & 1\\
1 & 0 & 0 & 1 & 1
\end{array}
\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$の計算に移ろう。まず$M*M=M^2$を計算すると,
\[
M^2 = \left(
\begin{array}{ccccc}
3 & 2 & 1 & 1 & 2 \\
2 & 3 & 2 & 1 & 1\\
1 & 2 & 3 & 2 & 1\\
1 & 1 & 2 & 3 & 2\\
2 & 1 & 1 & 2 & 3
\end{array}
\right)
\]
を得る。ここで,１行目さえ計算してしまえば,５頂点の位置関係の対称性から2行目以降は1行目の5つの数字の順番を変えただけのものになり容易に求められる。同様に,$M^2*M^2=M^4$を計算すると,
\[
M^4 = \left(
\begin{array}{ccccc}
19 & 17 & 14 & 14 & 17 \\
17 & 19 & 17 & 14 & 14\\
14 & 17 & 19 & 17 & 14 \\
14 & 14 & 17 & 19 & 17\\
17 & 14 & 14 & 17 & 19
\end{array}
\right)
\]
を得る。最後に$M^5=M^4*M$を計算すると,
\[
M^5 = \left(
\begin{array}{ccccc}
53 & 50 & 45 & 45 & 50 \\
50 & 53 & 50 & 45 & 45\\
45 & 50 & 53 & 50 & 45 \\
45 & 45 & 50 & 53 & 50\\
50 & 45 & 45 & 50 & 53
\end{array}
\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}-[\sqrt{x}]$$
が成り立つ。従って,\\
\[ \int_0^{100} <\sqrt{x}> dx = \int_0^{100} \sqrt{x} dx - \int_0^{100} [\sqrt{x}] dx \qquad ...(*) \]
式(*)右辺の計算を行うことで,元の積分値を求める。まず,
\[ \int_0^{100} \sqrt{x} dx = [\quad \frac{2}{3}x^{3/2} \quad ]_0^{100} = \frac{2000}{3} \quad ...(i) \]
また,$g(x)=[\sqrt{x}]$は$\sqrt{x}$の整数部分であるから,以下の図2C-1のように階段状に増加する関数になる。\\
$${\centering
\includegraphics[width=8cm]{gx.eps}
}$$
\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad 図2C-1 :$g(x)=[\sqrt{x}]$ のグラフ
\\
\\
高さ($=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段目を含まない形になる。従って,
\[ \int_0^{100} [\sqrt{x}] dx =
\sum_{0}^{9} (2n^2+n) =\frac{9}{3}*(9+1)*(2*9+1)+\frac{9}{2}*(9+1) = 615 \quad ...(ii)\]
$(i),(ii)$を$(*)$に代入して,以下に示す答えを得る。:
\[ \int_0^{100} <\sqrt{x}> dx = \frac{2000}{3}-615 =\frac{155}{3}\]
\\
<補足>:\\
なお,$<\sqrt{x}>$のグラフは以下の図2C-2のようになる。\\
$${\centering
\includegraphics[width=8cm]{ggx.eps}
}$$
\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad 図2C-2 :$h(x)=<\sqrt{x}>$ のグラフ
\\
\\
一見,のこぎり波のように直角三角形を繰り返しているように見えるので,直接$<\sqrt{x}>$の積分を$100*1/2=50$として計算できそうだが,正しい答え$\frac{155}{3}$とは$\frac{5}{3}$だけ絶対誤差がある。実際は$\sqrt{x}$の小数部分は一次関数のように直線状に増加するわけではなく,非線形な増加の仕方をしているためこの誤差が生じる。
\\
\\
\\
解答D.\\
mの倍数がGroupA,GroupBの両方に含まれると$gcd(A,B)\ge m$故に$gcd(A,B)\neq 1$となるから,全ての自然数mについてmの倍数は全て同一グループに含まれなければならない。このことから,
\begin{itemize}
\item 2の倍数は全て同一のグループに含まれる。
\item 50以下のすべての素数pについて,p,2pは同一のグループに含まれる。
\end{itemize}
の2点が成立し,これらより\bf「ある50以下の素数の倍数である数」\rm は全て同一グループに含まれるといえる。\\
逆に,任意の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$(通り)である。
\\
\\
\\
解答E:\\
以下,$A$が$B$の倍数であることを$B|A$と書くことにする。
$2_{2015}C_{1007}+_{2016}C_{1007}$が1009以上の素数pで割り切れると仮定するとpと1008は互いに素だから,\\
$$p|2_{2015}C_{1007}+_{2016}C_{1007}\Leftrightarrow p|2016_{2015}C_{1007}+1008_{2016}C_{1007} \qquad ...(*)$$
である。ここで,$2016_{2015}C_{1007}=1008_{2016}C_{1008}$であるから,
$$(*)\Leftrightarrow p|1008_{2016}C_{1008}+1008_{2016}C_{1007} \qquad ...(**)$$
更に,コンビネーションの性質:$_mC_r=_{m-1}C_{r}+_{m-1}C_{r-1}$より(この性質はパスカルの三角形を書いてみるとよく理解できる),\quad$1008_{2016}C_{1008}+1008_{2016}C_{1007}=1008_{2017}C_{1008}$であるから,
$$(**)\Leftrightarrow p|1008_{2017}C_{1008} \qquad ...(***)$$
$_{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を考える。\\
$$\centering{
\includegraphics[width=4.5cm]{hex.png}
}$$
\qquad \qquad \qquad \qquad \qquad \qquad \qquad
図2F-1：単位円に内接する正六角形\\
\\
この正六角形は図2F-1に示すように6つの合同な正三角形に分割されることから,一辺の長さが1であると分かる。従って,点Aを頂点Pに一致させたとき,点Bが点Q,Uに一致するまたはそれら以上に点Aから離れていることが|AB|が1以上となる必要十分条件であると分かる。つまり、$\stackrel{\frown}{AB}\geq \pi/3$であればよく,円周全体の長さ$2\pi$のうち$\stackrel{\frown}{UQ}=4\pi/3$の長さの領域に点Bがあれば|AB|が1以上となるので求める確率は, $\frac{4\pi/3}{2\pi}=\frac{2}{3}$である。
\\
\\
(2)\quad(1)と同様,片方の点を固定して考えてもよいので,点Aを固定し,円の中心をOとしてAから反時計回りに見た点Bの回転角を$\theta$,三角形ABOの内角AOBを$\phi$とおく(図2F-2参照)。
$$\centering{
\includegraphics[width=4cm]{TrionCircle.png}
}$$
\qquad \qquad \qquad \qquad \qquad \qquad \quad
図2F-2：3点A,B,Oによる二等辺三角形\\
\\
この図から,
\begin{itemize}
\item $0 \leq \theta \leq \pi$のとき$\phi=\theta$
\item $\pi \leq \theta \leq 2\pi$のとき$\phi=2\pi-\theta$
\end{itemize}
であると分かる。また,三角形ABOに対して余弦定理を適用すると,
$$r^2=2-2cos\phi$$
の関係式が得られ,$r\geq 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倍したものと一致することが分かる。従って,
$$E(r)=\frac{1}{2\pi}*2\sqrt{2}\int_0^{\pi} \sqrt{1-cos\phi} d\phi $$
ここで,半角の定理より,$1-cos\phi=2sin^2\frac{\phi}{2}$であるから,\\
$$\int_0^{\pi} \sqrt{1-cos\phi} d\phi
=\sqrt{2}\int_0^{\pi} sin\frac{\phi}{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に示す。\\
$$\centering{
\includegraphics[width=8.5cm]{pro.png}
}$$
\qquad \qquad \qquad 図2F-3:単位円周上の2点の距離期待値を計算するシミュレーションプログラム
\\
\\
このプログラムにより,1000万回の試行を行い2点間の距離の平均値をExとして算出した。Ex及び$\frac{4}{\pi}$を計算して比較できるよう出力した結果を以下の図2F-4に示す。\\
$$\centering{
\includegraphics[width=5cm]{res.png}
}$$
\qquad \qquad \qquad \quad 図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}$の大小を比較すればよい。
双方の値が正であることを考慮すると,
$$\sqrt{2}>\frac{4}{\pi}\Leftrightarrow \frac{1}{\sqrt{2}}<\frac{\pi}{4} \Leftrightarrow 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)$である。
\\
\\
\\
\\
解答Ｇ:\\
(1)$3^n$がM桁でかつその最高位がkであるとき,
$$k*10^(M-1)\leq 3^n < (k+1)*10^(M-1)$$
の関係式が成り立つ。これらを常用対数にとると,
$$log_{10}k+M-1 \leq nlog_{10}3<log_{10}(k+1)+M-1$$
となる。従って桁数をMに固定したとき,任意のMにおいて,その最高位がkとなるnの範囲は,
$$\frac{log_{10}k}{log_{10}3} \leq n<\frac{log_{10}(k+1)}{log_{10}3} \qquad...(*)$$
となる。
ここで,最高位がkである確率を$P_k$とおくと,$\sum_1^9P_k=1 ...(**)$である。また,$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$である。
\\よって答えは$P_9=log_{10}10-log_{10}9=1-2log_{10}3(\approx 0.0459)$である。
\\
\\
<補足>：
C++言語を用いてプログラムを組み,手元で$3^0$から$3^{10000}$までの最高位として現れる各数1から9の割合p[1]からp[9]を計算した。その結果を以下に示す。\\
---------------------------\\
p[1]=0.30101\\
p[2]=0.17611\\
p[3]=0.12492\\
p[4]=0.09692\\
p[5]=0.07917\\
p[6]=0.06696\\
p[7]=0.05799\\
p[8]=0.05116\\
p[9]=0.04576\\
---------------------------\\
この実行結果から,$n\leq 10000$のときp[9]は確かに理論値約0.0459に近い値を取っていることが分かる。\\
なお,一般にM進表記法で最初の桁がnで始まる(nは2桁以上でもよい)数の出現確率は
$$log_{M}(n+1)-log_{M}(n)$$
となることが示されており,これをベンフォードの法則という。この法則は不正データの検証などに用いられている。
\\
\\
(2)$3^n$と$3^{n+1}$の最高位の数字の関係を考察すると以下の表のような関係が得られる。\\
\begin{table}[htb]
\centering
\begin{tabular}{|l|l|} \hline
$3^{n}$の最高位の数字&$3^{n+1}$の最高位としてありうる数字\\ \hline
1&3,4,5\\
2&6,7,8\\
3&9,1\\
4&1\\
5&1\\
6&1,2\\
7&2\\
8&2\\
9&2\\ \hline
\end{tabular}
\end{table} \\
この表をもとに,最高位が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であることを意味する。
$$\centering{
\includegraphics[width=5cm]{3powGraph.png}
}$$
\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad 図2G-1:$3^{n}$の最高位の状態遷移図\\ \\
この図において1本の有向線分を通過して移動できるノードを隣接ノードという。隣接ノードへの移動は元の数を3倍することを意味する。\\
このグラフにおける,+1の重みのあるエッジを1回通過するまでのありうるノード間の移動パターンを列挙すると以下のようになる。\\
\begin{table}[htb]
\centering
\begin{tabular}{l} \hline
<1>→<4,5>→<1>\\
<1>→<3>→<1> \\
<1>→<3>→<9>→<2>\\
<2>→<7,8>→<2>\\
<2>→<6>→<1> \\ \hline
\end{tabular}
\end{table} \\
問題文から$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通りである。
\\
\\
<補足>：\\
(2)の結果から,nが0以上2019以下の値をランダムにとるときの$3^{n}$の最高位が9となる確率を求めると,$\frac{93}{2019} \approx 0.0461$となり,(1)で求めた$n$が全ての非負整数をランダムに取る場合の理論値とほとんど一致していることが分かる。
\section{参考文献}
[1]LaTexコマンド集(http://www.latex-cmd.com/),2018/05/11閲覧
\\ \relax
\quad[2]受験の月(http://examist.jp/),2018/05/12閲覧
\\ \relax
\quad[3]大滝みや子,岡嶋祐史,平成30年度応用情報技術者合格教本,技術評論社,56-66,2017
\end{document}