論理問題セット
以下の問題は、論理的思考力、アルゴリズム設計、および数学的証明能力を検証するための古典的な事例です。
-
容量の異なる容器による計量：
容量 6 リットルの容器 X と、容量 5 リットルの容器 Y があります。これらの容器のみを使用して、正確に 3 リットルの水を計量する方法を述べてください。 -
カップの配置交換：
6 個のカップが一列に並んでいます。左側の 3 個は水で満ちており、右側の 3 個は空です。たった 1 個のカップのみを移動させて、満杯のカップと空のカップを交互に配置する方法を説明してください。 -
確率論的な決闘（Truel）：
3 人の決闘者 A、B、C がいます。A の命中率は 30%、B は 50%、C は 100% です。公平性を保つため、命中率の低い順に A、B、C の順番で発砲し、生存者が 1 人になるまで循環します。各参加者が生存確率を最大化するための最適な戦略是什么か、また最終的に生存する可能性が最も高いのは誰ですか。 -
平面覆盖の数学的証明：
長方形の桌面上に n 個の同一サイズの円形コインが置かれています。コインは桌面からはみ出たり、互いに重なったりしていても構いません。ただし、新たにコインの中心を桌面内に置こうとすると、既存のコインのいずれかと必ず重なる状態であるとします。このとき、桌面全体を 4n 個のコインで完全に覆盖できることを証明してください。 -
囚人の公平な分配：
2 人の囚人がいる場合、「1 人が分け、もう 1 人が先に選ぶ」という方法で湯の分配争端を解決しました。現在、囚人が 3 人になった場合、同様に公平性を保ちながら争端を防ぐ分配方法を提案してください。 -
目の色の論理パズル：
ある村には赤い目と青い目の 2 種類の住人がいます。自分は鏡などで確認できませんが、他人の目は見えます。自分の目の色を知り、夜に自決すれば天国へ行けるとされます。ある日、外部の人が「少なくとも 1 人は赤い目である」と宣言しました。その後、2 日目に 2 人が自決し、3 日目に残りの 1 人も自決しました。3 人の目の色とその推理過程を説明してください。 -
川渡りの制約問題：
猎人、狼、男（子供 2 人）、女（子供 2 人）が川渡りをします。船には 2 人まで乗れ、操縦できるのは猎人、男、女のみです。猎人がいなくなると狼が全員を襲い、男または女がいなくなると相手の子供が危害を加えられます。全員が安全に渡る手順を述べてください。 -
スイッチと電灯の対応：
隣接する 2 つの部屋があります。一方の部屋に 3 つのスイッチがあり、もう一方の部屋に 3 つの電灯があります。スイッチの部屋と電灯の部屋にそれぞれ 1 回しか入れない場合、どのスイッチがどの電灯に対応するかを特定する方法を教えてください。 -
囚人の帽子の色：
3 人の囚人に黒または白の帽子が被せられました。自分は他人の帽子は見えますが、自分の色は不明です。「他人 2 人が白なら解放」「自分が黒と分かれば解放」という条件です。実際には 3 人とも黒でした。沈黙の後、囚人 A が自分が黒だと確信しました。その推理過程を説明してください。 -
探偵のアリバイ検証：
富豪が探偵を雇う際、候補者 B は「3 年前の 7 月、堤防で釣りをしていたら水面に映った通缉犯の影を見つけ、釣り竿で捕まえた」と主張しました。富豪はこれを嘘だと見抜きました。どこが矛盾していますか。 -
写真の位置関係：
父、母、私、弟の 4 人で写真を撮ります。母は父の左、私は母の左、弟は父の右にいます。左から右への並び順を答えてください。 -
馬と石の運搬：
100 匹の馬で 100 個の石を運搬します。大马は 3 個、中马は 2 個、小马は 2 匹で 1 個運べます。馬をちょうど 100 匹使い切るための各馬の数を求めてください。 -
確率過程の計算：
ある犬の毎年生死する確率は 50% です。3 年後にこの犬が死亡している確率を計算してください。 -
チップの選別アルゴリズム：
2k 個のチップがあり、良チップは不良チップより多いです。良チップは他を正しく判定し、不良チップはランダムに判定します。比較回数に上限を設け、良チップを 1 つ特定するアルゴリズムを設計してください。 -
ボトルのラベル推論：
白酒、ビール、コーラ、ジュースが入った 4 つのボトルがあります。ジュースのボトルのラベルのみ偽で、他は真です。以下のラベル情報から、各ボトルの中身を特定してください。
甲：乙は白酒
乙：丙は白酒ではない
丙：丁はコーラ
丁：最後に貼られた
参照解答（一部）
問題 1 の解法
容器 6L を X、5L を Y とする。
1. X を満タンにし、Y に注いで Y を満タンにする。X には 1L 残る。
2. Y を空にし、X の 1L を Y へ移す。
3. X を再び満タンにし、Y が満タンになるまで注ぐ（Y には既に 1L あるため 4L 入る）。X には 2L 残る。
4. Y を空にし、X の 2L を Y へ移す。
5. X を満タンにし、Y が満タンになるまで注ぐ（Y には既に 2L あるため 3L 入る）。
6. このとき、X には正確に 3L の水が残っている。
問題 2 の解法
カップに 0 から 5 までインデックスを付ける（0-2 が満杯、3-5 が空）。
インデックス 1 のカップ（満杯）の中身を、インデックス 4 のカップ（空）に移し替える。
結果として、満杯のカップは 0, 2, 4、空のカップは 1, 3, 5 となり、交互に配置される。
問題 3 の解法
ゲーム理論および確率論に基づく分析が必要。
命中率 100% の C にとって、A と B は脅威だが、互いに撃ち合う可能性が高い。
A（30%）は、最初に C を狙って外す、あるいは空中に撃つ戦略が有効となる場合がある。
なぜなら、C が生存すれば次に C が A を狙うため、A は B と C が互いを排除するのを待つ方が生存確率が上がるからだ。
最適な戦略は「最初の銃撃で故意に外す」ことであり、これにより A の生存確率が最大化される可能性がある。
問題 4 の証明
前提：これ以上コインを置けない状態（饱和状態）である。
これは、任意の点を中心とする半径 r の円領域が、既存のコインと重なることを意味する。
各コインの半径を r とすると、桌面の任意の点は、既存の n 個のコインのいずれかの中心から距離 2r 以内にある。
つまり、半径 2r の円で桌面を覆盖できる。
面積比を考えると、半径 2r の円の面積は半径 r の円の面積の 4 倍である。
したがって、既存の n 個のコインに対応する半径 2r の覆盖領域を、半径 r のコイン 4 個分で代替可能とみなせる。
不等式 (x+1)(y+1) + xy ≤ 4xy （x, y は正整数）を用いて整理すると、
1 ≤ 2xy - x - y が導かれる。
x, y ≥ 1 のとき、この不等式は恒等的に成立する。
よって、桌面全体を 4n 個のコインで完全覆盖することが数学的に証明される。