単調列の長さについて、ＨＰサイト「エヌシとダイユーのパズル研究室」の中のパズル
トランプを並べる
が詳しい。ＨＮ「ａｔ」さんより、ご紹介いただいた。（平成２２年８月２１日付け）
このＨＰサイトを参考に以下を考えたい。
当ＨＰの掲示板「出会いの泉」に、当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんが、単
調列の長さに関する問題を提起された。（平成２２年８月２１日付け）
異なる５つの数字を並べると、必ず左から右、もしくは右から左へ向かって昇順をなす３つ
の数が存在する。
＜例＞ ２，４，１，５，３→２，４，５
そこで、「異なる何個の数字をならべると、必ず４個の昇順の数が存在するのか？」と考え
た。
＜例＞ ５，７，８，３，１，４，２，６ と８個の数字を並べてもだめである。
さらに、 ５，８，３，１，７，２，９，６，４ と、９個の数字を並べたら、８，７，６，４ で、ＯＫ！
（８，７，６，４ は、当ＨＰがいつもお世話になっているＨＮ「らすかる」さんが発見されました。
（平成２２年８月２１日付け））
これは９個全ての順列で可能と言ってもいいのだろうか？
では、１０個では必ず４個がとれるのだろうか？
これを一般化し、異なる ｎ 個の数字を並べるとき、必ず ｒ 個の昇順する数を含むと断定
できるための ｎ と ｒ の関係はとれるだろうか？
この問題について、らすかるさんからのコメントである。（平成２２年８月２１日付け）
９個の順列すべてにおいて、必ず４個取れるとは限らないようです。
たとえば、 ３，２，１，６，５，４，９，８，７ とすれば、４個の昇順の数は存在しませんね。
10個だと、どう並べても、４個の昇順の数が存在するようです。
ｎ＝１〜１０ で、ｒ＝１、２、２、２、３、３、３、３、３、４ となることから、
ｒ−１ ＜ √n ≦ ｒ すなわち、 ｒ＝(√n の端数切り上げ)
となるような気がします。
さらに、ＨＮ「ａｔ」さんからご教示いただきました。（平成２２年８月２１日付け）
ＧＡＩ さんが知りたいとお考えになっているであろう ｎ と ｒ の関係式が、証明も含めて
http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/Puzzle/pigeon/Lv3_Q.html
にあります。鳩ノ巣原理を使って証明しているようです。
このページでは、上記サイトの証明を参考に、ＧＡＩ さんの問題を考えたいと思う。
相異なる自然数列 ａ1 ，ａ2 ，ａ3 ， ・・・ ， ａｎ の部分列 ｂ1 ，ｂ2 ，ｂ3 ， ・・・ ， ｂｋ において、
ｂ1 ＜ｂ2 ＜ｂ3 ＜ ・・・ ＜ ｂｋ が成り立つとき、数列 ｛ ｂｋ ｝ は 増加列
ｂ1 ＞ｂ2 ＞ｂ3 ＞ ・・・ ＞ ｂｋ が成り立つとき、数列 ｛ ｂｋ ｝ は 減少列
という。
相異なる自然数列 ｛ ａｎ ｝ のすべての増加列 ｛ ｂｋ ｝ の中で、ｋ の最大値を
数列 ｛ ａｎ ｝ の最大増加項数
相異なる自然数列 ｛ ａｎ ｝ のすべての減少列 ｛ ｂｋ ｝ の中で、ｋ の最大値を
数列 ｛ ａｎ ｝ の最大減少項数
という。
最大増加項数と最大減少項数の大きい方の値を、数列 ｛ ａｎ ｝ の単調列の長さと定義する。
例 数列 １ ，３ ，４ ，２ において、部分列は次の ２4−１＝１５ 個である。
１
３
４
２
１ ，３ ・・・・・・・・・・ 増加列
１ ，４ ・・・・・・・・・・ 増加列
１ ，２ ・・・・・・・・・・ 増加列
３ ，４ ・・・・・・・・・・ 増加列
３ ，２ ・・・・・・・・・・ 減少列
４ ，２ ・・・・・・・・・・ 減少列
１ ，３ ，４ ・・・・・・・ 増加列
１ ，３ ，２
１ ，４ ，２
３ ，４ ，２
１ ，３ ，４ ，２
上記の計算から、数列 １ ，３ ，４ ，２ の最大増加項数は、３ で、最大減少項数は、２
であることが分かる。
したがって、数列 １ ，３ ，４ ，２ の単調列の長さは、３ となる。
ところで、別の数列 ３ ，４ ，１ ，２ において
３
４
１
２
３ ，４ ・・・・・・・・・・ 増加列
３ ，１ ・・・・・・・・・・ 減少列
３ ，２ ・・・・・・・・・・ 減少列
４ ，１ ・・・・・・・・・・ 減少列
４ ，２ ・・・・・・・・・・ 減少列
１ ，２ ・・・・・・・・・・ 増加列
３ ，４ ，１
３ ，４ ，２
３ ，１ ，２
４ ，１ ，２
３ ，４ ，１ ，２
から、最大増加項数、最大減少項数ともに、２ で、数列 ３ ，４ ，１ ，２ の単調列の長さ
は、２ となる。
このように、同じ数字の順列で得られる数列であっても、単調列の長さは異なってくる。
そこで、相異なる ｎ 個の項からなる自然数列の単調列の長さの中で最小の値を
最小単調列長 といい、 Ｌ（ｎ） と表すことにする。
このとき、らすかるさんの予想された結果
の値が、 ｒ−１＜≦ｒ のとき、 Ｌ（ｎ）＝ｒの成り立つことが、冒頭で紹介したＨＰサイトで証明されている。
例 上記の事実が成り立つとすれば、 １＜√４≦２ なので、 Ｌ（４）＝２
すなわち、相異なる ４ 個の項からなる自然数列の単調列の長さの最小値は、２ である。
換言すれば、単調列の長さが ２ となるような数列を構成するには、項は４個準備すれば
よいということである。ただし、その４項がどのような配列になるかは別途考えなければなら
ないが．．．。
以下、工事中