数字排序 from WXC

fzy · 发表于 2005-4-15 18:05:26

Difficulty: +++

1,2,3,...,10任意排列，必可找出4个，它们是升序或降序的

General version: Given a number k > 1, find the smallest number n so that when 1,2,3,...,n put in any order, there are always k of them in increasing or decreasing order.

This problem appeared at WXC yesterday. It does not look very difficult and should have a simple solution. But I did not find one. The solution I have is to solve the general version and then apply the result to 4.

fzy · 发表于 2005-4-22 20:25:07

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. :) )

乱弹 · 发表于 2005-4-23 00:06:13

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.

fzy · 发表于 2005-4-23 00:48:37

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.

yma16 · 发表于 2005-4-23 01:46:26

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?

		自动登录	找回密码
密码			立即注册

动态微博

数字排序 from WXC

We were beaten this time

I think this is equally good.

回复：I think this is equally good.

回复：We were beaten this time