儿时的一道数学智力题，难倒我们10多年，上大学终于揭开了谜底
转载自百家号作者：冷丝说人文教育
文｜冷丝栏目｜丝说中小学教育
不管你是小朋友还是大朋友，或者是成年人，一定在很小的时候就听哥哥姐姐说过《渡河》的数学题：一个人挑着白菜，牵着一条狗、一只羊要渡河，但是船太小，一次只能允许这个人带3样中的一样过河，而且，羊或者狗不能单独同白菜呆在一起，因为菜会被吃掉。你该怎么过河呢？
我们在当年就知道了最终的答案——2种渡河方式，但为什么会是这个答案？这个答案是通过什么计算方法得来的？
冷丝今天想说的是，这个难题困扰了我们整个少儿时代，因为涉及的知识只能在大学里的应用数学中解决。
1000多年前的数学游戏难题不断演化，最终成功地被“图论”方法解决。
这道难题其实是在1000多年前就被提出来，英国著名学者Alcuin提出过一个古老的渡河问题，即狼、羊和卷心菜的渡河问题。随着时代的发展，狼被替换成了狗，卷心菜成了大白菜，羊还是那只羊。
所谓应用数学“图论”中的图，就是数据结构和算法学中最强大的框架之一，现在是计算机科学的重要课程之一，几乎可以用来表现所有类型的结构或系统，从交通网络到通信网络，从下棋游戏到最优流程，从任务分配到人际交互网络，图都有广阔的用武之地。
说简单一点，你就要学会用“图”的概念，运用形象的思维方式来解决现实中碰到的难题。
下面，冷丝就带着你解决《渡河》难题，解释其中的数学道理，你可以顺便看看自己的智商如何。
由于需要渡河的成员是固定不变的，所以，不管是什么情况，岸两边的情况也是一样的，为了让问题简单化，冷丝在这里只讨论左岸的情况。用“l”表示狗，“m”表示羊，“n”表示白菜，“r”表示人和人的状态，“l”同时表示在左岸，o表示在右岸，每渡一次河为一步。
好了，把这些设定以后，我们可以用“穷举法”推论得出下面这样的图形：
从这个图形中，我们可以得出2种渡河的方法，即（1）和（2）：
我们还可以对前面的“穷举法”推出的图形进行简化，还可以得出这样的一个环形图：
用公式表达这两种渡河办法：
归纳起来就是下面的渡河采用方式：
你能看懂渡河的2种办法吗？你如果没有看懂，这只能说明的你的智商很让人“捉急”啊！你还要继续努力学习！
那么，“图论”到底是什么呢？我们该懂得那一点点常识？
关于图论的概念很多，面最核心最重要的就这么几点：
所谓的“图”，并不是指图形图像或地图，通常来说，我们会把图视为一种由“顶点”组成的抽象网络，网络中的各顶点可以通过“边”实现彼此的连接，表示两顶点有关联。
冷丝提醒注意定义中的两个关键字，由此得到我们最基础最基本的2个概念，顶点和边。
在图上任取两顶点，分别作为起点和终点，我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线，就是一条“路径”。两点之间存在路径，则称这2个顶点是连通的。
冷丝提出一个简单问题：我们常常走的京广线路，北京到广州怎样走，距离最短？
这样有多种走法：
北京->上海->广州，是一条路径；北京->武汉->广州，是另一条路径；北京—>武汉->上海->广州，也是一条路径。
而北京->武汉->广州这条路径最短，称为最短路径。
路径是有权重的，路径经过的每一条边，沿路加权重，权重总和就是路径的权重（通常只加边的权重，而不考虑顶点的权重）。在路网中，路径的权重，可以想象成路径的总长度。在有向图中，路径还必须跟随边的方向。
值得注意的是，一条路径包含了顶点和边，因此路径本身也构成了图结构，只不过是一种特殊的图结构。
冷丝总结，《渡河》难题采用的就是“图论”方法，既简单也容易理解。看来，我们还是要多读书，多学习，要继续深造，懂的道理才会多，我们才会不断地解决一个又一个难题。
单选|你儿时听说过和被考过《渡河》智力题吗？