上海疫情封在家中有三个月，辅导了小孩子功课，每每小孩遇到不会做的题目，比她更着急。有时也会想起自己学生时代的样子，遇到难题，心中升起必须克服难题的决心，现在自己娃，怎么没有我当年的风采了。哈哈，扯远了，这两天网上看到一道小学二年级的题目，其实我之前做过类似的题目，但是当下还是震惊了，怎么现在小学二年级题目有这么难？

题目是这样的：
赛车比赛题目.jpeg

配合网友的回复，我马上想到了之前类似的问题，说是25匹马，5个赛道，至少比几场保证找出最快的2匹马。赛马这题答案我记得很清楚7场比赛，先分组进行小组赛：

赛马比赛分组.png

首先一个虚线框就是一场比赛，上来25匹马，分5组，进行5场预赛。5组比赛会得到组内的名次，比如A组，A1->A2->A3->A4->A5，每组第一名就是A1，B1，C1，D1和E1，然后第一名之间安排一场决赛：
赛马比赛决赛.png

假设结果就是A1->B1->C1->D1->E1(真正结果不重要，不管怎么样，总能推理出最后的结论)，这时候我们就通过4场比赛，知道了第一名是A1，那第二名是谁呢，是不是B1，不一定哦，有可能是在小组赛中被A1淘汰的A2，所以安排场附加赛吧，A2 vs B1：
赛马附加赛.png

附加赛之后，就能知道前两名了。话说回小学二年级赛车这道题目，其实思路一模一样，就是通过小组赛->决赛->附加赛，完成前两名的确认，也就是说赛车的话，通过至少5场比赛，保证找出前两名的赛车。

作为小学二年级的题目很变态了吧，但是出题的人还多问了一句，怎么证明这件事情呢，为什么通过4场比赛一定不能保证找出前两名呢？这个证明难倒我了，抓耳挠腮半天，没想出来。然后我就看了下出题老师的分析，茅塞顿开，原来还可以使用图论+反正法来证明。大致的过程如下：
首先把每一辆赛车想象成点，那么我们一共有9辆赛车，一共9个点，每场比赛，只能进行3辆赛车的比拼，每次比拼完，我们会有一个名次，紧挨着的前后两名之间，使用一条有向边连接，这个我文字讲得有点绕口，一图解千愁：
赛车比赛顺序图.png

圆圈表示赛车，1号比2号快，2号比3号快，所以每次比赛，我们仅仅能得到2条有向边，如果进行4场比赛，那么总共的有向边数量是4*2 = 8条，而赛车的数量是9，也就是节点数量是9，8条边，9个点，如果要保证所有边都连接到一张图中，不能出现环，否则边的数量不够。
环.png

出现环就意味着9个点形成了若干个分开的子图，上面图中9个节点，分为了两个子图，那么就会有一个问题，第一名都不知道是谁，为什么？因为在1～8节点所在的图中，1号赛车最快，9号赛车单独成子图，9号赛车和谁都没有比过，那么到底9号和1号赛车谁快呢？不知道。所以8条边，安排的比赛结果，划分为多个子图，这样是无法确认前两名的。

那我们4场比赛的结果，如何是可以前两名的图形呢，如下：
树形图.png

左边就是分3场比赛（1、4、7，2、5、8和3、6、9分别比赛），得到结果后，4、2、3比一次，结果是4->2->3，转化这张单图，得到右侧的结果，其实就是一个树形的图，那么前两名就是1、4号赛车。

这样我们很容易举出反例，你不是就8条边么，我最后4、2、3的结果是2->4->3，图就变成非树形图，如下：
多个根结点图.png

这样又回到之前多个子图的问题，我们是没法确认1号赛车和2号赛车谁快的，也就没法真正确认前两名是哪两辆赛车。

OK，至少5场比赛，而非4场比赛保证找出最快的2辆赛车得证。是不是挺难的，至少我是没有想出来，通过图论+反证法证明这个数据结论，由衷发出感慨，活学活用好难啊，能做到的大佬，真的太强了。
373d2c7114b84ac57e8b9e3ad3eb78fe.jpeg

标签: 科普, 小学问题

已有 26 条评论

  1. 1 1

    1

    回复
  2. 1 1

    555

    回复
  3. nuczzlvkpx nuczzlvkpx

    想想你的文章写的特别好https://www.237fa.com/

    回复
  4. aapdkrhuoz aapdkrhuoz

    想想你的文章写的特别好https://www.ea55.com/

    回复
  5. xfxeanshub xfxeanshub

    看的我热血沸腾啊www.jiwenlaw.com

    回复
  6. vresnkefen vresnkefen

    兄弟写的非常好 https://www.cscnn.com/

    回复
  7. bkyyxwzlri bkyyxwzlri

    《杀神出狱，血染京都》短片剧高清在线免费观看：https://www.jgz518.com/xingkong/14795.html

    回复
  8. txddeleelr txddeleelr

    《华人侦探陈查理之中国猫》喜剧片高清在线免费观看：https://www.jgz518.com/xingkong/136001.html

    回复
  9. vysmsxhsem vysmsxhsem

    《史前巨鳄3》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/10453.html

    回复
  10. bxoglvgfdv bxoglvgfdv

    《华人侦探陈查理之中国猫》喜剧片高清在线免费观看：https://www.jgz518.com/xingkong/136001.html

    回复
  11. btlxvtyjnl btlxvtyjnl

    《史前巨鳄3》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/10453.html

    回复
  12. fwazrdbaco fwazrdbaco

    《京武春秋》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/62609.html

    回复
  13. bnsxvatrii bnsxvatrii

    哈哈哈，写的太好了https://www.lawjida.com/

    回复
  14. cgxqxyftka cgxqxyftka

    逆境中的反思充满生命韧性。

    回复
  15. tyfuhxvedw tyfuhxvedw

    化身博士

    回复
  16. ddwoixbppn ddwoixbppn

    彩虹

    回复
  17. fccubcqozh fccubcqozh

    七百万元大劫案

    回复
  18. vopjykpbkg vopjykpbkg

    恐龙战队

    回复
  19. jdtyjfwdqg jdtyjfwdqg

    霹雳玫瑰

    回复
  20. rutrdyvzpx rutrdyvzpx

    阿赫德的膝盖

    回复
  21. tmgtportvl tmgtportvl

    红灯停绿灯行

    回复
  22. kidrrniciv kidrrniciv

    耶里肖

    回复
  23. mdbwdeqrel mdbwdeqrel

    爱情诅咒

    回复
  24. wujrrgeggn wujrrgeggn

    光年正传

    回复
  25. pbjyghhulr pbjyghhulr

    总是有爱在隔离粤配

    回复
  26. 鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099 鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099

    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099
    华纳公司合作开户所需材料？电话号码15587291507 微信STS5099

    回复
取消回复

添加新评论