摘要或動機

有一農夫帶著一隻狼、一隻羊及一個高麗菜渡河，而農夫划著小舟，一次只能載一物件。當農夫不在場時，狼會吃掉羊，羊會吃掉菜。只有農夫在場時，才不會發生上述情形。討論其最小移動次數及方法總數。

將菜、羊、狼編號為1、2、3，規定2能吃掉1，3能吃掉2，食性距離為一。其移動次數為7，方法總數為2。再將物件總數增加至n，利用合法狀態、連線數得到移動次數為7，方法總數為。另外討論平均移動次數，以了解物件編號為奇數與偶數不同的移動情形。

當了解距離為一時的移動情況後，延伸至距離大於等於二時，最後分成三個種類來討論。分別為：

（一）物件總數：n ? d+1：

走法總數：n² - n 種走法
次數：3次


（二）物件總數n=(β(d+1)+1)：


走法總數：-Y種走法

次數：5次

（三）物件總數n=(β(d+1)+R)，其中(R?{2~d}：


走法總數：-Z種走法

次數：3次