[過去ﾛｸﾞ] 面白い問題おしえて〜な 六問目 (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))}が昇順または降順に並ぶようにできる。
ってことが言えそう。
でした。後半の部分はそのまま。
上下前次1-新書関写板覧索設栞歴
あと 274 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.224s*