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

【１】　リーグ戦を考える．すなわち，各チームは他のすべてのチームとそれぞれ$1$回ずつ試合をする．ただし，どのチームも同じ日に$2$回以上試合はしないとする．全試合を最も少ない日数で行えるように対戦スケジュールを組みたい．このとき，以下の問いに答えよ．

問１　参加チームが$\mathrm{a}\text{，}$$\mathrm{b}\text{，}$$\mathrm{c}\text{，}$$\mathrm{d}\text{，}$$\mathrm{e}\text{，}$$\mathrm{f}\text{，}$$\mathrm{g}\text{，}$$\mathrm{h}$の$8$チームのとき，どのように対戦スケジュールを組むとよいかを述べよ．

問２　参加チームが$\mathrm{a}\text{，}$$\mathrm{b}\text{，}$$\mathrm{c}\text{，}$$\mathrm{d}\text{，}$$\mathrm{e}\text{，}$$\mathrm{f}\text{，}$$\mathrm{g}$の$7$チームのとき，どのように対戦スケジュールを組むとよいかを述べよ．

【２】

問１　$m\text{，}$$n$を$m\geqq n$を満たす自然数とする．ケーキを$m$個ずつ詰めた箱を$n$個作ることを考える．以下の$2$つの条件(A)，(B)を満たすには，ケーキの種類は最低いくつ必要か，$m$と$n$を使って表せ．

(A)　どの箱の中にも同じ種類のケーキはない．

(B)　どの$2$つの箱を比較しても，同じ種類のケーキがないか，または，入っていたとしても$1$種類までとする．

【２】

問２　$n$を自然数とする．パンケーキの片面を$2$枚ずつ焼けるフライパンを$1$つ用いて，$n$枚すべてのパンケーキの両面を焼く時間が最短である手法について述べよ．また，その最短時間を$n$を用いて表せ．なお，パンケーキの片面を焼くのにかかる時間は$1$枚でも$2$枚でも$1$分とする．

【２】

問３　ある本には，$1$から始まり順に$1$ずつ増えていくように，すべてのページに算用数字でページ番号が印字されている．この本のページ番号を印字した文字数は$2022$であるという．このとき，この本の総ページ数を求めよ．

【３】　観測点を$5$分間に通過した車の台数を交通量（台$/5$分），観測点付近$1\mathrm{km}$あたりに車が何台あるかを示す量を密度（台$/\mathrm{km}\text{），}$密度の増加とともに交通量が減少する状態を渋滞，および交通量が最大になるときの密度を臨界密度という．右図は，交通量と密度の関係を示した散布図である．このとき，以下の問いに答えよ．

問１　図から読み取った臨界密度を用いて，交通量が最大となるときの車間距離を求めよ．また，車間距離がどのようなときに渋滞が発生しているか述べよ．ただし，車長は$0$とし，車間距離はどの車の間でも同じとする．

問２　車の平均時速を車間距離と交通量を用いて表せ．また，図から読み取った最大交通量を用いて，最大交通量のときの車の平均時速を求めよ．

問３　図から，渋滞していない場合と渋滞している場合のどちらも，密度と交通量の間にはおおまかに$1$次関数で表される関係が読み取れる．これを踏まえ，渋滞していない場合と渋滞している場合のそれぞれについて，平均速度と車間距離の関係を述べよ．

【４】　南北に流れている川がある．狼と羊を連れ，キャベツを持った農夫が東岸にいる．その東岸には$1$$\stackrel{\text{そう}}{\text{艘}}$の小舟がある．以下の$4$つの条件(A)〜(D)を満たしつつ，狼，羊，キャベツのすべてを西岸に渡すことを考える．

(A)　小舟を漕げるのは農夫のみである．

(B)　小舟には，農夫のほかは，狼か羊かキャベツのいずれかのみ乗せることができる． ただし，乗せなくてもよい．

(C)　農夫がいないと狼が羊を食べてしまうため，狼と羊が同じ岸にいて農夫がその岸に いない状態は避ける．

(D)　農夫がいないと羊がキャベツを食べてしまうため，羊とキャベツが同じ岸にいて農 夫がその岸にいない状態は避ける．

ただし，キャベツに対しても「いる」，「いない」と表現することにする．

　東岸の状態を次のような$0$と$1$の並び（ビット列）で表す．農夫，狼，羊，キャベツの各々に対して，東岸にいれば値$1$を，いなければ値$0$を割り当てる．右から$1$桁目をキャベツの値，$2$桁目を羊の値，$3$桁目を狼の値，$4$桁目を農夫の値とした$4$桁の$0$と$1$の並びで状態を表す．例えば，$1010$は東岸に農夫と羊がいて西岸に狼とキャベツがいる状態を表す．また，すべてが東岸にいる状態$1111$を初期状態，すべてが西岸に渡った状態$0000$を終了状態という．このとき，以下の問いに答えよ．

問１　$2$条件(C)，(D)を満たす状態を初期状態と終了状態を含めてすべて求めよ．

問２　$2$条件(C)，(D)を満たす状態のうち，その状態から農夫のみが移動したとき，$2$条件(C)，(D)を満たさなくなるようなものをすべて求めよ．

問３　状態$P\text{，}$$Q$に対して，$1$回の小舟での渡河で状態$P$から状態$Q$に移るとき，$P$から$Q$に状態遷移するという．条件(A)〜(D)を満たしつつ，初期状態から終了状態に至るまでの状態遷移の回数を最も少なくなるようにするにはどうすればよいかを述べよ．