最長増加部分列(LIS)について勉強しています。資料に

質問

最長増加部分列(LIS)について勉強しています。資料に
「ｎ個のリストLについて、ｎ個の値がすべて異なるとき、
　Lは少なくとも長さ｛√(ｎ)の切り上げ｝の
　増加部分列, あるいは減少部分列をもつ」
とあります。
　考えたんですけど、その根拠がわかりません。

文章から、証明方法として背理法で
「長さが｛√(ｎ)の切り上げ｝より少ないとしたとき、
同じ値の要素が出てくるという矛盾を導く」
という方法を考えたんですが導けませんでした。
この方法もしくは違う方法あればご教授願います。

回答No.2

pori_boy · ベストアンサー

こんにちは

この問題では，
「ある長さの部分増加列が存在しない」とき
「ある長さの部分減少列が存在する」ことを
証明するのが良いのではないかと思います．

参照URLでは，具体的な例から証明まで，
比較的わかりやすく紹介していると思うので，
一度見てみることをおすすめします．

参考URL：

http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/Puzzle/pigeon/Lv1_Q.html

お礼

理解できました。ありがとうございます。

回答No.1

Tacosan

ん～,
「長さが ceil(√n) の増加部分列がない」と仮定して, 「長さが ceil(√n) の減少部分列が存在する」
ことを示す?

お礼

理解できました。ありがとうございます。