珍珠湾ART

标题: 三个自然数组成的序列 [打印本页]

作者: 野菜花 时间: 2006-2-1 01:19
标题: 三个自然数组成的序列

三个自然数组成的任意序列:

a1,a2,a3,...www.ddhw.com

b1,b2,b3,...

c1,c2,c3,...

证明存在自然数m,n，使得

a_m >= a_n

b_m >= b_n

c_m >= c_n

作者: ob 时间: 2006-2-1 02:47
标题: Does the 序列 contains unlimited elements?

Does the 序列 contains unlimited elements?

作者: 野菜花 时间: 2006-2-1 03:40
标题: Yes[:)]

Yes

作者: 流动的建筑 时间: 2006-2-1 03:44
标题: 柿子拣软的捏，题拣容易的解

Rearrange the sequence such that a₁≤a₂≤... now we only need to consider sequences b and c.

If b_n is the minimum of sequence b, we have two cases:

(i) There exists an index m, m>n, such that c_n≤c_m;
(ii) For all m, m>n, c_n>c_m.

For case (i), we already find the desired m, n.

For case (ii), we can simply remove index n and do the above analysis again using the next minimum in sequence b. Since natural numbers are bounded from below, after a finite number of steps, we will stop at case (i). QED.

作者: 野菜花 时间: 2006-2-1 03:53
标题: Right![@};-]

Right!

作者: 野菜花 时间: 2006-2-1 19:49
标题: Another proof

Given any infinite sequence of natural numbers we can find a non-decreasing subsequence (proof below). So suppose the three sequences are a_i, b_i, and c_i. Take a non-decreasing subsequence of a_i. Suppose it is a_i1, a_i2, a_i3, ... . Now consider the infinite sequence b_i1, b_i2, ... . It must have a non-decreasing subsequence. Suppose it is b_j1, b_j2, ... . Now consider the infinite sequence c_j1, c_j2, ... . It must have a non-decreasing subsequence c_k1, c_k2, ... . Each of the three sub-sequences a_k1, a_k2, ... , b_k1, b_k2, ... , c_k1, c_k2, ... is non-decreasing. So we may take, for example, m=k2 and n=k1.

[Proof that any infinite sequence of natural numbers has a non-decreasing subsequence: if the original sequence is unbounded, then we can take a strictly increasing subsequence. If not, then since there are only finitely many possible numbers not exceeding the bound, at least one of them must occur infinitely often.]

欢迎光临珍珠湾ART (http://zzwav.com/)