2002年度 中京大学 一般推薦（情報科学部）
| ここに１つの不思議な電灯がある。この電灯は３個のスイッチを持っていて、 その中のどれか２個が「入」、残りの１個が「切」の状態の時だけ点灯し、それ 以外の状態の時はすべて消灯になるという。 今、電灯は消灯していて、部屋の中は真っ暗である。そこで、スイッチを押し てこの電灯を点灯させたい。ところが、どのスイッチも、押すたびに「入」と「切」 が切り替わるタイプのスイッチなので、外見上、それがいま「入」になっている か、「切」になっているかは判断できない。また、３個のスイッチは完全に同じ 形をしていて、場所も固定されていないため、どのスイッチがどれかの区別は つかない。しかも、暗闇のせいで、いま押したスイッチがどれであったかも確認 できないとする。 さあ、この電灯を確実に点灯させるには、どのようにスイッチを押せばよいだ ろうか？なお、スイッチは１個だけ押してもよいし、複数個（２個または３個）同 時に押してもよいが、どちらも１回の操作と見なす。また、そのような操作を何 回行ってもよいものとする。 ここで問題を少し整理してみよう。電灯が消灯しているとき、どのスイッチが ① 「切、切、切」 従って、ここでの問題は、スイッチの状態を消灯状態から、最終的に点灯状態 |
【解答例】
①については本文中に分析されているので省略する。②の場合、最初にスイッチを
１個押したとき「切、入、入」となって点灯するか、「切、切、切」の状態かの２通りに別
れる。２個押したとき「切、切、入」、「入、入、入」の２通りに別れる。３個押したとき、
「切、入、入」となり点灯する。１個または、２個押したときは２通りに別れる。③の場合
１個押したとき「切、入、入」となり点灯する。２個押したとき「切、切、入」と②の状態と
なる。３個押したときは①の状態になる。
さて、以上の分析結果から、出来るだけ少ない回数で電灯を確実に点灯させるため
には、
１ ②の状態の場合を考える。②では、２個押すと、枝分かれが生じ、②の状態のまま
という場合がある。ということは、消灯したスイッチの状態が確認できないときには、2
個押すことは、電灯を確実に点灯させるという操作に貢献しないことになる。
２ 消灯状態の場合を少なくするためには、最初にスイッチを３個押せばよい。この場
合②は点灯し、点灯しなかったときは「切、切、切」、「入、入、入」の２通りの状態にな
る。
３ 続いて、スイッチを１個押せば、①の状態の場合は②の状態「切、切、入」になり、
③の状態は「切、入、入」となり、点灯する。（スイッチを２個押した場合でも、結果は②
の状態か、または点灯するので、１個押したときと同じ状態になる。）
４ この段階で、点灯してないスイッチの状態は、②「切、切、入」の状態なので、続け
てスイッチを３個押せば、「切、入、入」となり点灯する。
代って、３個、１個、３個（または、３個、２個、３個）と順に押していけば、消灯時のス
イッチの状態がどのような場合であっても、確実に点灯できる。
ちなみに、消灯時のスイッチの状態がどんな状態であっても１個、３個、１個と押して
いけば、確実に点灯することも確認できる。
【図】
① １個押す→②と同じ ② １個押す→点灯 ③ １個押す→点灯
２個押す→点灯 または①と同じ
２個押す→②と同じ
３個押す→③と同じ ２個押す→②と同じ
３個押す→①と同じ
または③と同じ
３個押す→点灯
『推薦入学年鑑』（栄美通信）より