This solution appeared at WXC. 定义: i(k): 以第 k 数为结尾的最长升列的长度 d(k): 以第 k 数为开头的最长降列的长度 注意到当 m< n 时, 不可能有 (i(m), d(m))=(i(n), d(n)). 因为假如第m数小于 第 n 数, 则可把第 n 数加在任何以第 m 数为结尾的升列上构成更长的升列,所以 i(m)< i(n). 反之, 如果第m数小于 第 n 数, 则可推出 d(m)>d(n). 这样,考察所有的 (i(m), d(m)) 的取值, 应该有 10 中可能,则他们不可能都是 (1,1), (1,2), ... (3,3). 必然至少有一个 i(m) 或者 d(m) 不小于4。 对一般的情况类似讨论。可证明,当 n 不小于 (k-1)^2+1 时, 肯定有长度为 k 的升列或降列。 The following is my solution, which is not nearly as good. For i, j >= 2, let M(i,j) be the smallest integer such that any sequence of length M(i,j) must contain an increasing subsequence of length i or a decreasing subsequence of length j. We prove inductively that M(i,j) <= (i-1)(j-1) + 1. First we know M(i,2) = i. Now for j >= 3, form a subsequence this way: let a1 = smallest number in the sequence. a(k+1) = the smallest number after ak. If the length of the subsequece >= i, we are done. Otherwise we need an increasing subsequence of length i or a decreasing subsequence of length j-1 in the rest of the original sequence. Therefore we have M(i,j) <= M(i,j-1) + (i-1). It is easy to see that M(i,j) >= (i-1)(j-1) + 1. So we will leave it as homework. (Still remember in college days, whenever a professor met something he does not want to or forgot how to prove, or a question he does not know how to answer, he would leave it as home work. I don't know whether professors of nowadays, such as wild cauliflower, still do that. :) ) |
So you are now considering yourself a member here and not one of WXC or QQSH? I think the best players are here. It looks like the guy who solved this problem in WXC is just a visitor. |
I consider myself a member of all three places. Two regular members at WXC, avanade, who posted the problem, and 梦回汉朝, apparantly knew the answer. Members here may also have known the answser. Some regular members here, such as wild cauliflower, are too busy to solve more difficult problems. While the new members at WXC (the idiots) are very good. So it is hard to say which site is stronger now. |
You said:"It is easy to see that M(i,j) >= (i-1)(j-1) + 1. So we will leave it as homework. " But this was what you proved. Do you mean -1? |
欢迎光临 珍珠湾ART (http://66.160.158.134/) | Powered by Discuz! X3 |