书城教材教辅中学理科课程资源-漫话数学故事
15181100000010

第10章 楚晋商人渡河

春秋战国时代,楚国和晋国连年打仗,伤亡惨重,结下了冤仇,弄得两国的人民,相互之间也都不信任了。在历次战争中,楚国失败的次数多。所以,一般晋国人都害怕楚国人要报复。

有一次,三个楚国商人和三个晋国商人一起到齐国去经商。齐国的主顾要求六个人同日到达,说是这样才好接待和拍板成交,少了任何一个都不答应。为此,他们只好结伴同行,一路上勾心斗角。

一天傍晚,他们来到了一条大河边。河水很深,他们又都不会游泳,河上也没有桥梁。幸好岸边有一只小船,可是船太小了,一次最多只能渡过两人。这六个商人,人人都会划船。为了防止发生意外,不论在河的这一岸和那一岸,或者在船上,都不允许楚国的商人数超过晋国的商人数。

请问,怎样才能把六个人全部渡过河去?

解决这个比较复杂的渡河问题,可以采用在括号里写两个数的办法,来记录河左岸人数的变化情况。在括号中的一对数,前一个表示楚国商人数,后一个表示晋国商人数。例如(2,3),就是说河的左岸有2个楚国商人,3个晋国商人。

开始时,六名商人全在左岸,采用上述记法,就是(3,3)。我们的目的是要使他们全部过河,到达右岸,所以终极目标是(0,0)。也就是说,他们全部过了河,左岸没有人了。问题是怎样才能从(3,3),逐步演变到(0,0)呢?

按规定,有些情况是不许可的。例如(3,2),说明在左岸的楚人比晋人多,这就是不许可的。于是,许可的情况只有(3,3),(2,3),(1,3),(0,3),(2,2),(1,1),(0,0),(1,0),(2,0),(3,0)这十种。至于船上的情况,因为船最多渡两人,不会发生楚人比晋人多的情形,所以不用考虑。

为了说明小船在左岸还是在右岸,我们画一条横线,横线上方的括号里的数对,表示船在左岸时的情况;横线下方的括号里的数对,表示船在右岸时的情况。

要是从甲情况可以一步演变到乙情况,当然这时由乙情况也一定可以演变回去,就在甲、乙之间连一条线。例如从上方的(3,3),可以一步变到下方的(2,3),或者(2,2)、(1,3),可以一步变到下方的(2,3),或者(2,2)、(1,3),就由(3,3)向这三个括号各画一条线。把所有与(3,3)相连的线都画出来,这就得到一张图(如图23):

把这张图翻译出来,便是:

第一步,两名楚国商人从左岸到右岸;

第二步,其中一人划船回到左岸;

第三步,回来的一人与原先留在左岸的一名楚国人一起渡河;

第四步,一名楚国人划船回来;

第五步,两名晋国人过河;

第六步,一名楚国人和一名晋国人回来;

第七步,两名晋国人过河;

第八步,一名楚国人回来;

第九步,两名楚国人过河;

第十步,一名楚国人回来;

第十一步,两名楚国人过河。至此,全部人员渡河完毕。

从图23上看出,共有四种最好的渡河办法,都是要渡11次。

明白了这个道理和办法后,你就不难解决:当楚国人和晋国人各有六人,而小船一次最多可容纳五人时,只用七步就可完成渡河。

要是不限定步数,只要小船每次最多可容纳四人,那就可以证明,任意数目的楚国商人和晋国商人,只要人数相等,都是可以渡过河去的。

这种方法,在数学里名叫状态分析图。它在人工智能等学科的研究中,有着蓬勃的生命力。