今日、友人から次の問題を聞かれました。
ランダムに並べられたn 個の異なる実数 (それぞれの 2 つは等しくない)のリストがある場合、少なくともそれらのいくつが昇順または降順で並べ替えられているでしょうか? 言い換えれば、ソートされたサブリストの最小の長さは?
たとえば、ランダムに並べられた 3 つの数字がある場合、少なくとも 2 の並べ替えられたサブリストがあります。ランダムに並べられた 4 つの数字がある場合でも、少なくとも 2 の並べ替えられたサブリストがあります。しかし、n はどうでしょうか?
どうもありがとう。