从“夫妻过河”谈起

rainbow

从“夫妻过河”谈起
首都师范大学数学系　马祖良
　　夫妻过河问题是一个历史久远的阿拉伯的趣味智力题．问题是这样叙述的：
　　有三对夫妻一同旅行，途中需要渡过一条河．按照古代当地的规矩，妻子不能在其丈夫不在场的情况下与其他男人在一起，而渡河的小船至多只可以载乘二人(无船夫)．问如何安排渡河程序，使这三对夫妻既不违反当时的规矩，又能顺利地渡过河去．
　　这类问题在一些智力竞赛中，常常是根据问题所给条件，逐一试验，最后得出结论．但这样做似乎与数学并无什么联系．其实只要对这些问题加以分析，建立适当的模型，就会发现判定这类问题是否有解，以及如何求解都并不困难，而这类数学模型一般被称为状态转移模型．
　　1．建模
　　我们把此岸有M个男人(丈夫)，F个女人(妻子)的情形称为一种状态，用一对数组(M，F)表示，注意M、F的顺序不要变，其中M、F均为不小于0且不大于3的整数．很显然，在我们的问题中，并非所有数组所表示的状态。
　　　　(M，F) M，F∈Z，0≤M，F≤3
　　都是被允许的．例如在0＜M＜F≤3时，状态(M，F)就不允许，因为它表示必有女子在其丈夫不在场的情形下与其他男人在一起了．除去不允许状态后，剩下的就都称为允许状态．于是我们可以把本问题的允许状态集合S写出来：
　　S={(0，0)，(0，1)，(0，2)，(0，3)，(1，1)，(2，
　　2)，(3，3)，(3，2)，(3，1)，(3，0)，(2，1)}．
　　有了允许状态集S，还需要知道这些允许状态之间是如何变化的，特别是如何从三对夫妻全在此岸是的状态(3，3)一步步地变为三对夫妻全在彼岸的状态(0，0)的．这就需要讨论所谓运算(或决策)，它们也是由一对有序数组表示的．因为小船每次从河的一岸驶向另一岸都使状态发生变化，故我们把小船的一次运送称为一次运算(或决策)．
　　我们规定第n次运算dn由第n+1个状态Sn+1减去第n个状态Sn来确定，即
　　dn=Sn+1－Sn．
　　注意到小船由此岸驶向彼岸时，此岸人数由多变少，而船由彼岸驶回此岸时，此岸人数由少变多．又由于小船载乘人数不多于2人，故运算dn必然满足：
　　dn=(－1)n(p，q)，p，q≥0且1≤p+q≤2，n∈N，
　　其中p，q分别表示小船离岸时船上男人与女人的数量．当Sn+1，Sn均为允许状态时，称dn为允许运算，我们把方程
　　Sn+1=Sn+dn
　　称为状态转移方程．
　　至此，我们已经把问题完全抽象化了．
　　2．解法
　　我们下面的任务就是利用状态转移方程来求解．实际上是要一步一步地考虑由一个允许状态加上一个允许运算，得出另一个允许状态的过程，试图寻求一条由初始状态(3，3)转为期望状态(0，0)的路径(当然对有些问题这种路径不一定存在)，也就是要确定一系列的允许运算dn(n=1，2，…，m)，使得
　　(3，3)+d1+d2+…+dm=(0，0)．
　　由于本问题涉及的变量不多，约束条件也不多，我们可以凭简单的演算来求解．当某些问题变量较多，约束条件也较复杂时，我们可以借助计算机，以避免十分繁琐的演算．
　　下面是利用状态转移方程直接求解“夫妻过河”问题的一条路径：

　　　　
　　3．讨论
　　与“夫妻过河”类似的有“商人过河”或“传教士与野蛮人过河”的问题．其中“传教士与野蛮人过河”问题是这样叙述的：三个传教士与三个野蛮人要过河，小船最多可载二人．传教士以为只要野蛮人多于他们的人数，他们就会被害，问如何设计渡河方案．细心的读者可能会注意到，前面讨论过的“夫妻过河问题中“女子不得在其丈夫不在场时与其他男人在一起”这一条件实际上是限定了在任何情况下，女子的数量不得多于男子，这样就与“野蛮人的人数不得多于传教士的人数”相似了．于是这两个问题所抽象出来的数学模型其实是一样的，解法自然也是相同的． 　　考虑一下当问题的条件发生变化时，问题的解决会朝什么方向发展是极有意义的．很明显，夫妻数量的增加会使问题难于解答，甚至不可解(请读者考虑四对夫妻的情形)，而小船载人的数量增加(比如可载3人)将大大降低问题的难度．若小船可载4人的话，则无论多少对夫妻过河，就都不成问题了．
　　还有所谓“人狗鸡米过河”问题，也是颇有趣味的，人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人不在时，狗会吃鸡，鸡会吃米，问如何设计顺利过河方案．我们把这个问题的解答留给同学们．另外，用一定容积的若干油瓶倒油的问题也属此类问题．
　　下面给出状态转移问题的图解法：
　　当所讨论问题变量不很多时，人们也常常利用作图的方法来解决状态转移问题．例如对于“夫妻过河”问题，可以在M－F平面上标出允许状态集S中的点，而将允许运算看作是沿方格移动1格或2格，为了区别小船的往返，我们用实线表示小船由此岸至彼岸，用虚线表示小船由彼岸至此岸．于是下图就是“夫妻过河”问题的一个图解法。
　　　　
　　4．结语
　　状态转移问题一般并不一定有解存在，有解时解法又不一定唯一．当解法不唯一时，我们应该比较不同解法的优劣，从而确定出最优解法．有兴趣的同学请考虑一下“夫妻过河”问题的解法是否唯一，图解法或许对你很有帮助。