2023　広島市立大学　総合型選抜MathJax

【１】　大小$2$つのサイズの正方形を灰色で塗ることで模様を描くロボットがある．ロボットの形状は一辺の長さが$2\mathrm{cm}$の正方形で，前側が太線，中心が点で表されている（図１）．ロボットは全方位に移動でき，ロボットの中心を通り紙面に垂直な軸周りに回転できる．反時計回りを正の回転，時計回りを負の回転とする．小さい正方形を描く場合は図２(a)のようにロボットの右前側にある一辺の長さが$1\mathrm{cm}$の正方形の部分を塗り，大きい正方形を描く場合は図２(b)のように一辺の長さが$2\mathrm{cm}$の正方形の部分を塗る．

　ロボットが$1\mathrm{cm}$方眼紙の上を移動しながら方眼紙に模様を描くとする．ロボットの中心の位置は図３のように方眼紙の横方向を$x$軸，縦方向を$y$軸とする$2$次元座標系の点$(x,y)$で表される．例えば，図３のロボットの位置は$(3,2)$である．

　ロボットを動かすために表１の$4$つの命令が用意されている．例えば，以下の順序で命令を送ったときは図４(a)〜(f)のように動作する．図４(g)は最終的に描かれた模様である．

$\mathrm{Init}()\to \mathrm{Trans}(3,2)\to \mathrm{Draw}(2)$$\to \mathrm{Rot}(45)\to \mathrm{Trans}(-1,2)\to \mathrm{Draw}(1)\text{(★)}$

　このロボットに関する以下の問いに答えよ．

問１　次の順序で命令を送ったときに描かれる模様を図４(g)にならって図示せよ．

$\mathrm{Init}()\to \mathrm{Trans}(2,2)\to \mathrm{Rot}(45)\to \mathrm{Draw}(2)$$\to \mathrm{Rot}(-45)\to \mathrm{Trans}(1,1)\to \mathrm{Draw}(1)$

問２　図５の模様を描くためには，どのような順序で命令を送ればよいかを，(★)にならって記述せよ．

問３　図６の模様を描く際，以下の条件(1)，(2)をそれぞれ満たすには，どのような順序で命令を送ればよいかを，(★)にならって記述せよ．また，それらが条件を満たしている理由を説明せよ．

(1)　ロボットに送る命令の数が最少

(2)　ロボットの総移動距離が最短

【２】問１　${\left({\displaystyle \frac{1}{3}}\right)}^4$と${\left({\displaystyle \frac{1}{4}}\right)}^3$はどちらが大きいか調べよ．

問２　${\left({\displaystyle \frac{1}{3}}\right)}^{\frac{1}{3}}$と${\left({\displaystyle \frac{1}{4}}\right)}^{\frac{1}{4}}$はどちらが大きいか調べよ．

問３　当たりの確率が${\displaystyle \frac{1}{99}}$のくじ引き$\mathrm{A}$と，当たりの確率が${\displaystyle \frac{1}{100}}$のくじ引き$\mathrm{B}$がある．くじ引き$\mathrm{A}$で$100$回連続して当たりくじを引く確率と，くじ引き$\mathrm{B}$で$99$回連続して当たりくじを引く確率は，どちらが大きいか調べよ．ただし，くじは引くたびに元に戻すものとする．

【３】　$n$を$2$以上の自然数とする．図１のように$n$個すべてのコップが下向きに置いてある状態から，$1$回で$n-1$個のコップを上下反転させる操作を繰り返すことで，最終的に$n$個すべてのコップを上向きにする作業を考える．

　上向きと下向きのコップをそれぞれ$1$と$0$に対応させることで，ある時点での$n$個のコップの状態は$0$または$1$が$n$個並んだ列$\text{（}n$ビット列）で表せる．例えば，図２(a)の$3$つのコップは$000\text{，}$(b)は$011\text{，}$(c)は$110$で表せる．

　$A$をある時点での$n$個のコップの状態を表す$n$ビット列とする．自然数$i$$\text{（}1\leqq i\leqq n\text{）}$に対して，$i$番目以外の$n-1$個のコップを上下反転させる操作を，$A$の$i$番目以外の各位置にある数字が$1$ならば$0$に，$0$ならば$1$に変える操作（ビット反転操作）に対応させる．この操作を$A$に適用して得られる$n$ビット列を$\mathrm{Rev}(A,i)$で表す．例えば，$\mathrm{Rev}(000,1)=011$は，図２(a)の$3$つのコップに対して$1$番目以外の$2$つのコップを上下反転させて図２(b)の状態となることを表す．同様に，$\mathrm{Rev}(011,2)=110$は，図２(b)の$2$番目以外の$2$つのコップを上下反転させると図２(c)の状態となることを表す．また，$\mathrm{Rev}(\mathrm{Rev}(000,1),2)=110$は，$1$番目以外の$2$つのコップを上下反転させた後$2$番目以外の$2$つのコップを上下反転させることで，図２(a)の状態から図２(c)の状態となることを表す．

　冒頭で述べた作業を，$1$つを除いたビット反転操作を繰り返してすべてが$0$の$n$ビット列$00\cdots 0$からすべてが$1$の$n$ビット列$11\cdots 1$を得ることに対応させて考える．このとき，以下の問いに答えよ．

問１　$1$つを除いたビット反転操作を繰り返して$4$ビット列$0000$から$4$ビット列$1111$を得る手順を$\mathrm{Rev}$を用いて表せ．

問２　$1$つを除いたビット反転操作を繰り返してすべてが$0$の$n$ビット列$00\cdots 0$からすべてが$1$の$n$ビット列$11\cdots 1$が得られるとき，$n$が満たすべき条件を述べよ．

問３　$n$を問２の条件を満たす$2$以上の自然数とする．このとき，$1$つを除いたビット反転操作を繰り返すことで，すべてが$0$の$n$ビット列$00\cdots 0$からすべてが$1$の$n$ビット列$11\cdots 1$を得る手法（アルゴリズム）を$\mathrm{Rev}$を用いて述べよ．なお，$1$つを除いたビット反転操作の適用回数を最少にすること．

【４】　アメ$15$個，クッキー$12$個，チョコレート$11$個がテーブルの上に置いてある．$32$人の人に，好きなお菓子を取るように伝えた．その際，$2$種類以上のお菓子を取ってもよいが，同じお菓子を$2$個以上取ってはいけないこととした．その結果，テーブルからはすべてのお菓子が無くなり，アメだけを取った人が$7$人，クッキーだけを取った人が$5$人，チョコレートだけを取った人が$4$人であった．このとき，以下の問いに答えよ．

問１　お菓子を$3$個取った人は最大で何人いるかを調べよ．

問２　取ったお菓子の数が$2$個である人がいるかどうかを調べよ．いる場合，その人が取ったお菓子を答えよ．

問３　なにもお菓子を取らなかった人は最大で何人いるかを調べよ．