新型ウイルスの形を暴け！：日経サイエンス

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

HOME ＞パズリング・アドベンチャー＞新型ウイルスの形を暴け！

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

新型ウイルスの形を暴け！

デニス･シャシャ

　リペラノイド（repellanoid）という名のウイルスがさまざまな病気にかかわっていることがわかった。このウイルスは円筒形をしているが，円筒の周長は不明だ。
　円筒はたくさんのリングを積み重ねるようにして構成されている。各リングは紐（ひも）状のパーツをつないで輪にしたものだ。1本の紐が1つのリングになることもあれば，複数の紐がつながって1つのリングになることもある。紐には5種類の長さがあり，それらを色で区別している。長さ4の紐は薄緑，長さ5は青，長さ6は赤，長さ7は黄色，長さ8は紫だ。
　円筒のリングを縦方向に次々に調べたところ，次の制約条件があるとわかった。ある色の紐のすぐ上やすぐ下に同じ色の紐が来ることはない。同様に，縦に2つか3つ離れた位置にも同じ色の紐が来ることはない。つまり，同じ色は距離3までは反発しあう（訳注：ウイルス名は「反発する」のrepelにちなむようだ）。
　もちろん，リングはすべて同じ長さである。今月の基本問題はこの制約を満たす円筒で，最小の周長を持つリペラノイドはどういう構造をしているのかを突き止めることだ。

ウオーミングアップ問題：

　基本問題を解く前にまずはウオーミングアップをしよう。同じ色は距離2まで反発するとし，紐のタイプは，薄緑（長さ4），青（5），赤（6），黄色（7）の4種類だけとしたら，最小の周長を持つリペラノイドはどういう構造だろう。

発展問題：

　別の科学者グループがミニリペラノイドと呼ぶ第2のウイルスを発見した。次のことがわかっている。紐は5種類あり，いずれも長さは2 以上の整数。リングの周長は7で，同じ色は距離3まで反発しあう。これはどんな構造をしているだろう？

ウオーミングアップ問題の答え：
周長は12。薄緑-薄緑-薄緑，赤-赤，青-黄色のリングを積み重ねる

	坂井公（さかい・こう）

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

	Dennis E. Shasha

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


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