2023　群馬大学　後期情報学部小論文MathJax

【１】　次の文章を読んで，問１-１，１-２に答えよ．

　プログラミングを勉強している$\mathrm{G}$と$\mathrm{U}$は，プログラミングの実践練習も兼ねてすごろくに類似した一人用のゲームを作成することとした．このゲームでは，プレイヤーがボタンを押す度に，プレイヤーの駒が規則に従ってマス目を移動する．

問１-１　以下の説明を読んで，(1)から(4)に答えよ．なお，解答には根拠も記述すること．

　図１に示すマス目を利用し，プレイヤーの駒は次の規則に沿って動かすこととした．

規則１.　最初，プレイヤーの駒は一番左$\text{（}\mathrm{A}\text{）}$のマスに置かれる．

規則２.　プレイヤーがボタンを押すと，駒は右隣のマスに移動するか，もしくは同じマスにとどまり動かない．どちらが適用されるかはそれぞれ等確率${\displaystyle \frac{1}{2}}$で選ばれる．

規則３.　駒が一番右$\text{（}\mathrm{C}\text{）}$のマスにたどり着いたら目標達成となり，そこでゲームは終了する．

　ボタンを$n$回押した後に，駒が$\mathrm{A}\text{，}$$\mathrm{B}$にある確率をそれぞれ$a_n\text{，}$$b_n$とする．ここで$n$は$0$以上の整数とする．

(1)　プレイヤーが$2$回ボタンを押した後に，駒が$\mathrm{A}$にある確率$a_2$と$\mathrm{B}$にいる確率$b_2$をそれぞれ求めよ．

(2)　$a_n$を求めよ．

(3)　$b_n$を求めよ．

(4)　ゲームを開始してからゲームが終了するまでにボタンを押した回数が$n$回以下である確率$p_n$を求めよ．

問１-２　以下の説明を読んで，(1)から(3)に答えよ．なお，解答には根拠も記述すること．

　問１-１で作成したゲームをテストしながら$\mathrm{G}$と$\mathrm{U}$は以下のように話している．

そして次の規則と図２に示すマス目を作成した．

規則１.　最初，プレイヤーの駒は左上$\text{（}\mathrm{X}\text{）}$のマスに置かれる．

規則２.　プレイヤーがボタンを押すと，駒は現在あるマスに隣接するいずれかのマスに必ず移動する．ここで，隣接するとは，辺を共有することを指す．

規則３.　どのマスに移動するのかは等確率で選ばれる．つまり，隣接するマスが$m$個ある場合，どのマスも移動先になる確率は${\displaystyle \frac{1}{m}}$である．

規則４.　駒が右下$\text{（}\mathrm{W}\text{）}$のマスにたどり着いたら目標達成となり，そこでゲームは終了する．

　例えば，左上$\text{（}\mathrm{X}\text{）}$のマスに隣接しているのは右上$\text{（}\mathrm{Y}\text{）}$と左下$\text{（}\mathrm{Z}\text{）}$のマスであり，右下$\text{（}\mathrm{W}\text{）}$のマスは隣接していない．左上$\text{（}\mathrm{X}\text{）}$のマスに駒がある状態でプレイヤーがボタンを押すと，移動先の候補となるマスは右上$\text{（}\mathrm{Y}\text{）}$と左下$\text{（}\mathrm{Z}\text{）}$の$2$つであり，どちらかに駒が移動する．この場合$m=2$であり，どちらのマスも移動先となる確率は${\displaystyle \frac{1}{2}}$ずつである．

　ボタンを$n$回押した後に，駒が$\mathrm{X}\text{，}$$\mathrm{Y}\text{，}$$\mathrm{Z}$にある確率をそれぞれ$x_n\text{，}$$y_n\text{，}$$z_n$とする．ここで$n$は$0$以上の整数とする．

(1)　$x_0\text{，}$$x_1\text{，}$$x_2\text{，}$$x_3$を求めよ．

(2)　新しく作ったゲームをテストをしながら$\mathrm{G}$と$\mathrm{U}$が以下のように話している．

　この$\mathrm{U}$の発言には正当な根拠がある．この根拠を記述せよ．

(3)　$x_n\text{，}$$y_n+z_n$を求めよ．

【２】　次の問２-１，２-２，２-３，２-４に答えよ．

問２-１　$a$を整数，$m$を正の整数とするとき，

$a=qm+r\text{，}$$0\leqq r<m$

となる整数$q$と$r$を，それぞれ$a$を$m$で割ったときの商と余りという．このような$q$と$r$の組は存在し，一通りに定まることを証明せよ．

問２-２　$a$と$b$を整数，$m$を正の整数とする．$a$を$m$で割ったときの余りと，$b$を$m$で割ったときの余りが等しいとき，

$a\equiv b(\mathrm{mod}m)$

と表し，$a$と$b$は$m$を法として合同であるという．$a$を$m$で割ったときの商を$q$とし，余りを$r$とすると，$a=qm+r$であるから，$a\equiv r(\mathrm{mod}m)$が成立する．

　$a\text{，}$$b\text{，}$$c\text{，}$$d$を整数，$m$を正の整数とするとき，$a\equiv b(\mathrm{mod}m)\text{，}$$c\equiv d(\mathrm{mod}m)$ならば，

$ac\equiv bd(\mathrm{mod}m)$

であることを示せ．

問２-３　$3^5=3\times 3\times 3\times 3\times 3=243=18\times 13+9$より，$3^5$を$13$で割ったときの余りは$9$である．ゆえに，$3^5\equiv 9(\mathrm{mod}13)$である．一方で，位取りの基礎を$2$として$5$を表すと，$5=2^2+2^0=4+1$である．ゆえに，$3^5=3^4\times 3^1$であり，

$3^2\equiv 3\times 3\equiv 9(\mathrm{mod}13)\text{，}$$3^4\equiv 3^2\times 3^2\equiv 9\times 9\equiv 81\equiv 3(\mathrm{mod}13)$

であることから，次を得る．

$3^5\equiv 3^4\times 3^1\equiv 3\times 3\equiv 9(\mathrm{mod}13)$

つまり，$3^5$を$13$で割ったときの余りは$9$である．

　位取りの基礎を$2$として$100$を表し，$3^{100}$を$13$で割ったときの余りを求めよ．

問２-４　電卓やコンピュータなどを使わず，手計算で$3^{100}$を$13$で割ったときの余りを求めることを考える．このとき，$3^{100}$を$3^{100}=3\times 3\times \cdots \times 3$として計算してから$13$で割ったときの余りを求める方法と比較して，問２-３のように位取りの基礎を$2$として$100$を表してから$3^{100}$を$13$で割ったときの余りを求める方法がもつ利点を説明せよ．