面白い問題おしえて～な 二十問目at MATH面白い問題おしえて～な 二十問目 - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このｽﾚｯﾄﾞのURL■項目テキスト644:１３２人目の素数さん 14/05/25 17:16:00.99 この類か https://www.wolframalpha.com/input/?i=graph+hatune+miku+curve 645:１３２人目の素数さん 14/05/25 19:06:43.66 >>642 ((())())→((()))((())) 深さ3並列度1が1個→深さ3並列度1が2個 646:１３２人目の素数さん 14/05/25 20:21:30.19 っつうかグラフ木から順序数に対応付けすればいいだけじゃん そうすれば置き換えによって順序数は必ず減少するんだから 647:１３２人目の素数さん 14/05/25 20:54:39.85 具体的に 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個以上増やせば操作が無限に行える 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch