・新単語作り                            GAI 氏

 50音の内で、「い」と「か」の2音を用いると、

 い(胃)、か(蚊)、いか(烏賊)、かい(貝)、いかい(位階)、かいか(開花)

の様に豊富に単語が発生する。(この組合せを考えるのに苦労した。)

 しかし、それ以上この2音だけで作ろうとすると、

 いかいい、いかいか、かいかい、かいかか

の様に同じ音が連なることになり、言い難いし、くどい印象は免れない。どんな長さであって
も、連続して続けることは避けたい。そうすると2音からは上記の6通りの単語しか作れない。

 では、3音、敢えて発音しづらい「ぬ」、「ね」、「む」を決してどんな部分でも同じ音が連続し
ないように、新単語を構成してほしい。

 因みに、「abcacbacbc」を単語とすると、長さ1はOK、長さ2もOK、長さ3は、acbの部分で
繰り返していてアウト(長さ4,5もOK)なので、これは条件を満たさないことになります。

 では、全体の長さが5,10,50(寿限無的単語:もしこれが構成できたら日本一難しい早
口言葉)のものを構成してください。


 DD++さんからのコメントです。(平成26年10月3日付け)

 将棋の千日手のルール変更の話を思い起こしますね。

 1983年までは千日手は同一手順3回を繰り返したら成立だったのですが、同一局面に戻
る手順Aと手順Bがあると、

Aから「AとBを入れ替えたもの」を後ろにつけて、AB
   「AとBを入れ替えたもの」を後ろにつけて、ABBA
   「AとBを入れ替えたもの」を後ろにつけて、ABBABAAB
   「AとBを入れ替えたもの」を後ろにつけて、ABBABAABBAABABBA

とすると、同じ内容3回のループが出ないまま任意の長さの手順を作れてしまうことがわかり、
手順の内容にかかわらず同一局面4回で千日手成立と変更されました。

 この文字列の問題は、ループ制限が2回か3回かという差以外同じ問題ですね。

 以下で、とりあえず56文字、たぶん同一音節の連続はないと思いますが見落としあるかも。

「ぬねぬむねぬねむぬねぬむぬねむねぬねむぬねぬむねぬねむねぬむ
                ぬねぬむねぬねむぬねぬむぬねむねぬねむぬねぬむねぬね」

 以下は取り組んでませんが、結果はどうなるのでしょうね。

(1) 3種の文字で最長どこまで行けるか、あるいは無限に続けられるか
(2) 3種だと有限なら、何種あれば無限に続けられるのか、あるいは有限の文字種では必
  ず有限の文字列しか作れないのか


 at さんからのコメントです。(平成26年10月3日付け)

 たった3種の文字で、どこまででも行けることが知られています。(→ 参考


 DD++さんからのコメントです。(平成26年10月3日付け)

 なるほど。この論文と同じ発想で4種あれば無限にいけることはすぐわかりましたが、++と
--を同一視すれば3種でもいけたのですね。

 文字列の作り方だけピックアップするとこういうことになるわけですか。

 前述の方法で必要な長さより長い文字列を作る
→ABBABAABBAABABBABAABABBAABBABAAB

直前と同じ文字のものをCに置き換え、先頭の1文字を切り落とす
→BCABACBCACBABCABACBABCACBCABACB


 GAI さんからのコメントです。(平成26年10月3日付け)

 無限に可能とは驚きですよね。因みに、1000の長さの単語にしてみました。勿論10000の
長さが必要ならすぐに構成されます。(→ 参考


 とんくまさんからのコメントです。(平成26年10月3日付け)

 問題の本質からは外れますが、辞書を引くと、こんな単語も有りました。

いい【飯】、いい【易易】、いい【依依】、いい【遺意】、かか【嬶】 庶民階級で、妻をいう語

かか【仮果】、かか【花果】、かかい【下界】、かかい【歌会】、かかい【花界】、かかい【河海】

委委佗佗(イイイイ)・(イイタタ) のびやかで美しいさま。

いかいか《「いがいが」とも》 赤ん坊が泣くさま。また、その声。

かいかい【開会】、かいかい【詼諧】、かいかい【怪怪】、かいかい【回回】

かいかい《「かゆいかゆい」から》 疥癬の俗称。


 GAI さんからのコメントです。(平成26年10月3日付け)

 2つの発音「0」「1」だけで、どの部分も決して3回繰り返さない列(Thue-Morse sequence):
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0,
1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1,
1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1,・・・・

について、すごく面白い現象が起こることを知りました。

 数字"0"がある位置A={0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,・・・・}

 数字"1"がある位置B={1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,・・・・}
  *最初の位置は0であるとみなしている。

このとき、f(x)が任意の2次関数であるとすると、A,Bから4個分の要素{ai,bj}に対して、

  Σi=1〜4 f(ai)=Σi=1〜4 f(bj)

例えば、f(x)=x2+x+2 のとき、 f(0)+f(3)+f(5)+f(6)=f(1)+f(2)+f(4)+f(7) が成立する。

 f(x)が任意の3次関数であるとすると、A,Bから8個分の要素{ai,bj}に対して、

  Σi=1〜8 f(ai)=Σi=1〜8 f(bj)

例えば、f(x)=2x3-3x2+4x-5 のとき、
 f(0)+f(3)+f(5)+f(6)+f(9)+f(10)+f(12)+f(15)=f(1)+f(2)+f(4)+f(7)+f(8)+f(11)+f(13)+f(14)

 一般に、f(x)がn次関数なら、A, Bから2n個の要素の数でこの関係式が成り立つ。また、
関数の係数は整数でなくても、有理数や無理数でもかまわない。

 俄には信じられないでしょうが、計算ソフトで確認してみて下さい。


 GAI さんから追加情報を頂きました。(平成26年10月4日付け)

 さらに、この部分の驚くべき関係式として、P、Qを任意の整数とするとき、

  Σi=1〜2n f(P*ai+Q)=Σj=1〜2n f(P*bj+Q)

のありえないだろうと思える強力なものでも成立します。


 at さんからのコメントです。(平成26年10月4日付け)

 大変興味深い等式ですね。この証明はいったいどのようにすればいいのでしょうか?


 DD++さんからのコメントです。(平成26年10月4日付け)

 2次はむしろ当然という印象でしたが、一般の n 次でも成り立つのは予想外でした。確か
に二進法で多項展開してみればほぼ自明な式なのですが...。

 また、f(Px+Q) については、f(x) が n 次式なら f(Px+Q) も n 次式なので、任意の n 次関
数 f(x) について証明した中に既に含まれています。PとQは任意の整数と言わず任意の実
数でいいはず。


 at さんからのコメントです。(平成26年10月5日付け)

 Consider all the sums of the form ±1^5 ± 2^5 ± … ±1985^5.
What is the smallest nonnegative value attained by a sum of this type?


 DD++さんからのコメントです。(平成26年10月5日付け)

 どうせなら「1985」などとせず、今年の西暦でとか...。その場合、5乗は大変なので4乗
の問題になりますが...という発想で、魔改造した問題です。

 Consider all the sums of the form ±1^4 ± 2^4 ± … ±2014^4.
What is the smallest nonnegative value attained by a sum of this type?

 先日の GAI さんの出題から気になっているものの答えが出ない問題があるのですが、お
分かりになる方がいらっしゃいましたらお力を貸していただきたく。

 ルールを「同じ文字が等間隔に3つ並ばない」にすると最長文字数はどうなるんでしょう。
つまり、AABABBAB は 1,4,7 文字目に A が等間隔に並んでいるので、間に挟まった 2 文
字ずつの内容に関係なくアウトと。

 ・ 1種だと AA の 2 文字が明らかに最長。
 ・ 2種だと ABABBABA などいくつかの 8 文字が最長で、9 文字は不可能な証明も比較
  的容易。

 では、3種だと最長で何文字並べることが可能? 4種、5種では?
有限の文字種で無限列を作ることは可能?


 at さんからのコメントです。(平成26年10月5日付け)

 有限の文字種で無限列を作ることは不可能です。これは「ファン・デル・ヴェルデンの定理
から言えます。


 DD++さんからのコメントです。(平成26年10月13日付け)

 日本語Wikipediaを見て、ファン・デル・ヴェルデンの定理の証明の理解を試みました。一週
間かかりましたが、なんとか飲み込むことができました。なるほど、確かに無限列を作るのは
不可能ですね。ご紹介いただきありがとうございました。

 しかし証明が巧妙すぎですね。どこからこんなもの思いついたのやら。


 らすかるさんからのコメントです。(平成26年10月5日付け)

 3種をプログラムで調べたら、26文字(例:AABBAABCBCCACAABABBCACCBCB)が最長
でした。4種は「75文字以上」ということしかわかっていません。


 らすかるさんからのコメントです。(平成26年10月7日付け)

 4種のとき75文字が最長であることが(プログラムによる全探索で)わかりました。まとめると、

1種:2文字(例:AA)
2種:8文字(例:AABBAABB)
3種:26文字(例:AABBAABCBCCACAABABBCACCBCB)
4種:75文字
(例:AABCCDDADAACADBBADBDBCDDBCACCBCBBAADCAA
                     BCCDDADAACADBBADBDBCDDBCACCBCBBAADCB)


 DD++さんからのコメントです。(平成26年10月13日付け)

 探していただいて、ありがとうございます。これは辞書順検索しているのだとすると、3種の
ときにAABBAABBから始めると、26文字続けられないわけですか。思ったよりはるかに複雑
な問題の予感。

 英語 Wikipedia の Van der Waerden number の一覧がほとんど埋まってないということは、
計算機で探すのはひょっとしてNP困難だったりするのでしょうか。


 らすかるさんからのコメントです。(平成26年10月13日付け)

 26文字どころか、10文字しか続けられないですね。AABBAABB の次はAもBも置けません
ので、AABBAABBC となります。すると、この次もAもBも置けませんので、AABBAABBCC と
なります。こうなると、この後にはAもBもCも置けず、これで終了です。

  なるほど、英語 Wikipedia の Van der Waerden number に4種までの答えがあったのです
ね。


                                             投稿一覧に戻る