商人过河四商四仆

2012高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师)研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺,严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写)： A 我们的参赛报名号为(如果赛区设置报名号的话）： J2202 所属学校（请填写完整的全名）： 江西环境工程职业学院 参赛队员 （打印并签名） :1。 杨松泉 2. 付 琪 3. 付建华 指导教师或指导教师组负责人 （打印并签名）： 教导组

日期： 2012 年 8月 9 日

赛区评阅编号(由赛区组委会评阅前进行编号）：

1

2012高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号)：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）:

全国评阅编号(由全国组委会评阅前进行编号）：

2

摘要

本文研究的是四个商人和四个仆人从河岸的一边过到河的另一边的问题,过河的工具只有一搜小船,只能同时载两个人过河，包括划船的人，由他们自己划行。针对商人安全渡河的问题,采用多步决策的过程，根据各量的空间几何关系,经过严格的数学公式推导。

分别建立两个模型：模型一采用穷举法，对各种过河的方案一一列举，然后根据商人们要安全过河为前提对各种进行了列举，经过层层筛选，最终求出商人安全的方案。模型二采用图解法，利用图示表示说明该题的解法。

最后本文就此问题进行推广，当有M名商人N名随从且小船容量为K时，将会得到几种解决方案给出了说明.

关键词:渡河问题 数学公式

3

一、 问题的提出

当今社会每个人都想当王者，谁都想成为富翁，所以就在这个问题中仆人们也想成为商人。仆人们密约，在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物,问应如何设计过河顺序才能让所有人安全地过到河的另一边。

二、模型的分析

四个商人各带一名仆人乘船渡河，一只小船最多能容纳两个人，要他们都安全到达河的对岸。这个问题可以看成一个多步决策的过程,每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员作出计算,在保证安全的前提下(两岸的商人数都比仆人多）。在有限步内使人员全部渡河，用状态（变量)表示某一岸的人员数量，决策（变量）表示船上的人员数量，可以找出状态随决策的变化规律。问题转化为在状态的允许范围内（安全条件渡河）,确定每一步决策,达到渡河的目的。

三、模型的假设

1. 小船的质量是好的.

2. 过河的途中没有突发情况。 3. 水流的速度正常。

4. 每个商人和随从都会划船 5. 随便两个人都会做同一条船

四、符号说明

符号 M 诠释 商人 商人数量 小船的容量 正常情况下,商人和随从所在河的一边的对岸 第n次，A岸的随从数 符号 N 诠释 仆人 仆人数量 正常状况下，商人和随从所在河的一边 第n次，A岸的商人数 渡河前A岸的商人和随从的人数状况 m K n A x g B y 图1 符号表示示意图

4

五、 模型的建立与求解

A B 图2 商人渡河示意图

模型一：穷举法

①假设商人数量有4个(分别为M1,M2，M3，M4），仆人数量也有4个(分

别为(N1,N2，N3，N4)，小船可容纳人数为2

②首先N1、N2先过河对岸 ③N2回来

④N2、N3过河对岸 ⑤N3回来

⑥M1、M2过河对岸

这时,河的本岸及对岸人数都是2商人2仆人，无论哪一方过河对岸，结果都是商人无法安全过河，此模型陷入无限循环之中。因此此模型无解。 模型二:坐标法

5

y仆人 x商人 图3 商人和仆人所在河岸示意图

允许步骤数L是沿方格线移动1格或2格,L为奇数时向左.下方移动，L为偶数时向右.上方移动，要确定一系列的L，使初始状态（4，4）最终变为（0，0）,无论怎样走都必须经过中间点（2,2），然后奇数次到达Y轴,，而无论怎么变化人数都也只能到达此点后不能继续走下去，只能循环走，达不到最终的目标（0，0）。

S0=（4,4） S1=(3,3） S2=(4,3） S3=（4,1） S4=（4,2） S5=(4，0） S6=（4，1)

S1=（4，2) S5=（2,2) S6=（3,3)

由流程图看出，最后陷入循环，达不到(0，0).

六、模型的评价及推广

“商人渡河”模型适合于解决很多问题，如“传教士与野蛮人渡河”，“印度夫妻渡河”等。这些问题本质上都是相同或相似的,由此可见这个趣味问题流传的广泛性.另外还有所谓“人狗鸡米过河”问题，也是颇有趣味的,人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人不在时，狗会吃鸡，鸡会吃米，问如何设计安全过河方案.我们完全可以仿照商人渡河问题建立一个多步决策模型，将上述算法稍作修改，就可以得到它的解。这里就不再赘述了。另外，用一定容积的若干油瓶倒出一定量的油的问题也属此类问题。

6

七、模型的改进

优点：多步决策不会出现遗漏可能的过河方式，可以将其全部得出来且看起来直观易懂。

缺点：模型的缺点也很明显,就是解决是复杂繁琐，且只能解决过河的人少时的过河方案，如果人多的话，这种方法显然不适合.

推广：商人过河模型适合于解决很多问题,如“和尚和尼姑过河”、“人狗鸡米过河”等。这些问题本质上市相同的或相似的，由此可见这个有趣味的问题流传的广泛性。

参考文献：

［1]全国大学生数学建模竞赛组委会，数学建模的实践：2006年全国大学生数学建模夏令营论文集，北京：高等教育出版社，2007.8

[2] 姜启源，《数学模型》，北京：高等教育教育出版社，2003.

7