问题

一农民带着一只狼、一只羊和一棵白菜要过河，河上有一条小船。农民一次只能带三者之一上船，但狼和羊、羊和白菜不能单独在一起（至于原因，很明显吧）。请问农民要怎样把狼、羊、白菜一起带过河？

推理分析

已知条件如下：

先来分析第一步，由于只有狼和白菜可以单独共处，所以农民只能先带羊过河，然后返回。

第二步带什么过河呢？先假设带狼过河，则到达对岸的就有狼和羊了，由于它俩不能单独共处，因此农民便无法返回，问题便“无解”了。反过来假设带白菜过河，会遇到同样的问题。

如果该问题有解，而现在我们推理陷入困境，说明我们可能忽略了什么条件。

重新审视前面的推理步骤：第一步是“无懈可击”的，只能先带羊过河。第二步过河后，农民真的无法返回吗？不，农民只是不能“独自”返回，他还可以带羊返回！这样，就可以继续下去了。

为什么第二步的推理可能陷入困境呢？因为谜面诱发了人们的一种思维定势：要把东西带过河，因此运送是“单向”的——即只能带过河不能带回来。

因此，我们很可能会忽略谜面给出的第 4 个条件：运送是“双向”的，可以把东西带过河，也可以再带回来。

上面的解法是纯逻辑推理分析，其实我们可以把题目转化为数学问题来求解。

把狼、羊、白菜用 $(x, y, z)$ 表示。由于只有在此岸和对岸两个状态，所以用 0 表示此岸，用 1 表示对岸。

这样就把问题转换成了一个数学问题：现有一个边长为 1 个单位的立方体，现要求从原点 $(0, 0, 0)$ 到 $(1, 1, 1)$ 的路径。限制条件如下：

初始农民的状态值是 0；
经过立方体一条边，有且仅有一个维度的状态改变，转变到的状态值就是农民的状态值。比如从 $(0, 0, 0) \to (0, 1, 0)$，即 $y$ 值 $0 \to 1$，则农民状态值为 1；
顶点坐标如果 $x \neq y \text{ 且 } y \neq z$，则农民的状态值可任意转换（即农民独自坐船任意往返）；
顶点坐标中如 $x = y \text{ 或 } y = z$，除非农民状态值与相等的状态值相同，否则称其为一个“不可达转换”。比如 $(0, 0, 0) \to (0, 0, 1)$，农民状态值根据条件 2 可知为 1，而相邻相同的状态值为 0。因此这是一个不可达转换；
经过一条边转换，农民状态必然改变。

第一步，候选路径为 $(0, 0, 0) \to (0, 1, 0)$、$(0, 0, 0) \to (0, 0, 1)$、$(0, 0, 0) \to (1, 0, 0)$。由条件 4 可知，后二条路径为不可达转换，只能取 $(0, 0, 0) \to (0, 1, 0)$。

第二步，首先根据条件 3 将农民状态由 1 翻转为 0。此时，除来路外，另两条路径都是可选，这里我们选 $(0, 1, 0) \to (0, 1, 1)$ 来讨论。

第三步，候选路径为 $(0, 1, 1) \to (0, 0, 1)$ 和 $(0, 1, 1) \to (1, 1, 1)$。注意农民的起始状态为 1，而由条件 3 知其不能翻转，因此转变必为 $1 \to 0$。故只能选前一路径。

第四步，由于不能往回走，可选路径仅有 $(0, 0 ,1) \to (1, 0, 1)$。

第五步，翻转农民状态 $1 \to 0$，然后 $(1, 0, 1) \to (1, 1, 1)$ 结束。

完整路径为：$(0, 0, 0) \to (0, 1, 0) \to (0, 1, 1) \to (0, 0, 1) \to (1, 0, 1) \to (1, 1, 1)$。

同理可得另一路径为：$(0, 0, 0) \to (0, 1, 0) \to (1, 1, 0) \to (1, 0, 0) \to (1, 0, 1) \to (1, 1, 1)$。