欢迎光临散文网 会员登陆 & 注册

抽屉原理:如何证明葫芦娃七兄弟是亲兄弟

2021-07-22 22:47 作者:奥数奥术师  | 我要投稿


【思路】

  1. 此题为抽屉原理[1]章节中的进阶题型——“构造抽屉”[2];

  2. 所谓“正难则反”[3],想要证明正面说法“每个男孩都与其他男孩是亲兄弟”显然需要考虑多种情况,倒不如否定该说法的反面[4];

  3. “每个男孩都与其他男孩是亲兄弟”的反面是“7人中至少有两人不是亲兄弟”[5];

  4. 假设“7人中有两人不是亲兄弟”,然后一路推出某个结论[6],若该结论与题目条件[7]矛盾,则说明结论的源头——假设“7人中有两人不是亲兄弟”是错误的;

  5. 假设错误,则只能接受假设的反面“每个男孩都与其他男孩是亲兄弟”正确.

至此完成证明.

【步骤】

反证法步骤示意

【详解】

  1. 为方便描述,设7个男孩分别为A、B、C、D、E、F、G;

  2. 为方便操作,不妨设7人中A与B不是亲兄弟[8];

  3. 考虑除A、B以外的五人C、D、E、F、G与A、B的关系:比如C与A、C与B的关系——C不可能既是A的亲兄弟,也是B的亲兄弟,因为亲兄弟具有传递性[9],所以C最多与A、B中的一人是亲兄弟,若把C比喻为苹果[10],则A与B可当作两个抽屉,苹果只能放入两个抽屉中的一个;

  4. 包含C在内的“苹果”共有5个[11],它们要么进抽屉A[12],要么进抽屉B[13]根据抽屉原理,5÷2=2······1,则放苹果较多的抽屉至少有:2+1=3个苹果,放苹果较少的抽屉最多有2个苹果;

  5. 不妨设抽屉A放苹果较多,抽屉B放苹果较少;

  6. 不妨设E、F、G进了抽屉A,C、D进了抽屉B;

  7. 考虑B与其余6人的关系,由于B与A不是亲兄弟,且A与E、F、G是亲兄弟,则B与E、F、G中的任何一个都不能是亲兄弟[14],所以B最多只能有C、D两个亲兄弟;

  8. 第2条假设[15]推出的“B最多有两个亲兄弟”与题目条件“每一个在其余6人中都至少有3个亲兄弟”矛盾,因此第2条假设不成立,即“7人中至少有两人不是亲兄弟”的说法不对,那么该说法的反面“每个男孩都与其他男孩是亲兄弟”是对的.

至此证明结束.[16]


【参考】

  1. ^我把抽屉原理理解为计算“量变引起质变”所需的最少数量,这个最少数量又被我称为“老大的最少值”,例如将5个苹果放入2个抽屉,老大抽屉里的苹果比小弟抽屉里的苹果多,那么老大的抽屉里最少几个苹果?注意到老大最少,那么小弟就分得最多,要使两人的差距最小,5个苹果应该尽量平均分:5÷2=2······1,即每个抽屉都先得到2个苹果,余下的1个给老大,否则小弟就会变为老大,所以老大的抽屉里最少有2+1=3个苹果.

  2. ^题目中没有明说哪些是“苹果”,也没有说哪些是“抽屉”,需人为指定或计算出抽屉数,然后再利用抽屉原理得到“老大的最少值”或“小弟的最大值”.

  3. ^意思是从正面考虑较复杂的问题,从反面考虑往往容易,在计数问题上也称为“排除法”(总数减去反面数得正面数),在求阴影面积的几何题中也叫做“阴影等于整体减空白”.

  4. ^在本问题中,若待证明命题是某图形中的阴影面积,该命题的反面则是图形中阴影以外的空白,只需要证明空白不存在,整体即阴影即可.

  5. ^若“7个男孩全部互为亲兄弟”为假,则必有至少2人不是亲兄弟;反过来也成立:若7人中找不到2人不是亲兄弟,则7人全都互为亲兄弟.

  6. ^比如:7人中必有某人最多只有2个亲兄弟.

  7. ^每一个人在其余6人中都至少有3个亲兄弟.

  8. ^字母ABCDEFG任意选两人均可,因为他们都是对称的,仅仅是字母命名上的区别.

  9. ^若A与C是亲兄弟,且C与B是亲兄弟,则A与B是亲兄弟.

  10. ^C也有可能是“抽屉”,这种情况的讨论我们放在最后讨论.

  11. ^分别是C、D、E、F、G这5个.

  12. ^即与A是亲兄弟.

  13. ^即与B是亲兄弟.

  14. ^同样是因为传递性:若B与E是亲兄弟,又因为E与A是亲兄弟,则B与A是亲兄弟;但B与A不是亲兄弟,所以B与E不能是亲兄弟;同理,B与F、B与G都不能是亲兄弟.

  15. ^不妨设7人中A与B不是亲兄弟.

  16. ^以上证明还有一点瑕疵,那就是第3条中我们认为C一定与A或B是亲兄弟,还有一种可能是:C既不是A亲兄弟,也不是B亲兄弟,那么C就会“自成一派”:成为与A、B一样的“抽屉”,除A、B、C以外的D、E、F、G四人作为苹果,根据抽屉原理,4÷3=1······1,则A、B、C中亲兄弟最多的一人至少有:1+1=2个亲兄弟,而亲兄弟较少的某人最多有1个亲兄弟,由此看出,“抽屉”越多,由此推出的“必有某人最多有n个亲兄弟”的n值越少,且n≤2;事实上我们之前的证明恰好是n=2的“最难情况”,n=2的情况已经证明,其余n<2的情况也一定成立.

抽屉原理:如何证明葫芦娃七兄弟是亲兄弟的评论 (共 条)

分享到微博请遵守国家法律