五千年(敝帚自珍)

主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎

共:💬102 🌺203
全看分页树展 · 主题 跟帖
家园 【原创】称球问题的另外证明。(一)【二色划分引理】

【描述】

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个白球,即可完成任务。

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河