液体スイッチで不可能なのは？：日経サイエンス

	日経サイエンスは米国の科学雑誌「SCIENTIFIC AMERICAN」の日本版です。
	HOME

HOME ＞パズリング・アドベンチャー＞液体スイッチで不可能なのは？

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

液体スイッチで不可能なのは？

デニス・シャシャ

　下の図のようにパイプ５本を円形に束ねて立てたものがある。それぞれのパイプには，上から着色された水が注がれる。５つの色は，名前の頭文字をとって，AからEのラベルが貼ってある。Aはアンバー（琥珀色），Bがブルー，Cはクリムゾン（赤），Dがダイヤモンド（無色），Eがエメラルド（緑）だ。パイプはAからEの順に時計回りに並んでいる。隣り合うパイプの間には，３段にわたってスイッチが取り付けてあり，これで色水の流路を変更できる。
　例えば，AのパイプとBのパイプの間の上段のスイッチを開けると，パイプAを流れるアンバーの水がパイプBへ回り，反対にパイプBからはブルーの水がパイプAに流れ込む。色水は混ざり合うことはない。中段や下段のスイッチを開けることで，水の流れをさらに変えることができる。
　上中下どの段のスイッチにおいても，色水は右に回るか，左に回るか，（両側のスイッチがどちらも閉じていれば）まっすぐ下に流れるかのいずれかだ。水を同時に２つの方向に流すことはできない。つまり，同じ段の隣り合うスイッチを同時に開けることはできない。例えば，パイプA-B間の上段のスイッチが開いているときは，パイプA-E間の上段のスイッチは開かない。
　まずはウォーミングアップ問題だ。スイッチの開け閉めを調整して，パイプA，B，C，D，E内の水が一番下では，C，D，E，A，Bになるようにできるだろうか。つまり，パイプAの下の水はクリムゾン，Bはダイヤモンド，Cはエメラルド，Dはアンバー，Eはブルーとなるようにしたい。
　図に示したように，上段では，A-B間のスイッチとC-D間のスイッチを開ける。すると，色の順番はB，A，D，C，Eに変わる。次に中段のスイッチは，B-C間とD-E間を開け，色のパターンをB，D，A，E，Cの順に変える。最後に，下段のスイッチを２つ開ければ目標の色順が得られる。

ウォーミングアップ問題

　この色順は，もとのパターンとはかなり違うので，どんな順番にすることも可能だと考えるかもしれない。本当にそうだろうか？もし，そうではないとしたら，不可能なのはどんな色順だろう？また，すべての色順を可能にするには，スイッチが何段あればよいだろうか。

	坂井公（さかい・こう）

	筑波大学数学系助教授，理学博士。専門は計算機科学。

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。　原題名 Liquid Switchboard （SCIENTIFIC AMERICAN November 2003）


会社案内　\| 「日経サイエンス」はこんな雑誌　\|　個人情報の取り扱いについて　\|	Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved