日経サイエンス

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

CONTENTS


メールニュース会員登録(無料)
モバイルマガジンのご案内
定期購読のご案内
SCIENTIFIC AMERICAN
バックナンバーのPDF販売

パズリングアドベンチャータイトル
難易度2
雄弁は銀,沈黙は金 デニス・シャシャ

 But I repeat myself. But you repeat yourself.(しかし私は自分の言葉を繰り返す。しかしあなたは自分の言葉を繰り返す)。
 1文目を読むとなかなかしゃれた書き出しで,何が繰り返されるのかと好奇心をそそられる。しかし,2文目を見た後,どんなことを感じるだろう?何が言いたいのか意味不明ながら,最初の文とよく似ていることは確かだ。
 今回のパズルでは,このような繰り返し構造を考える。次の条件を満たすとき,その記号列が「意外」であると定義しよう。条件とは,任意の記号ペアX,Yと任意の正の整数Dに対し,記号列の中で「XのちょうどD個後ろにYが来ること」が2回以上はない場合だ。冒頭の2つの文では,butとrepeatのペアが等間隔で2カ所に現れているので,この8語からなる記号列は意外だとは言えない。
 他の例をあげよう。AABやAABAは意外な列だが,AABBはそうではない。Aの2つあとにBが来るというパターンが2カ所にあるからだ。同様に,AAXYBBは,Aの4つあとにBが来るパターンが2回繰り返されるので意外ではない。

image

ウォーミングアップ問題
 ではウォーミングアップ問題だ。A,B,Cからなる列,BCBABCCが意外ではないと言える理由を答えてほしい。また,A,B,Cだけを使った7文字以上の意外な文字列を作ることができるだろうか?

ウォーミングアップ問題の答え
BCBABCCは文字Bが間隔2で2回出てくるので意外ではない。長さ7の意外な列の例には,たとえばBACCBCAがある。

 今月の問題として,もっと難しい問題を3つ出題しよう。5個の異なった記号を使うと,どれくらいの長さの意外な列ができるだろう?10個では?26個では?記号としてはアルファベットのA〜E,A〜J,A〜Zを使うといいだろう。実際やってみると,記号が増えても,この長さはそれほど急速に大きくはならないことに気づくはずだ。記号が26個の場合でも,意外な列の最大長は100以下だろうと思われる。
 ここまでは2個の記号のパターンを考えてきた。そこで今までの列を「2-意外列」と呼ぼう。これを拡張すれば「3-意外列」を次のように定義することができる。任意の相異なる3つの記号X,Y,Zが,記号列の中でXのD1文字分だけ後ろにYが,YのD2文字分だけ後ろにZが来るように並んでいるとき,そのパターンが文字列の中で2回以上は現れないような列を3-意外列と呼ぶ。
 アルファベットのA〜Eを使った最長の3-意外列はどうなるだろう?
 任意のkとnに対して,n個の記号からなる最長のk-意外列を考えることができるが,その単純な構成規則はまだ見つからない。きれいな理論を作ることができるだろうか?

 
答えはこちらから
 

訳者 田中裕一(たなか・ゆういち)
アルティス・リサーチ代表。
専門は計算機科学。
 

著者 Dennis E. Shasha
ニューヨーク大学クーラント研究所教授。
専門は計算機科学。
 
原題名
You Don't Say!
(SCIENTIFIC AMERICAN December 2003)
 

 
Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved