主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎
【描述】
i、 有Nb个黑球和Nw个白球,其总数N是个奇数。
ii、现在要从中挑出M个球(M为偶数,M≤N-1),满足这个条件:
其中的黑球个数Mb是偶数,白球个数Mw也是偶数。M=Mb+Mw。
(Nb、Nw 以及M 这三个数的数值是事先给定的;而Mb和Mw的取值有自由度,仅需满足:“是偶数”,以及“相加为M” 这两个约束条件即可)。
【引理】对于任意的和为奇数的Nb和Nw,以及任意的偶数M<Nb+Nw,前述任务都是可以达成的。
【证明】
不失一般性,假设Nw>Nb(Nw≠Nb,因为Nb+Nw 是奇数)。
先尽量选黑球,从0直到最大可能的偶数 Nb0 = 2×floor(Nb/2)。 [floor(x) 是取x的整数部分,例如floor(4.9) = 4。]
如果M∈[0, Nb0],那么任务就可以完成了。
如果M>Nb0,那么我们再接着取 Nw1 = M-Nb0 个白球,即可完成任务。 因为M和Nb0都是偶数,所以Nw1也是偶数。另外,也不难证明Nw1≤Nw。
所以任务完成。证毕。
【例子】假设有3个黑球,4个白球,要选满足条件(ii)的6个球。
做法:先取2个黑球,这就到黑球数为偶数的顶了。再接着取4个白球,即可完成任务。
- 相关回复 上下关系8
🙂您这是奥运征文啊! 不同的蚕 字0 2008-08-08 03:27:16
🙂第一题是什么意思?没看懂 1 河兮兮 字379 2008-08-06 18:22:31
😂“切分次数越少越好” 衲子 字0 2008-08-06 19:18:03
🙂【原创】称球问题的另外证明。(一)【二色划分引理】
🙂【原创】称球问题的另外证明。(二)【称球引理1】 1 衲子 字2225 2008-08-06 13:53:50
🙂【原创】称球问题的另外证明。(三)【称球引理2】 2 衲子 字1463 2008-08-06 14:34:47
🙂【原创】称球问题的另外证明。(四)【主定理】 4 衲子 字1070 2008-08-06 14:54:22
🙂说的明白,送花! 王树 字0 2008-08-07 06:03:45