[過去ﾛｸﾞ] 面白い問題おしえて〜な 六問目 (966ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
691(4): 03/09/04 17:31 AAS
>>680
一般に、n＞m^2 (n,mは自然数)のとき、
1からnまでの整数を並べ替えた有限数列を{a(k)} (k=1〜n)とし、
1からnまでの整数の集合の項数mの部分集合Sをうまくとると、
Sの項を昇順に並べた有限数列を{b(k)} (k=1〜m)として
{a(b(k))}が昇順または降順に並ぶようにできる。
ってことが言えそう。
方針：次の長ったらしい補題を、帰納法で証明する。
「mを2以上の自然数とし、
1からm^2までの整数を並べ替えたある有限数列{a(k)} (k=1〜m^2)が、
『1からm^2までの整数の集合の項数m+1の任意の部分集合Sは
Sの項を昇順に並べた有限数列を{b(k)} (k=1〜m+1)として
{a(b(k))}が昇順または降順に並ぶようにできない』
という条件を満たすとき、
1からm^2までの整数をm×mのマス目に重複しないように並べた
配置{c(j,k)} (j,k=1〜m)をうまくとると
c(j,k)＜c(j,k+1) (j=1〜m, k=1〜m-1)
c(j,k)＜c(j+1,k) (j=1〜m-1, k=1〜m)
a(c(j,k))＜a(c(j,k+1)) (j=1〜m, k=1〜m-1)
a(c(j,k))＞a(c(j+1,k)) (j=1〜m-1, k=1〜m)
とすることができる。また、このような配置{c(j,k)}は一意に決まる。」
あとは、まかせた。
692(3): 03/09/04 17:43 AAS
>>691 >>680
あ、しまった。
＞ 一般に、n＞m^2 (n,mは自然数)のとき、
＞ 1からnまでの整数を並べ替えた有限数列を{a(k)} (k=1〜n)とし、
＞ 1からnまでの整数の集合の項数mの部分集合Sをうまくとると、
＞ Sの項を昇順に並べた有限数列を{b(k)} (k=1〜m)として
＞ {a(b(k))}が昇順または降順に並ぶようにできる。
＞ ってことが言えそう。
これ、間違い。正しくは
一般に、n＞m^2 (n,mは自然数)のとき、
1からnまでの整数を並べ替えた有限数列を{a(k)} (k=1〜n)とし、
1からnまでの整数の集合の項数m+1の部分集合Sをうまくとると、
Sの項を昇順に並べた有限数列を{b(k)} (k=1〜m+1)として
{a(b(k))}が昇順または降順に並ぶようにできる。
ってことが言えそう。
でした。後半の部分はそのまま。
693(2): 03/09/04 17:59 AAS
>>691-692 >>680
んで、あとはまかせたとは書いたものの、もうちょっと詳しく。
mが補題の条件を満たすとき、n=m^2+1は最終的に証明する命題の条件を
満たすことの証明：
1からm^2+1までの整数を並べ替えた数列からm^2+1を除いたものから、
m+1個の昇順または降順の列がとれない場合について考える。
その数列を{a(k)} (k=1〜m^2)とすると、補題より
配置c(j,k) (j,k=1〜m)が存在し、
c(1,1)＜c(1,2)＜...＜c(1,n)＜c(2,n)＜...＜c(n,n)
a(c(1,1))＜a(c(1,2))＜...＜a(c(1,n))＞a(c(2,n))＞...＞a(c(n,n))
となるので、{a(k)} (k=1〜m^2)にm^2+1を追加するとき、
a(c(1,n))より前に挿入すれば、m+1個の降順の列ができ、
a(c(1,n))より後ろに挿入すれば、m+1個の昇順の列ができる。
694(1): 03/09/04 18:18 AAS
>>691-693
＞方針：次の長ったらしい補題を、帰納法で証明する。
この補題は予想なん？それとも証明できたけど書くのメンドイから書いてないだけ？
695(1): 03/09/04 18:33 AAS
>>691-693 >>680
補題の証明の概略：
次のように、有限数列{p(k)}(k=1〜N_p),{q(k)}(k=1〜N_q)を定める。
p(1)=1
a(p(k))=1のとき、p(k)は最終項(N_p=k)
a(p(k))＞1のとき、
p(k+1)は、p(k)＜p(k+1)≦m^2、a(p(k))＞a(p(k+1))を満たす最小の整数
q(1)=m^2
a(q(k))=1のとき、q(k)は最終項(N_q=k)
a(q(k))＞1のとき、
q(k+1)は、q(k)＞q(k+1)≧1、a(q(k))＞a(q(k+1))を満たす最小の整数
このとき、条件より、N_p≦m, N_q≦m
また、{p(k)},{q(k)}の項の重複はp(N_p)=q(N_q)だけなので、
{p(k)},{q(k)}の項を合わせた集合の要素数はN_p+N_q-1
1〜m^2の整数から、p(k),q(k)の各項を除外したものを昇順に並べた列を
{x(k)} (k=1〜N_x)とすると、そのN_x=m^2-(N_p+N_q-1)
ここで、N_p≠mまたはN_q≠mと仮定すると、
N_x=m^2-(N_p+N_q-1)＞m^2-2m+1＝(m-1)^2なので、
帰納法の仮定より{a(x(k))}からは必ずm個の昇順または降順の列がとれ、
降順の場合は、末尾に{a(q(k))}のどれかを付加して
昇順の場合は、先頭に{a(p(k))}のどれかを付加して、
{a(k)}からm+1個の昇順または降順の列がとれることになる。（詳細略）
これは、条件と矛盾。
よって、N_p＝mかつN_q＝m
あとは、帰納法の仮定から、{a(x(k))}の構造が分かるので、それをもとに
配置{c(j,k)}を構築できる。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.022s