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

CONTENTS


メールニュース会員登録（無料）
モバイルマガジンのご案内
定期購読のご案内
SCIENTIFIC AMERICAN
検索方法はこちら
 バックナンバーのPDF販売

パズリングアドベンチャーSpecial［特別版］
　
「意外列」の上限を探せ！ 田中裕一／平 理一郎

１−２−３−４ page １ of ４
３月号のパズリング・アドベンチャー「雄弁は銀，沈黙は金」（下の囲みを参照）に対して，読者の平理一郎（ひら・りいちろう）さんが意外列の長さに関する性質を発見し，編集部にメールを送ってこられた。さっそく訳者の田中裕一（たなか・ゆういち）さんとの間でメールのやりとりが始まり，意外列の面白い性質が次々と明らかになっていった。お二人により見つかった意外列の性質，それを用いた探索方法や結果を紹介しよう。（編集部）

３月号の問題（要旨）
　記号列が「２-意外列」であるとは，任意の記号ペアX，Yと任意の正の整数Dに対し，記号列の中で「XのちょうどD個後ろにYが来ること」が２回以上はないことをいう。AAXYBBは，Aの４つあとにBが来るパターンが２回繰り返されるから２-意外列ではない。CABACCは，A-A，A-B，A-C，…など，どの記号ペアに対しても同じ間隔の繰り返しがないので２-意外列だといえる。
　記号の任意の３つの組み合わせX，Y，Zと，任意の正の整数D1，D2に対して，記号列の中で「XのD1個後ろにYが，YのD2個後ろにZが来る」というパターンが２回以上なければ，それは「３-意外列」であるという（注１）。 このようにして一般にm-意外列を定義したとき，k種類の記号を使ったm-意外列の中で，最も長いものは何だろう？きれいな理論を作ることができるだろうか？

　本文の中で示されている意外列の定義（上の囲み）は非常に扱いにくい。だが，「XのD個後ろにYが来る」というパターンが２回繰り返されるとき，X同士の間隔とY同士の間隔は必ず同じ値になる。このことに気がついた平は，２-意外列の判定法を以下のように書き直した。

　長さnの2-意外列において，各記号ごとの出現間隔を全記号について集めると，1〜n−1の範囲に含まれる整数が重複なく現れる。逆に，その条件を満たす出現間隔を持つ任意の記号列は２-意外列である。

　この定義の変形が，意外列を考える上での出発点となった。読者には，これは目からウロコが落ちたように感じられることだろう。
　上の囲みにある例で考えてみよう。AAXYBBではAとBの出現間隔はどちらも１となり，１が重複しているため，2-意外列でないとわかる（XとYは各1回しか出現していないので，出現間隔は考えられない）。CABACCでは，Aの出現間隔は２，Cは４と１と５（両端）であるから重複がなく，２-意外列だとわかる。
　平はここから出発し，後述する考察を経て次の「最大長の定理」を導くことに成功した。

最大長の定理
　k種類の記号からなるm-意外列の最大長は （m＋1）k より小さい。

　３月号の問題にあげられていた例で，この定理を確かめてみよう。記号の種類が５（A〜E），10（A〜J），26（A〜Z）の２-意外列を考える。定理によれば，その長さは順に15，30，78よりも小さいはずだ。実際，出題者のシャシャ（Dennis E. Shasha）が用意した答えでは，長さが順に12，26，66となっているので，確かに制約を満たしている。３-意外列では５種類のとき長さ18で，これも条件に合う。しかも，どの長さも定理にいう限界に近い数になっている。したがって，最大長の定理はこの問題の本質をついていると考えられる。
注１：３月号の本文では，X，Y，Zが相異なる記号と書いたが，これは誤訳であり「相異なる」は不必要な条件だった（田中）。

　 →
１−２−３−４ page １ of ４
　
 
Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved