赤白のポーンたちの写真撮影(問題)

　2020年9月号では，赤のポーンたちの“賭け事なし”晩餐会に白のポーンたちがなだれ込んできて大宴会に発展した話をしたが，この晩餐会も次第に定着してきて，このごろは初めから赤白のポーン全員が仲良く揃って開かれるようになった。

　会の最後に行う16人全員の記念写真撮影も定番のイベントになった。何度か述べてきたようにポーンたちの身長は微妙に異なり，全員を集めて身長順に並べると等差数列になる。そこでまず，全員が身長順に並んで撮影し，なだらかな直線が浮かび上がった写真を鑑賞する。一方で， 2回目の撮影ではランダムに並んでその不規則性を楽しむことが多い。

　あるとき，1回目の撮影後にポーンの1人が妙な疑問を口にした。「俺たちって，どのくらいでたらめに並べるんだろう？」

　別のポーンが言う。「なんだ，その『どのくらい』ってのは？ でたらめはでたらめであって，どのくらいもへったくれもないだろう」。

　すると最初のポーンが「いや，でたらめの度合いを測るってのは，本当は俺にもよくわからん。だけど，例えばこういうのはどうかな?」と提案する。「さっき撮影したときみたいに俺たち全員が背の順に並ぶと，長さ16の減少列または増加列ができる。ランダムに並んだ場合でも，途中を適当に省いて考えると単調列にできる。そのような単調部分列で一番長いものの長さを元のランダム列の『でたらめ度』と考えるのは？　それが短いほど元の列のでたらめ度が高いとすると，俺たちはどのくらいでたらめに並べるかな？」

　読者のみなさんはこのポーンの疑問がおわかりだろうか？　今，16人のポーンを適当に並べ，その身長を左からa₁， a₂，…，a₁₆とする。このときi₁＜i₂＜…＜i_kなるインデックスi₁，i₂，…，i_kでまたはとなるものを「単調部分列」と呼び，kをその部分列の「長さ」と呼ぶ。16人の列が含む最長の単調部分列をどこまで短くできるかというのがこのポーンの疑問だ。

　16人のポーンの身長は（等差数列を作るのだから）全員異なるが，うまく並べれば，この最長の単調部分列の長さを4以下に抑えることが可能である。そこで，読者にはまず，長さ5の単調部分列を含まないように16人を並べていただきたい。次に，もしこの16人にもう1人加わって17人になったとしたら，長さ5の単調部分列を含まないように17人を並べることは不可能であることを証明してほしい。ただし，新しく加わる1人は他の16人の誰とも身長は異なるものとする。