<命题>
以升序排列的自然数组集合A和B，其median value分别为x和y（x≤y）;将A和B合并为一个新自然数组C，且同样以升序排列。试证明：其median value（假设为z）必然满足以下条件：x≤z≤y。
<说明>
median value：中位数，即一组数从小到大（或者从大到小）排列，正中间的元素（若元素个数为偶数则为正中间两个元素的平均值）即为中位数。
ascending order：升序排列，从小到大排列。
<证明>
⑴当集合A和B的元素个数为1
则A中唯一元素为x，B中唯一元素为y，
则集合C必然为{x,y}，
则z=(x+y)/2，
显然x≤z≤y；
⑵ 当集合A和B的元素个数大于1
设集合A的元素个数为m，集合B的元素个数为n，
则集合C的元素个数必然为m+n；
①显然在集合A中，值小于等于x的元素个数为m/2（m为偶数）或者(m-1)/2（m为奇数）；
同理，在集合B中，值小于等于y的元素个数为n/2（n为偶数）或者(n-1)/2（n为奇数）；
同理，在合并后的、升序排列的集合C中，值小于等于z的元素个数为(m+n)/2（m+n为偶数）或者(m+n-1)/2（m+n为奇数）；
想象合并A和B的过程为：将A中的元素一一插入到B中，则显然在新集合C中，因为x≤y，至少原来A集合中的小于等于x的元素（包括x在内）必然将插入到B中的y的左边，此时y的左边（即小于等于y）元素个数至少为：
(m+n)/2
+ 1（m、n都为偶数，m+n为偶数）或者(m+n-1)/2 + 1（m为奇数n为偶数，m+n为奇数）
或者(m+n-1)/2
+ 1（m为偶数n为奇数，m+n为奇数）或者(m+n-2)/2 + 1（m、n都为奇数，m+n为偶数）。
（说明：+ 1表示将x包括在内，但实际上，只有集合A元素个数m为奇数时，x才是实际存在的元素，需要+ 1；而m为偶数的时候，x只是集合A正中间两个元素的平均值，不是实际存在的元素。由此可见m为奇数还是偶数是决定是否要 + 1的关键。）
由此可见：
m+n为偶数时：z = (m+n)/2 ≤ y；
m+n为奇数时：z = (m+n-1)/2 < (m+n-1)/2 + 1 ≤ y；
即z≤y；
②将集合B中大于等于y的元素插入到A中x的右边的类似方法可以证明得到x≤z，证明过程略。
综上所述，可得x≤z≤y。证毕。
ps：前两天，一位G友问我的一道GRE数学题（新东方发的黄皮书笔试模考练习20页14题）涉及到这个问题，当时我只是简单的告诉她“新数组的中位数的值肯定处于组成它的那两个数组的中位数之间”这个直觉。当时真的只是直觉，她也觉得理所当然，但是没想到正儿八经地证明起来还是写了这么长。不管怎样，今天还是亲自证明了，免得想起总有种心虚的感觉^_^。
慧闽 刘 on May 26, 2006
同桌，强烈要求加一下msn
liuhuimin840609@hotmail.com
欣 on May 28, 2006
佩服 ！