面白い問題おしえて～な二十問目

面白い問題おしえて～ ..

648:１３２人目の素数さん
14/05/25 23:44:50.14
>>629
なかなかいい問題やねｗ出典が知りたいｗ

>>636のような木構造で考えると、「置き換え」による操作は以下の通り
・根と一致しない部分木を1つ指定する。ただし、部分木は2以上の高さを持つものとする
　(X(Y)Z)
・部分木に属する任意の頂点を1つ消去し、頂点の子以下の部分木をもとの頂点の親に接続する
　(X(Y)Z) --> (XYZ)
・変形した部分木を任意個複製する
　(XYZ) --> (XYZ)...(XYZ)

あとは木の複雑度を数に対応付けて、それらが単調減少することを示せばおｋ
数列 a_n の一般項を（外側から n 番目の括弧の組の数）で（その内側にある括弧の組の数）を割った値
とすれば、変形によりある p, q （p＜q）について a_p が増えて a_q が減るので収束が示せる

注意すべきは、>>635のように X, Y, Z が外側と同じレベル以下の括弧を含む場合で
この場合は無限に増殖できることが示せる

例えば (())(()) で、X="", Y="", Z=")(()" とおくと
　(())(()) --> ()(()) が任意個
となって、1操作につき3個以上増やせば操作が無限に行える

次ページ

続きを表示

1を表示