ｸｲｽﾞ大陸

Yssです。こんにちは。

古典的なスイッチのクイズがあります。

屋根裏部屋に電球があり、いまあなたがいる一階にはスイッチが３個ある。
このどれかが、屋根裏部屋の電球に通じているのだが、ここからでは点いたかどうか確認できない。また、別の電球が点灯するなどの情報で「消去法」を使うこともできない。
一往復するだけで、どのスイッチが屋根裏部屋の電球のものかを確定せよ。

というもの。

光っている、切れているが温かい、冷えている、の三種類の情報を作ることで一往復での判別が可能になります。


さて本題です。
たぶん、問題の本質は、今の話とは、あまり関係ありません（すいません）。

ある屋根裏部屋に、電球がありました。しかしなんと、１Ｆにスイッチは２４個もあります。
昨日の午後から挑戦しているのですが、どのスイッチがつながっているか、一向に分かりません。

（あまり書くとネタバレしちゃうので、ざっくりしていてスミマセンが）
その電球もスイッチも配線も、正常に機能していることは、確認できました。
しかし、点いている、温かい、冷たいで判定していく、例の作戦を実行したのですが、失敗しました。まったく冷たいままなのです。


どうやら、スイッチは複数操作しないと、ダメなようです。

スイッチはS1からS24まであります。
11/17追記：スイッチのＯＮ／ＯＦＦは手元で分かるタイプです。
スイッチＯＮを真として、Ｃ言語的な論理記号で書くと、論理積を&&として、

あくまでたとえば、ですが、
S1 && S2　が真の時、あるいは、
S1 && S2 && S3　が真の時、
のように、二つ以上のスイッチが真（ON）のときに電球が点くようです。

別の言葉で言うと、スイッチが何個か直列になっていて、その経路を全てＯＮにしなければ、電球は点かない、と言い換えることができます。

スイッチ１個では点かないことを半日かけて理解しました。
しかし、
どのスイッチがつながっているのかも、
そもそも、何個ＯＮにすればいいのかも、
現時点では分かりません。



さて問題です。

問１　難易度★★から★★★ぐらいです。
上の仮定が成立する場合、最も効率的なスイッチのルールの探索方法を提案してください。そのとき、何往復が必要になるでしょうか。
あくまで、点灯させるのは、屋根裏部屋の電球１個です。

問２　難易度修正。問１が解けた皆さん正解されています。★★ぐらいのようです
上の論理式の仮定が成立するとは限らないとした場合、
問１において、最も効率的な探索方法が裏目に出ることがあります。
それは、スイッチの配線がどのようになっている場合でしょうか？


問２は、問１の正解を前提にしていますので、
問１が分からないと、問題の意味自体もよく分からないと思います（スミマセン）。


でも、実は、ある、有名な、話なんですよね。

そこで、
問３　この問題は、テレビのニュースにもなった有名な話をモチーフにして作りました。（11/17追記：元ネタは、数学的には近いのですが、本問の場面設定とは相当かけ離れています）それは何でしょう？　その話が分かれば、必ず分かる、中心人物がいます。
人名を漢字で（姓名の間に空白を入れずに）囁くと、かってに君が反応します。