阿里巴巴数学大赛赛题公布，你敢来挑战吗？（含参考答案）

2018 年 10 月 11 日 阿里技术

9月中旬，阿里巴巴在全球范围内发起一场数学比赛，旨在让全社会看到基础科学尤其是数学的价值，理解数学之美。目前，组织方正在紧张地阅卷中，AI会辅助阅卷。

这次数学大赛引发社会强烈关注。活动公开不到一周，组委会收到近4万全球参赛者的报名，共吸引了来自哈佛大学、麻省理工学院、清华大学、浙江大学等诸多高校的学生参与，这一参赛人数也创下近年来数学专业比赛的人数之最。组委会将在10月中旬公布大赛结果，11月中旬举行决赛。

2018年杭州云栖大会上，阿里巴巴CTO张建锋宣布数学比赛正式启动

自从公布数学题目后，社会各阶层人士就在关注解题思路和出题缘由。比如，许多参赛者关注的“外卖小哥如何送外卖最快”这道题，背后反映的是数学中的“网络流”问题。据了解，目前全国的外卖小哥和快递员人数保守估计，已超过千万。有了数学模型和算法的助力后，真的可以解决外卖小哥的实际问题，让数以千万计的外卖小哥在原基础上再提高15%-30%的效率。

在紧张等待结果的同时，我们不妨一起来解读下这次数学比赛的经典赛题。

赛题：“外卖小哥如何送外卖最快?”

上图中有一个无向图，其中圈内数字代表一个地点，边e上数字代表长度

（双向相同）。

a.一位外卖小哥在起点A，要去3个商家取餐，送到3个对应的地方

，即至至至。小哥的电动助力车的箱子同时最多装下2份外卖。

请问：小哥该怎么走最短路径？这个最短路径的长度是多少？这里，A是出发点，最后一餐（不限次序）送达地为终点。为了简化问题，假设商家已经备好了外卖，小哥取餐送餐不用等。又假设每份外卖重量大小一样。

b. 此题与上图无关，而是考虑一个一般的图，图中有很多点和边。外卖小哥刚刚取了一份外卖，计划经过图上的边送给目的地。途中经过每条边e的时候，以概率会收到至送相同地址的另一单外卖。（一个条边上收到另两单及以上的概率小，暂忽略不计。）

假设对应边的概率为。

请问：送一次外卖，小哥平均能收到几个送去相同地址的新单（不考虑电动车的箱子容量）？小哥收到至少一个去相同地址的新单的概率是多少？

c. 此题延续上题，但不再固定路径，而是对路线进行优化。假设小哥每送一单外卖有固定收益r，但是总路径长度（途中经过的每边e的长度之和）是成本。总收益是。（为了简化，这里设成本系数为1）。现在小哥刚刚出发，车上只有一份外卖，箱子最大容量仍设为两份外卖，请问怎么走能够最大化收益？（提示：这里不但要考虑路径长短，还要考虑可能收到送至相同地址的另一单外卖而带来的无额外成本的收益r。假设）

对于这道赛题，一位参赛者说：78年前，“计算机科学之父”图灵用一道数学题，在二战中挽救了2000多万人的生命，使得二战至少提前2年结束；而阿里巴巴的这次全球数学大赛，一道比赛题也能影响很多人，它能使让上千万的外卖小哥群体少绕弯路，早点回家。

究竟本次数学大赛的出题思路到底是什么？我们也请到相关数学家进行解析：

Q：为什么选择购物和外卖小哥送外卖这两个场景？

A：题目要结合实际应用，要让普通群众能读懂，有兴趣动手试试。既然阿里是电商，最关心的问题就是东西怎么卖，卖出去怎么最快送到客户手里，所以选择了定价和外卖小哥送外卖这两个场景。

大家经常讲共享经济么。共享就是为了节约。2c那个题就是最基本的运输类共享经济问题之一，以收益作为杠杆，让小哥尽量一次送两份，节省时间，减少碳排放。你订外卖也便宜了，送得快了。如果是顺风车（运人）顺风货车（运货）的话也是类似的。当然，实际场景比题目里的情形来得更富复杂，拿小哥来说，他的电动车也许能装下超过两份外卖，那些外卖的终点也不一定是一致的。怎么选择、怎么走，会更好？

这些都是大家平时能碰到的问题，但以往的数学竞赛考得不多。我们是想把生活中出现的问题加以简化，让大家用数学方法来试着解决。

Q：数学会对以上两个场景是否会带来效率上的优化，请结合具体案例和数据说明。

A："外配配送实际是数学中的'网络流'问题。虽然外卖小哥凭借自己丰富的经验完成送餐，但有了数学模型和算法的助力后，大概可以在原基础上再提高 15%-30%的效率。而且当任务越复杂时，提高得越显著。"

拿上文赛题a举例，一个人盯它看一小会儿，然后给一个路线，一般来说就挺好的了，长度可能在最优的15%到30%之内。可是你再提高的话，就要有数据（比如每边的长度）、用算法了。即便算法是简单的穷举法，也需要掌握穷举的规则。2a那个问题实际上是有很好的算法，非常快，手机上一按就能就能算出来，毫秒级，而且能解决规模更大更复杂的情况。

Q：希望收到什么样的解答？

A：我个人希望看到的答案是不仅思路正确，而且包含选手自己的发挥。比如正负1矩阵那题，直接去证明并不难，中学生、甚至知道矩阵和向量正交定义的小学生都能试试。题面是问，Hadamard矩阵中，全1的子矩阵一定不大。实际上，几乎全为1的子矩阵的大小也有个界。这个性质在通讯压缩中有意义。如果看到一个解题思路能触及到题目没有问的性质，就是一种惊喜，这样同学有做大学问的潜质。

Q：之前还想过出什么题？

A：想过出这个地图的题，用到的是泛函分析里的Banach不动点定理，结果发现居然是国内小学三年纪给小学生做的题目（虽然答案给出的是比较直觉性的）。国内的小学生教育也真的是不可低估啊！

包括“外卖小哥如何送外卖最快”，本次竞赛含应用题&建模题&数学基础题，共三题，每题三问。点击文末“阅读原文”，即可查看阿里巴巴数学大赛全部赛题。

如果实在实在做不出来怎么办？别着急，阿里妹也为大家准备了官方参考答案（英文版）。长按识别以下二维码，关注“阿里巴巴机器智能”公众号，并在对话框内回复“数学大赛”，获得全部参考答案。