数の話（解決編・未完成）

（定義）
n（自然数）が「Ｎ」（○のＮがないので代わりに）とは、
n個の自然数を一列に並べたとき、少なくとも長さＮの単調列が存在するときいう。
まず、次が成り立つ。

n（自然数）が「Ｎ」のとき、
n+1は「Ｎ」以上である。
これはほとんど明らかであるが、念のため証明を与える。
n+1（個）並んだ数のうち、どのひとつを取り除いても、
残った数はn（個）あり、それは「Ｎ」であるから、
さきほど取り除いた数を元に戻せば、
n+1（個）は「Ｎ」か「Ｎ＋１」となる。

このことを使うと、
１０が④であることを示すには、
Ⅰ、９が④であって、１０のうちでひとつでも④がある。
Ⅱ、９が③であって、１０のうちでひとつも③がない。
のどちらかを示せばよいことがわかる。

それでは、１から順に調べていこう。
１は明らかに①

２は
12(12,②)
21(21,②)
よって②

３は
12・・・312(31,②),132(13,②),123(123,③)
21・・・321(321,③),231(23,②),213(23,②)
よって②
次に４の場合を考えるわけだが、最小のものを探すので、③については無視して考える。
また、312と213、132と231はそれぞれ逆の関係なので、片方を考えればよい。
（単調増加を逆から見れば単調減少なので。）

すなわち、４は
312・・・4312(431,③),3412(34,②),3142(31,②),3124(124,③)
132・・・4132(432,③),1432(432,③),1342(134,③),1324(124,③)
よって②
ほとんど明らかなことだが、④は出てこない。
なぜなら、②のものについて考えたから、１つ増やしただけでは④が出るはずがないからだ。

５は
3412・・・53412(541,③),35412(541,③),34512(345,③),34152(345,③),34125(345,③)
3142・・・53142(542,③),35142(542,③),31542(542,③),31452(145,③),31425(145,③)
よって③
ここで気づくことがある。４のとき単調列をいくつか探しておけば、
5がその単調列のどちら側にあるかによって、簡単に単調列が見つけられる。
例えば、3412には34,41などの単調列があるが、
5が41の左側（つまり、一番左と左から二番目）にあるときは541という単調列、
5が34の右側（つまり、左から三番目と四番目、一番右）にあるときは345という単調列、
が見つけられる。
また、明らかなことだが、見つけられた単調列には必ず5が含まれている。
つまり、最大の長さの単調列は5を含むというわけである。
なぜなら、5を含まないなら、４のときにすでに③になっているからである。
この考え方はこれからも用いる予定である。

６は
（かなり多いのだが・・・）
53412・・・563412(641),536412(641),534612(346),534162(346),534126(346)
35412・・・365412(641),356412(641),354612(356),354162(356),354126(356)
34512・・・634512(652),364512(652),346512(652)
34152・・・634152(652),364152(652),346152(652),341652(652)
34125・・・634125(641),364125(641),346125(346),341265(346)

53142・・・563142(642),536142(642),531642(642),531462(146),531426(146)
35142・・・356142(356),351642(146),351462(146),351426(146)
31542・・・315642(356),315462(356),315426(356)
31452・・・631452(652),361452(652),316452(652),314652(652)
31425・・・631425(642),361425(642),316425(642),314625(346),314265(346)
注意してもらいたいのは、
例えば34512には345という単調列があるが、6が左から４，５，６番目にあるとき（345の右側）は
④になるので無視をした。
この考え方もこれからも用いる予定である。
よって③

・・・・・・・１０で④を探す。
7 3 1 5 9 10 6 2 4 8（1 5 9 10）
7 5 1 3 9 10 6 2 4 8（1 3 9 10）
などはどう？

もどる