• 24th May 2006 - By 薛芒

    <命题>

          以升序排列的自然数组集合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题)涉及到这个问题,当时我只是简单的告诉她“新数组的中位数的值肯定处于组成它的那两个数组的中位数之间”这个直觉。当时真的只是直觉,她也觉得理所当然,但是没想到正儿八经地证明起来还是写了这么长。不管怎样,今天还是亲自证明了,免得想起总有种心虚的感觉^_^。



    无觅相关文章插件,快速提升流量

  • 2 Comments to “答G友关于一个定理的证明”

    请发表您的看法


Ad

free corel downloads

free corel downloads cracked

corel dvd moviefactory 6

corel dvd moviefactory 6 downloads

windows 7 free

windows 7 crack

winrar password cracker serial

wirar password cracker

windows key

windows key

key office 2010

office 2010 key

serial corel draw 11

serial corel draw 11 serials

free corel photoshop download

free corel photoshop download keygen

free winrar download for xp

download winrar for xp for free

download photo shop free

photo shop serial

winrar 3 download

winrar 3 download freedownload

photoshop key

photoshop key

adobe free

adobe free

cs5 serialz

cs5 serialz free

windows 7 key

windows 7 key

office 2010 professional key

office 2010 key

serial winzip 11

serial winzip 11 key

photo shop key

photo shop key

office 2010 free

office 2010 key