三个自然数组成的序列

野菜花 · 发表于 2006-2-1 01:19:24

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

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:59

Does the 序列 contains unlimited elements?

野菜花 · 发表于 2006-2-1 03:40:53

Yes

流动的建筑 · 发表于 2006-2-1 03:44:46

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:03

Right!

野菜花 · 发表于 2006-2-1 19:49:35

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.]

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

动态微博

三个自然数组成的序列

Does the 序列 contains unlimited elements?

Yes[:)]

柿子拣软的捏，题拣容易的解

Right![@};-]

Another proof