パズルの国のアリス

大工と助手の配線工事(解答)

この問題は,英語ではWire Identification Problem(電線同定問題)と呼ばれ,ご存じの読者もおられるかもしれない。両サイドへの行き来を何度も繰り返す必要がありそうな印象だが,そうでもない。実は2回の往復で十分だ。逆に,1回に減らすことはできないだろう。

 解答には「10が三角数であることを利用するのではないか」とのご意見を読者の1人からいただいた。筆者が用意しておいた解答とは違うが,確かに10=1+2+3+4であることを利用したほうがわかりやすそうだから,まずそれを述べよう。

 対応を示しやすいように別荘地中央側の電線を番号順にc0,c1,……, c9と呼ぶことにしよう。南側も同様にs0,s1,……,s9とする。まず別荘地中央に行き,c0-c1-c2-c3をすべてつなぐ。またc4-c5-c6とc7-c8をそれぞれつなぐ。それから南端に戻り,2本ずつ電線を選び通電テストを行う。どの電線も切れていなければ,互いに通電する線が2本,3本,4本のグループに分かれ,1本はどことも通電しないはずだ(そうでないなら,埋設した電線がどこかで切れているから,大工には気の毒だが工事をやり直す必要がある)。再び別荘地中央に行き,今までの結線を外して今度はc3-c6-c8-c9,c2-c5-c7,c1-c4をそれぞれつなぐ。どの電線も2回の結線で別のグループに入るようにするのがミソだ。もう一度南端に戻って通電テストを行うと,今度も1本,2本,3本,4本のグループに分かれる。例えば,s0が1回目は2本のグループ,2回目は4本のグループに入ったとしよう。すると中央側でそれに該当する電線はc8だけだからs0=c8とわかる。他の電線も同様だ。

 しかし,実は10が三角数というのとは無関係に,電線が3本以上の場合に適用できる手法があり,それによっても2回の往復で電線の同定が可能だ。

 まず別荘地中央で,c2-c3,c4-c5,c6-c7,c8-c9をつなぎ(c0とc1はつながないのがミソ),南端に戻って通電テストを行う。例があったほうがわかりやすいだろうから,例えばs0-s8,s2-s9,s3-s6,s5-s7と通電し,s1とs4はどことも通電しなかったとしよう。再び別荘地中央に行き,今度はc1-c2,c3-c4,c5-c6,c7-c8をつなぐ(c0とc9はつながない)。2回目の通電テストでは,s0-s6,s1-s8,s2-s3,s5-s9が通電したとしよう。

 あとは,これらのデータをじっくり眺めていると,電線番号の対応がわかってくる。まず,2回ともつながなかったc0だが,2回とも通電のなかったs4と同じ線だとわかる。つまりc0=s4だ。次にc1だが,最初のテストでは通電していなかったが,2回目のテストで通電したs1と同じ線だとわかる(c1=s1)。さらにc2だが,2回目のテストでc1とつないだので,2回目にs1と通電したs8と同じだ(c2=s8)。さらに最初のテストでc2とつないだc3は,s8と最初のテストで通電していたs0とわかる(c3=s0)。以下,順繰りにたどっていくことで,c4=s6,c5=s3,c6=s2,c7=s9,c8=s5,c9=s7と対応関係が現れてくる。電線が3本以上の場合にこれをどう一般化するかはほとんど自明だと思うので,読者にお任せしよう。

 どちらの手順でも,実際には,電線を利用する前に別荘地中央に行って結線を外す必要があるし,番号札もわかりやすくつけ替えたほうがよいだろうが,ともかく2往復だけで電線の同定はできる。実は,後者の手順ではc0=s4の同定はできるが,この線が切れていてもそれがわからない。電線が1,2,4本以外の場合,2往復ですべての電線を同定するとともに,電線が切れていればそれがわかるような手順もあるが,複雑だ。さらなる改善を含め読者の工夫を期待したい。

問題はこちらです