赤白のポーンたちの写真撮影(解答)

　最初の「長さ5の単調部分列を含まないように16人を並べる」問題は，いきなり答えを与えて，読者のみなさんにそれを検証していただこう。

　ポーンを身長の小さいほうから順にP₁，P₂，…，P₁₆とすると，例えばP₄，P₃，P₂，P₁，P₈，P₇，P₆，P₅，P₁₂，P₁₁，P₁₀，P₉，P₁₆，P₁₅，P₁₄，P₁₃と並べると，長さ5の単調部分列を含まない。他の並べかたもあるが，一般にn²人の場合，このように身長順にn人ずつn個のグループを作って同様に並べれば，それが長さn＋1の単調部分列を含まないことは納得していただけるだろう。

　逆にm＞n²のとき，m人を並べて長さn＋1の単調部分列を含まないようにすることは，全員の身長が異なれば不可能である。よって，m＝17で全員の身長が異なれば，長さ5の単調部分列を必ず含むことになる。これを証明するのが次の問題だ。

　それがなぜかを考えるには，任意に与えられた数列a₁，a₂，…，a_mの中から最長の単調部分列とその長さを探し出すアルゴリズムの1つが参考になるかもしれない。それは次のようなものである。左からk番目の要素が最後になるような最長の増加部分列の長さをU（k）と書き，同様に左からk番目の要素が最後になるような最長の減少部分列の長さをD（k）と書こう。このときU（k）とD（k）は帰納的に次のように計算できる。

U（k）＝max｛U（i）｜i＜kかつa_i＜a_k｝＋1
D（k）＝max｛D（i）｜i＜kかつa_i＞a_k｝＋1

ただしとする。従ってU（1）＝D（1）＝1である。このアルゴリズムのアイデアは難しくはない。例えばUで説明すると，a_kより左に列を探しにいき，a_i＜a_kでU（i）が最大のものがあれば，長さU（i）の増加部分列a_t＜a_s＜…＜a_i（t＜s＜…＜i）が存在するから，その後ろにa_kをくっつけて，長さU（i）＋1の増加部分列a_t＜a_s＜…＜a_i＜a_kを作るというものだ。Dも同様である。

　U（k）とD（k）をすべてのk＝1，…，mについて計算してしまえば，問題の最長の単調部分列を見つけだすには，その中から最大のU（k）またはD（k）を取り，それが示す増加部分列または減少部分列を取り出せばよい。

　このアルゴリズムは，素朴に実装しても，記憶容量はmに比例する量，計算時間はm²に比例する時間で実行できるから，悪くないものだ。この種の「元の問題をよりサイズの小さい部分問題に帰着し，その結果を記録しておいて，それを利用して元の問題を解く」という形になっているアルゴリズムは，一般に「動的計画法」と呼ばれ，計算機で問題を解く場合の常套手段の1つになっている。最長の単調部分列を見つけるためのアルゴリズムは，動的計画法の代表例といえよう。

　ちなみに，このアルゴリズムを先のポーン列P₄，P₃，P₂，P₁，P₈，P₇，P₆，P₅，P₁₂，P₁₁，P₁₀，P₉，P₁₆，P₁₅，P₁₄，P₁₃に適用すると，下の表のようになり，U（k）とD（k）のどこにも5以上の数値は現れないから，長さ5の単調部分列は含まれていないことがわかる。

　さて，異なる数値からなる列は，n²よりも長ければ，nよりも長い単調部分列を必ず含むが，そのことへのヒントは，上の表のUとDを眺めていれば気づくかもしれない。ポイントはj＜kなる2つのインデックスjとkを見た場合，U（j）＜U（k）またはD（j）＜D（k）が成り立つことである。少し考えてみれば，これは当たり前だ。a_j≠a_kだから，a_j＜a_kまたはa_j＞a_kだが，定義より前者ならばU（j）＜U（k）だし，後者ならばD（j）＜D（k）である。

　以上から，異なるjとkに対してU（j）＝U（k）かつD（j）＝D（k）となることはないことがわかる。もしD（1），U（1），D（2），U（2），…，D（m），U（m）の中にnよりも大きい数が現れなければ，D（k）もU（k）も1，2，…，nのどれかということになる。しかし，対（D（k），U（k））の可能性はn²種類しかない。従って，m＞n²ならば，ある異なるjとkがあって，U（j）＝U（k）かつD（j）＝D（k）ということになり，上でみてきたことに反する。