13
4商人过河问题
分析
此类智力问题当然可以通过一番思考， 拼凑出一个可行方案来。
但是，我们现在希望能找到求解这类问 题的规律性、建立数学模型，用以解决更 为广泛的问题。
2
如图所示:
例如： d1：(3,3)-----(2,2) 1个商人1个随从过对岸 d1：(3,3)-----(3,1)2个随从过对岸
12
探索
(1) 夫妻过河问题 有三对夫妻要过河，船最多可载两人。 约束条件是根据法律，任一女子不得在其
丈夫不在场的情况下与另外男子在一起，问 此时这三对夫妻能否过河? 四对夫妻呢 (2) 人、狗、鸡、米过河问题
某人要带一条狗、一只鸡、一箩米过河， 但小船除需要人划外，最多只能载一物过河， 而当人不在场时，狗要咬鸡、鸡要吃米。问 此人应如何过河?
9
思考
(1) 若船的情况不变，则2名商人2个随从 如何安全渡河？
(2) m名商人m个随从(m≥4)能否安全渡 河？
10
(1) (2,2)→(1,1) or (2,0)→(2,1)→(0,1) → (1,1)→(0,0) 如下图：
11
(2) m名商人m个随从(m≥4)无法安全渡河,如m=4 时的图(如下图)，d7就无法作不重复的转移。