京都大学 理学部特色入試 2024年度 第4問 解説
（2023年11月に行われた特色入試の問題です。）
問題編
問題
$t$ を実数とする。投げたとき表と裏の出る確率がそれぞれ $\dfrac{1}{2}$ であるコインを $10$ 回投げて、座標空間の点 $\mathrm{P_0}$, $\mathrm{P_1}$, $\mathrm{P_2}$, $\cdots$, $\mathrm{P_{10}}$ を以下で定める。
- $\mathrm{P_0}$ の座標は $(1,2,3)$ とする。
- $n$ を $1\leqq n\leqq 10$ を満たす任意の自然数とする。 $\mathrm{P}_{n-1}$ の座標が $(x,y,z)$ であるとき、もし $n$ 回目のコイン投げで表が出たなら $\mathrm{P}_n$ の座標は $((1-t)x+ty,x,z)$ とし、裏が出たなら $\mathrm{P}_n$ の座標は $(x,(1-t)y+tz,y)$ とする。
例えば $t=-1$ のとき、1回目のコイン投げで表、2回目のコイン投げで裏が出たなら、 $\mathrm{P_0},\mathrm{P_1},\mathrm{P_2}$ の座標はそれぞれ $(1,2,3)$, $(0,1,3)$, $(0,-1,1)$ となる。また $t=-1$ のとき、 $\mathrm{P_1}$ が取り得る座標空間の点は $(0,1,3)$ と $(1,1,2)$ の2個である。以下の設問に答えよ。
(1) $t=-1$ のとき、 $\mathrm{P_3}$ の座標が $(1,0,1)$ となる確率を求めよ。
(2) $\mathrm{P_{10}}$ が取り得る座標空間の点の個数を $N(t)$ とする。 $N(t)\geqq 250$ となる実数 $t$ が存在するかどうかを判定せよ。
考え方
(1)はやるだけですが、これを(2)のヒントだと思うのはなかなか難しいです。
(1)を利用したとしても、(2)ですぐに結論が出せるわけではなく、地道に計算していくしかなさそうです。重複に気を付けて計算していきましょう。
解答編
問題
$t$ を実数とする。投げたとき表と裏の出る確率がそれぞれ $\dfrac{1}{2}$ であるコインを $10$ 回投げて、座標空間の点 $\mathrm{P_0}$, $\mathrm{P_1}$, $\mathrm{P_2}$, $\cdots$, $\mathrm{P_{10}}$ を以下で定める。
- $\mathrm{P_0}$ の座標は $(1,2,3)$ とする。
- $n$ を $1\leqq n\leqq 10$ を満たす任意の自然数とする。 $\mathrm{P}_{n-1}$ の座標が $(x,y,z)$ であるとき、もし $n$ 回目のコイン投げで表が出たなら $\mathrm{P}_n$ の座標は $((1-t)x+ty,x,z)$ とし、裏が出たなら $\mathrm{P}_n$ の座標は $(x,(1-t)y+tz,y)$ とする。
例えば $t=-1$ のとき、1回目のコイン投げで表、2回目のコイン投げで裏が出たなら、 $\mathrm{P_0},\mathrm{P_1},\mathrm{P_2}$ の座標はそれぞれ $(1,2,3)$, $(0,1,3)$, $(0,-1,1)$ となる。また $t=-1$ のとき、 $\mathrm{P_1}$ が取り得る座標空間の点は $(0,1,3)$ と $(1,1,2)$ の2個である。以下の設問に答えよ。
(1) $t=-1$ のとき、 $\mathrm{P_3}$ の座標が $(1,0,1)$ となる確率を求めよ。
(2) $\mathrm{P_{10}}$ が取り得る座標空間の点の個数を $N(t)$ とする。 $N(t)\geqq 250$ となる実数 $t$ が存在するかどうかを判定せよ。
解答
(1)
コインを投げた結果が表の場合を〇で表し、裏の場合を×で表す。
$t=-1$ なので、 $(x,y,z)$ にいるとき、次が〇なら $(2x-y,x,z)$ に移動し、×なら $(x,2y-z,y)$ に移動する。
$\mathrm{P}_0$ の座標は $(1,2,3)$ なので、 $\mathrm{P_1}$ の取り得る座標は $(0,1,3)$ と $(1,1,2)$ である。
それぞれに対し、〇・×の場合を考えると、 $\mathrm{P_2}$ の取り得る座標は $(-1,0,3)$, $(0,-1,1)$, $(1,1,2)$, $(1,0,1)$ である。
また、それぞれに対し、〇・×の場合を考えると、 $\mathrm{P_3}$ の取り得る座標は次のようになる。1行目は〇、2行目は×の場合である。
| $\mathrm{P_2}$ の座標 | $\mathrm{P_3}$ の座標 |
|---|---|
| $(-1,0,3)$ | $(-2,-1,3)$ $(-1,-3,0)$ |
| $(0,-1,1)$ | $(1,0,1)$ $(0,-3,-1)$ |
| $(1,1,2)$ | $(1,1,2)$ $(1,0,1)$ |
| $(1,0,1)$ | $(2,1,1)$ $(1,-1,0)$ |
これより、 $(1,0,1)$ は2通りあることがわかるので、求める確率は $\dfrac{2}{2^3} =\dfrac{1}{4}$ …（答）
(2)
$(x,y,z)$ にいるとき、次が〇なら\[ ((1-t)x+ty,x,z) \] に移動し、×なら\[ (x,(1-t)y+tz,y) \]に移動する。
そのため、 $(a,b,c)$ にいるとき、次が〇なら\[ ((1-t)a+tb,a,c) \]に移動し、さらにその次が×なら
\begin{eqnarray}
& & ((1-t)a+tb,(1-t)a+tc,a)
\end{eqnarray}に移動し、さらにその次が〇なら $x$ 座標は
\begin{eqnarray}
& & (1-t)\{(1-t)a+tb\}+t\{(1-t)a+tc\} \\[5pt]
&=& \{(1-t)^2+t(1-t)\}a +t(1-t)b+t^2c \\[5pt]
&=& (1-t)a +t(1-t)b+t^2c \\[5pt]
\end{eqnarray}なので、\[ ((1-t)a +t(1-t)b+t^2c, (1-t)a+tb, a) \]に移動する。
一方、 $(a,b,c)$ にいるとき、次が×なら\[ (a,(1-t)b+tc,b) \]に移動し、さらにその次が〇なら
\begin{eqnarray}
& & ((1-t)a+t\{(1-t)b+tc\},a,b) \\[5pt]
&=& ((1-t)a+t(1-t)b+t^2c,a,b) \\[5pt]
\end{eqnarray}に移動し、さらにその次が×なら\[ ((1-t)a +t(1-t)b+t^2c, (1-t)a+tb, a) \]に移動する。
よって、 $(a,b,c)$ にいるとき、次以降が「〇×〇」となる場合と、「×〇×」となる場合では、移動先が一致することがわかる。
$n$ 回目のコイン投げの結果が表だったら $2^{10-n}$ の位を $0$、裏だったら $1$ として、10回のコイン投げの結果と $0$ から $1023$ までを2進数表記したものを対応させる。例えば、〇〇〇〇××××〇〇は、 $0000111100_{(2)}$ と対応させる（ここでは、頭に $0$ を追加して、必ず10桁になるようにする）。10回のコイン投げの結果をシナリオと呼び、シナリオに対応したこの数をシナリオ番号と呼ぶことにする。
以下では、それぞれのシナリオに対し、より小さなシナリオ番号で同じ最終地点に到達するものがあるか、考えていく。
まず、先ほど見たように、「×〇×」は「〇×〇」と移動先が同じである。よって、シナリオに「×〇×」が含まれている場合、その部分を「〇×〇」に置き換えたものを考えることで、より小さなシナリオ番号で同じ最終地点に到達するものが存在することがわかる。
これを踏まえ、全シナリオの中で、「×〇×」を含まないものを数える。
$n$回コインを投げたとき、 $n-1$回目、$n$回目の結果が「〇〇」となるシナリオで、途中に「×〇×」を含まないものの個数を $a_n$ とし、
「〇×」を $b_n$ 、
「×〇」を $c_n$ 、
「××」を $d_n$ 、
とする。
$n$ 回目が〇で $n+1$ 回目が〇のものを考えると、 $a_{n+1}=a_n+c_n$ が成り立つ。また、$n$ 回目が×のものを考えると、 $c_{n+1}=b_n+d_n$, $d_{n+1}=b_n+d_n$ が成り立つ。
$n$ 回目が〇で $n+1$ 回目が×のものを考えると、今は「×〇×」を含まないものを数えているので、 $b_{n+1}=a_n$ となる。
以上から、次の式が成り立つ。
\begin{eqnarray}
a_{n+1} &=& a_n+c_n \\[5pt]
b_{n+1} &=& a_n \\[5pt]
c_{n+1} &=& b_n+d_n \\[5pt]
d_{n+1} &=& b_n+d_n \\[5pt]
\end{eqnarray}これらの値は、順番に計算して次のようになる。
| $n$ | $a_n$ | $b_n$ | $c_n$ | $d_n$ |
|---|---|---|---|---|
| $2$ | $1$ | $1$ | $1$ | $1$ |
| $3$ | $2$ | $1$ | $2$ | $2$ |
| $4$ | $4$ | $2$ | $3$ | $3$ |
| $5$ | $7$ | $4$ | $5$ | $5$ |
| $6$ | $12$ | $7$ | $9$ | $9$ |
| $7$ | $21$ | $12$ | $16$ | $16$ |
| $8$ | $37$ | $21$ | $28$ | $28$ |
| $9$ | $65$ | $37$ | $49$ | $49$ |
| $10$ | $114$ | $65$ | $86$ | $86$ |
こうして、「×〇×」を含まないものは $114+65+86+86=351$ と求められる。これより、「×〇×」を含む $1024-351=673$ のシナリオに対しては、より小さなシナリオ番号で同じ最終地点に到達するものが存在するため、 $N(t)$ は $351$ 以下であることがわかる。
ここからは、「×〇×」を含まない $351$ 個のシナリオに対して、より小さいシナリオ番号で同じ最終地点に到達するものが存在するか考える。
「×〇〇〇×〇」
について考える。最後の3つの「〇×〇」は「×〇×」と同じ行き先になるので、これは
「×〇〇×〇×」
と同じ行き先になる。次に、3番目から5番目にある「〇×〇」に対して同じ変換をすると
「×〇×〇××」
と同じ行き先になることがわかる。さらに、最初の3つの「×〇×」を「〇×〇」に入れ替えて
「〇×〇〇××」
と同じ行き先になることがわかる。これに対応するシナリオ番号は、もとのシナリオ番号より小さくなる。つまり、「×〇〇〇×〇」を含むシナリオに対して、より小さいシナリオ番号で同じ最終地点に到達するものが存在する。
上で見た内容から
「×」
「2つ以上の〇」
「×」
「〇」
が連続して並んでいる場合、後ろから繰り返し「〇×〇」を「×〇×」に変換し、最初の3つが「×〇×」になるようにしてからさらに「〇×〇」と変換したものを考えると、より小さいシナリオ番号で同じ最終地点に到達するものが存在することがわかる。
ここからは、次の2つを同時に満たすシナリオを数える。
- 「×、2つ以上の〇、×、〇」が連続して並んでいる
- 「×〇×」を含まない
(i) ×が2つの場合
「|×〇〇|×〇|」で、3箇所の「|」に $0$ 個以上の〇を合計 $5$ 個入れる場合を考えればよい。
重複組合せの考え方から ${}_7\mathrm{C}_5=21$ 個と求められる。
(ii) ×が3つの場合
まず、×がすべて離れている場合を考える。「×〇×」が含まれないように、×同士の間には2つ以上の〇が必要である。
よって、「|×〇〇|×〇〇|×|」で、4箇所の「|」に $0$ 個以上の〇を合計 $3$ 個入れる場合を考えればよい（左から1番目・2番目の×の部分で1つ目の条件を満たしている）。
重複組合せの考え方から ${}_6\mathrm{C}_3=20$ 通りである。
次に、×が離れいていない場合を考える。1つ目の条件を満たすには、××と×に分かれなければいけない。
これは、「|××〇〇|×〇|」で、3箇所の「|」に $0$ 個以上の〇を合計 $4$ 個入れる場合を考えればよい（左から2番目・3番目の×の部分で1つ目の条件を満たしている）。
重複組合せの考え方から ${}_6\mathrm{C}_4=15$ 通りである。
よって、この場合は、 $20+15=35$ 個と求められる。
(iii) ×が4つの場合
×が「1個・1個・2個」と分かれている場合を考える。
「|×〇〇|×〇〇|××|」で、4箇所の「|」に $0$ 個以上の〇を合計 $2$ 個入れる場合を考えればよい（左から1番目・2番目の×の部分で1つ目の条件を満たしている）。${}_5\mathrm{C}_2=10$ 個ある。
×が「2個・1個・1個」と分かれている場合を考える。
「|××〇〇|×〇〇|×|」で、4箇所の「|」に $0$ 個以上の〇を合計 $2$ 個入れる場合を考えればよい（左から2番目・3番目の×の部分で1つ目の条件を満たしている）。${}_5\mathrm{C}_2=10$ 個ある。
×が「3個・1個」と分かれている場合を考える。
「|×××〇〇|×〇|」で、3箇所の「|」に $0$ 個以上の〇を合計 $3$ 個入れる場合を考えればよい（左から3番目・4番目の×の部分で1つ目の条件を満たしている）。${}_5\mathrm{C}_3=10$ 個ある。
これらには重複はないので、少なくとも $10+10+10=30$ 個あることがわかる。
(iv) ×が5つの場合
×が「1個・1個・3個」と分かれている場合を考える。
「|×〇〇|×〇〇|×××|」で、4箇所の「|」に $0$ 個以上の〇を合計 $1$ 個入れる場合を考えればよい（左から1番目・2番目の×の部分で1つ目の条件を満たしている）。$4$ 個ある。
×が「2個・1個・2個」と分かれている場合を考える。
「|××〇〇|×〇〇|××|」で、4箇所の「|」に $0$ 個以上の〇を合計 $1$ 個入れる場合を考えればよい（左から2番目・3番目の×の部分で1つ目の条件を満たしている）。$4$ 個ある。
×が「3個・1個・1個」と分かれている場合を考える。
「|×××〇〇|×〇〇|×|」で、3箇所の「|」に $0$ 個以上の〇を合計 $1$ 個入れる場合を考えればよい（左から3番目・4番目の×の部分で1つ目の条件を満たしている）。$4$ 個ある。
×が「4個・1個」と分かれている場合を考える。
「|××××〇〇|×〇|」で、3箇所の「|」に $0$ 個以上の〇を合計 $2$ 個入れる場合を考えればよい（左から4番目・5番目の×の部分で1つ目の条件を満たしている）。${}_4\mathrm{C}_2=6$ 個ある。
これらには重複はないので、少なくとも $4+4+4+6=18$ 個あることがわかる。
(i)～(iv)より、「×〇×」を含まない $351$ 個のシナリオのうち、より小さいシナリオ番号で同じ最終地点に到達するものが存在するのは、\[ 21+35+30+18=104 \]個以上あることがわかる。よって、 $N(t)$ は最大でも $351-104=247$ なので、 $N(t)\geqq 250$ となる実数 $t$ は存在しない。（答）
解説
難しく書いていますが、結局やっていることは、最終地点が一緒のものをはじいていってるだけです。はじきやすいように、コイン投げの結果に番号をふって、すでに出てきた結果になるものを除外していく、という方針をとっています。
問題文を読んでもぱっと答えは予想できません。ただ、もし $N(t)\geqq 250$ となる $t$ が存在するなら、そのような $t$ を具体的に選んで計算して、「たしかに、$250$以上になります」と示すことになりそうです。が、これは大変そう。
一方、 $t$ が存在しないと予想すると、ほとんどが同じ最終地点になる、ということです。(1)を見れば、表裏表と裏表裏が同じ結果になり、このケースでは、その後はどんな結果でも最終地点は重複します。こういう性質を利用すれば、たしかに重複するものを除外できそうです。
ということで、(1)がヒントだとしたら、たくさん除外していく方針をとることになるでしょう。はじめはこの方針で考えていきます。
その前に、(1)で見た「表裏表と裏表裏が同じ結果」がたまたまなのか、どんな $t$ でも成り立つのかを考えておきます。この計算も大変で、行列が使えればもう少し楽になるかもしれませんが、これはがんばって示すしかありません。
次に、「表裏表と裏表裏が同じ結果」を使ってすぐに除外できるものを消していきます。 $n=10$ なので、ある程度ちからわざで求めることもできます。重複に気をつけて数えなくてはいけません。
ここまでしても、まだ $250$ とは乖離があります。さらに除外できるものを探さないといけなくて、かなり大変です。
上の解答では、 $250$ 未満になるように、一部だけを除外しています。すべて除外するのは大変なのでやっていませんが、すべてを除外すると、 $232$ となります。実際、 $t=2$ とすると $N(t)=232$ となるので、これが最大値となります。 $249-232=17$ 個しかバッファがないので、かなりがんばって除外しないといけません。
追記
上の解答はかなり力づくでやっている感じですが、ネット上で他の解答・解説を見ると、もっとスッキリ解いています。その手法について説明していきます。
別解1
1つ目の別解の方針を書いていきます。
(2)で、表裏表と裏表裏が同じ結果になることの確認は同じようにします。
また、上の解答と同じように、$n-1$ 回目と $n$ 回目がともに〇のものを $a_n$ 通りとし、同様に
「〇×」を $b_n$ 通り、
「×〇」を $c_n$ 通り、
「××」を $d_n$ 通り、
とします。ただし、「〇×〇」と「×〇×」との同一視によって、小さいシナリオ番号にできるものは除くことにします。
$a_{n+1}$ を考えるには、 $n$ 回目が「〇」で終わっていて、 $n+1$ 回目が「〇」ならよく、「〇×〇」と「×〇×」との同一視で新しく一致するものはないので\[ a_{n+1}=a_n+c_n \]が成り立ちます。同様に\[ d_{n+1}=b_n+d_n \]となります。
$b_{n+1}$ は、 $n-1$ ～ $n+1$ 回目が「×〇×」だとすると「〇×〇」に置き換えてシナリオ番号を小さくできるので、すべて除外されます。一方、「〇〇×」は問題ありません。なので、\[ b_{n+1}=a_n \]となります。
$c_{n+1}$ は、 $n-1$ ～ $n+1$ 回目が「××〇」は問題ありません。「〇×〇」の場合を考えます。最後が「×〇×〇」なら「〇×〇〇」と一致するので、必ずシナリオ番号を小さくできます。また、「×、2つ以上の〇、×〇」は、上の解答の中でも書いた通り、必ずシナリオ番号を小さくできます。なので、「〇×〇」の前はずっと「〇」というケースだけが残ります。よって、\[ c_{n+1}=d_n+1 \]が成り立ちます。
以上から、
\begin{eqnarray}
& &
a_{n+1}+b_{n+1}+c_{n+1}+d_{n+1} \\[5pt]
&=&
(a_n+c_n)+a_n+(d_n+1)+(b_n+d_n) \\[5pt]
&=&
(a_n+b_n+c_n+d_n)+(a_n+d_n+1) \\[5pt]
\end{eqnarray}が成り立ちます。これはすべての $n$ について成り立つので、もう一度変形すると
\begin{eqnarray}
& &
a_{n+2}+b_{n+2}+c_{n+2}+d_{n+2}+1 \\[5pt]
&=&
(a_{n+1}+b_{n+1}+c_{n+1}+d_{n+1})+(a_{n+1}+d_{n+1}+1)+1 \\[5pt]
&=&
(a_{n+1}+b_{n+1}+c_{n+1}+d_{n+1}+1)+(a_n+c_n+b_n+d_n+1) \\[5pt]
\end{eqnarray}となります。
ここで、 $F_n=a_n+b_n+c_n+d_n+1$ とすると、 $F_{n+2}=F_{n+1}+F_n$ が成り立ちます。 $F_2=1+1+1+1+1=5$ で、 $F_3=2+1+2+2+1=8$ なので、数列 $\{F_n\}$ はフィボナッチ数列になります。
順番に計算すると、 $F_{10}=233$ となります。よって、「〇×〇」と「×〇×」とを同一視することで、結果は最大でも $233-1=232$ 通りになることがわかり、問題文にあるような $t$ は存在しないことがわかります。これでおしまいです。
全然関係のなさそうなフィボナッチ数列が出てくるのがおもしろいですね。
別解2
もう一つの別解も紹介します。
$n$ 回目の結果のうち、「〇×〇」と「×〇×」を同一視したときの結果の数を $A_n$ とします。
$n\geqq 4$ のとき、 $n-1$ 回目までの結果に、〇か×をつければ、 $n$ 回目までの結果になるので、同一視のことを考えなければ、 $2a_{n-1}$ です。しかし、最後が「〇×〇」で終わるものと「×〇×」で終わるものを新しく同一視するので、 $a_{n-3}$ 通りのシナリオが同一視されます。なので、\[ a_{n}=2a_{n-1}-a_{n-3} \]が成り立ちます。順番に代入して $a_{10}=232$ が得られ、 $t$ が存在しないことがわかります。これでおしまいです。
ここで、少し疑問に思う人がいるかもしれません。$n-2$ ～ $n$ 回目までの「〇×〇」と「×〇×」を同一視することで、 $A_{n-3}$ よりたくさんのシナリオが減るのではないか、と。
例えば、上の解答中でも書いた次の例を見てみます。
「×〇〇〇×〇」
「×〇〇×〇×」
「×〇×〇××」
「〇×〇〇××」
この4つは、同一視により全部同じ結果になるのですが、1つ目と4つ目のように、さらに同一視できるものが増えるのではないか、と。
しかし、こう考えてみましょう。3つ目と4つ目のシナリオは、3回目の結果の時点で、同一視できるようになります。つまり、 $A_3$ を考えている時点で、3つ目と4つ目を同一視しており、4回目以降の結果が何であっても同じと考えています。
2つ目と3つ目のシナリオは、 $A_5$ を考えた時点で同一視が済んでいます。なので、1つ目のシナリオで $A_6$ に考えた時点では、2つ目・3つ目・4つ目のシナリオの同一視は済んでいて、新しく除外するシナリオは増えず、1つ目と2つ目の同一視だけが起こる、というわけです。
つまり、 $n$ 回目ではじめて同一視が起こるものを考えているので、それ以前に起こる同一視はすべて考慮済みなので、 $A_{n-3}$ より多くのシナリオが減ることはないとわかります。
