[過去ﾛｸﾞ] 面白い問題おしえて〜な 六問目 (966ﾚｽ)
上下前次1-新

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

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-新書関写板覧索設栞歴

---

あと 271 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ

---

ぬこの手 ぬこTOP 0.010s