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

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

644:１３２人目の素数さん
14/05/25 17:16:00.99
この類か
URLﾘﾝｸ(www.wolframalpha.com)

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個以上増やせば操作が無限に行える

649:１３２人目の素数さん
14/05/26 00:02:26.41
具体的に

650:１３２人目の素数さん
14/05/26 00:09:55.58
> 数列 a_n の一般項を（外側から n 番目の括弧の組の数）で（その内側にある括弧の組の数）を割った値
の部分は、分母を（その内側にある（n+1）番目の括弧の組の数）としても同じ結果になる

>>642の言葉を借りれば、全体について「並列度」を「子供の数の平均」と定義し直して0世代目から並べるイメージ

複雑度が上昇しないことは示せても、最終的に ()()...() の形に収束することは示せないので
厳密な証明には別のアプローチが必要になりそう

あと、具体例を無理に想像するとアッカーマン関数のように急激に増加するのでおすすめしない

651:１３２人目の素数さん
14/05/26 00:41:37.68
>629
> (X(Y)Z)の外側および内側の括弧はそれぞれ対応する括弧であるものとし

仮定から、この操作が可能ならばX,Y,Zにまたがる括弧の組は無い。
従ってこの操作で生成される(XYZ)内の括弧の組は(X(Y)Z)より一つ少なく、
かつ、(XYZ)をいくつ繋げても(XYZ)をまたぐ括弧の組は生まれない。
ゆえに(XYZ)の繰り返し回数が有限ならばこの操作は有限回で収束する。

652:１３２人目の素数さん
14/05/26 01:10:19.38
具体的に書かないのは反論させないためか。

653:１３２人目の素数さん
14/05/26 01:12:04.91
((()))=(X(Y)Z)
X=(
Y=
Z=)

654:１３２人目の素数さん
14/05/26 07:20:59.41
>>648=>>650です

>>651
> 仮定から、この操作が可能ならばX,Y,Zにまたがる括弧の組は無い。
「X,Y,Zにまたがる」を「X,Y,Zとその外側にまたがる」
と言いかえれば成り立ちますね。

確かに、外側同士が「対応する括弧」ですから
選んだ部分列の内側に低レベルの括弧は存在しないといえます。

655:１３２人目の素数さん
14/05/26 12:57:51.49
何度かトライ(631,633,637,642)しましたが、結局、

記号列を食べるある関数F[]を用意し、それが、
F[A(X(Y)Z)B] ＝ F[A(XYZ)B]　＋　α
F[A(XYZ)(XYZ)...(XYZ)B]　＝　F[A(XYZ)B]　＋β
　ただし、常に、α＞β≧０　　（「任意個」のβが積み重なっても、αより小さい）
を満たせばよいということですよね。

そのようなF[]が存在するのは確かっぽいけど、具体的な中身は、当初の予想とは異なり面倒そうです。

656:１３２人目の素数さん
14/05/26 13:05:54.05
具体的に書こうとしないからはっきりしないが
(()()())()()
->
(()())(()())(()())()()
が反例じゃないか。

657:１３２人目の素数さん
14/05/26 13:58:04.27
>>656は確かに、>>648と>>650の反例になってますね
（単純に平均値を取っただけでは、ゴミを巻き込むことで
評価関数が 3/3 --> 6/5 と増えてしまう）

出題者の>>655さんは解決に近づいているようなので
本職の数学者の降臨を待ちつつ様子見

658:１３２人目の素数さん
14/05/26 14:13:52.78
出題者は>>629だが

659:１３２人目の素数さん
14/05/26 20:25:57.86
>>648
一応自作なので出典は無し。
同じような問題はどこかにあるかも。

>>657
>>655は出題者ではないよ。

660:１３２人目の素数さん
14/05/26 21:23:06.93
これは「ヒドラゲーム」と同じ類の問題だな
下のリンク先にグラフ木と順序数との対応付けの方法が載ってる

URLﾘﾝｸ(math.andrej.com)
URLﾘﾝｸ(ja.googology.wikia.com)

661:１３２人目の素数さん
14/05/29 09:53:05.43
>>465
> 面積nを超える平面図形は、内側(境界含む)に
> n+1個の格子点を含むように配置できることを示せ。
>
> ってのが面白かった。

ブリクフェルトの定理。有界がいる。

662:１３２人目の素数さん
14/06/05 03:17:39.63
四角形の４辺と２本の対角線の長さが全て奇数であるものは存在しないことを証明せよ。

663:１３２人目の素数さん
14/06/14 11:48:01.30
四角形の頂点をそれぞれabcdとしたとき、の辺の長さab, bcと対角線の長さacには
ab^2 + bc^2 = ac^2の関係があり　ab,ｂｃを奇数とすると、ab^2、bc^2はそれぞれ
奇数であるから、ac^2は偶数なっちゃうよ。
acを奇数とするとac^2は奇数だから。ab,bc,acがすべて奇数であるこたーないってこと？

664:１３２人目の素数さん
14/06/14 12:23:54.72
長方形でない四角形もあるだろ