まとめたい論理クイズ備忘録

まとめたい、解きたいと思っている論理クイズを備忘録として列挙します。私自身が解けていない問題もあります。随時更新。気になったものがあれば解いてみてください。

1. 帽子の色当て問題の一般化

有名問題の一般化です。この参加者(2人)と帽子の色の種類(2色)に共通する2という値を$${n}$$に一般化したものです。解答自体は数行で終わるためわざわざまとめるほどでもないかもしれませんが一応上げておきます。考えてみてください。

　$${n}$$を正整数とする。$${n}$$人の囚人は以下のゲームに参加する: 
　$${n}$$人の囚人にそれぞれ一つずつ帽子が被せられる。帽子の色の候補は$${n}$$色あり、囚人の中には同色の帽子の者がいる場合もあり得る。各囚人は自分の帽子の色を確認できず、お互いにコミュニケーションをとることもできない。囚人たちは自分以外の囚人の帽子の色を確認し、その後皆同時に1色の色を宣言する。宣言した色が自分の帽子の色と一致する囚人がいた場合、囚人たちの勝利となる。
　このゲームに参加する前に囚人たちは$${n}$$の値と候補となる$${n}$$色を教えてもらい、全員で作戦会議を開く。どのような作戦を立てればゲームに勝利できるか。

元問題：https://sist8.com/2hat

2. 箱かくれんぼ

　自作の問題です。ぜひ解いてみてください。おそらく解けますがもし不備などを見つけた方がおられましたら教えて下さい。

二人のプレイヤー$${P_1, P_2}$$は以下のゲームを行う。なお$${n\ge2}$$を整数とする: 
$${n}$$個の箱があり、初めに$${P_1}$$が一つの箱に隠れる。その後$${P_2}$$は次の条件に従って箱を選ぶ:

　(条件$${A}$$)相手の入っている確率が最も高い箱を選ぶ。候補が複数ある場合はその中からランダムに選ぶ。

今回の場合、$${P_2}$$は$${n}$$個全ての中からランダムに一つの箱を選ぶことになる。隠れた相手の箱を当てることができれば当てた者がゲームに勝利する。外れた場合、外した者が外した箱に隠れた後、もともと隠れていた者は箱から出て条件$${A}$$に従って箱を選ぶ。勝者が出るまでこれを繰り返す。
　お互いゲームの内容を把握している場合$${P_1}$$がこのゲームに勝利する確率はいくらか。

3. トランプ当てクイズの一般化

　元の問題自体はそれほど難しいものではありませんがこれを一般化したものです。私は解けていません。トランプはスートや数字が書かれていますが、これらは本質的な要素ではありませんので52個の区別のつくものであればよいです。以下では0から51までの整数から選んだ5個を手札とみなします。
　この問題の本質となる部分を考えてみましょう。5枚の手札(組み合わせ)全体から、4枚の手札を並べたもの(順列)全体への写像を考えてみましょう。この写像を渡し方とみなすには、任意の手札$${x}$$に対しこの写像による像は$${x}$$に含まれる4枚を並べたものである必要があります。もしそのような条件を満たした単射が存在すれば、単射性から元の手札を復元できるため二人目の囚人はカードを当てることができます。単射が存在するには最低でも終域の大きさが定義域の大きさ以上である必要があります。この問題の場合は定義域の大きさが$${{}_{52} \mathrm{C}_5}$$、終域の大きさが$${{}_{52} \mathrm{P}_4}$$であり、当然終域の方が大きくなっています。
　$${n \ge 2}$$を整数とし、$${k}$$を$${2 \le k \le n}$$を満たす整数としましょう。$${0}$$から$${n-1}$$までの整数全体を$${[n]}$$で表すとします。さらに一人目の囚人の貰う手札全体と、二人目の囚人の貰う順列全体に対応する集合を以下のように定めます: 

$$
\begin{aligned}
&・\mathcal{C}^n_k \coloneqq \lbrace A \in [n] \mid |A|=k \rbrace  \\
&・\mathcal{P}^n_k \coloneqq \mathcal{C}^n_k \times [k!]
\end{aligned}
$$

$${\mathcal{C}^n_k}$$から$${\mathcal{P}^n_{k-1}}$$への単射が存在するには、$${|\mathcal{C}^n_k| \le |\mathcal{P}^n_{k-1}|}$$即ち$${{}_{n} \mathrm{C}_k \le {}_{n} \mathrm{P}_{k-1}}$$が成り立つ必要があります。これを解くと$${n \le k!+k-1}$$となります。ですので問題はこの条件が成り立つときに渡すという条件を満たす単射を探すことにあります。

　$${n, k}$$を$${2 \le k \le n}$$を満たす整数とする。$${n}$$が$${n \le k!+k-1}$$を満たすとき、以下の条件を満たす写像$${f \colon \mathcal{C}^n_k \to \mathcal{P}^n_{k-1}}$$、$${A \mapsto (f_1(A), f_2(A))}$$は存在するか: 

・任意の$${A \in \mathcal{C}^n_k}$$に対し、$${f_1(A) \subset A}$$. 
・$${f}$$は単射. 

例えば$${n=k!+k-1}$$の場合はどうか。また存在する場合は具体的に$${f}$$をどのように構成すればよいか。

　元の問題は$${n=52, k=5}$$に相当します。例えば$${k=3}$$とき(即ち一人目の囚人の手札が3枚のとき)、$${n}$$の上限は$${3!+3-1=8}$$ですが、この$${n=8, k=3}$$場合は比較的分かりやすい構成の単射を見つけることができます(気になった方は考えてみてください)。

元問題：https://handyman-shiki.com/20230201-2/