背公式以及提灯过河问题的通解

在上一篇《提灯过河问题》的评论区，有读者朋友指出这个问题和“四牛过河问题”是同一个问题，并且给出了解题口诀。

四牛过河问题常见于小学奥数，以及考公复习。问题表述为：

牧童骑在牛背上赶牛过河，共有甲乙丙丁四头牛，每头牛过河分别需要a、b、c和d分钟。每次过河牧童必须骑一头牛，再最多赶一头牛。问：牧童将这四头牛全部赶过河最少需要多少时间。

这个问题的表述虽然和“提灯过河”的问题表述不同，但问题的本质是一样的，只不过提灯过河问题中的人变成了牛，灯变成了牧童。在更一般性的赶牛过河问题中，牛的头数可以是四头，也可以是五头或者更多头。

这位读者朋友给出了两个口诀，作为四牛过河和五牛过河问题的答案：

四牛过河1301，五牛过河23101。

把这个口诀翻译成白话，就是说：

如果四头牛过河所需的时间从短到长依次为a、b、c和d，那么牧童赶全部四头牛过河所需的最少时间则为1a + 3b + 0c + 1d= a + 3b + d；

如果五头牛过河所需的时间从短到长依次为a、b、c、d和e，那么牧童赶全部五头牛过河所需的最少时间则为2a + 3b + 1c + 0d + 1e = 2a + 3b + c + e。

背口诀、背公式在小学奥数套路化训练中非常常见，对于考公的成年人来说，口诀和公式更是可以节约考试时间的秘笈，他们往往只想“知其然”，对“知其所以然”没有兴趣。

比如，碰到五牛过河问题，直接用23101作为系数，分别乘以各牛过河所需时间再加起来即可得到答案。至于这五头牛该以什么方案过河，或者为什么这个答案是所需的最短时间，很少有人会去思考这个问题。

这可能是我们的数学教育中存在的一个奇怪、但不幸又很常见的现象吧。

具体到赶牛过河问题，很可惜，使用上述口诀不仅不能“知其所以然”，甚至在某些情况下还不能“知其然”。也就是说，在某些情况下按照口诀得到的答案是错误的。

我们先说结论：考虑每头牛过河所需的时间，对于某些时间组合，将用时最长的两头牛或者多头牛两两结伴过河是最优选择；而对于另外一些时间组合，牧童始终骑在用时最短的那头牛上过河，需要的总时间反而更短。

以《提灯过河问题》一文中的几个时间为例，在组合一中，如果四头牛过河分别需要1、2、5和8分钟，那么口诀“1301”有效，即总需时等于1 + 6 + 8 = 15分钟。具体的过河方案为：

甲乙牛过河用时2分钟，牧童骑甲牛回来用时1分钟，丙丁牛过河用时8分钟，牧童骑乙牛回来用时2分钟，最后甲乙牛再次过河用时2分钟。5次过河共用时 2 + 1 + 8 + 2 + 2 = 15分钟。其中，第二次过河的甲牛和第四次过河的乙牛可以互换，结果不变。

现在考虑组合二：如果四头牛过河分别需要1、4、5和8分钟，那么根据口诀“1301”，总需时等于1 + 12 + 8 = 21分钟；而牧童如果始终使用甲牛过河，根据以下方案，则只需要17分钟：

甲乙牛过河用时2分钟，牧童骑甲牛回来用时1分钟，甲丙牛过河用时5分钟，牧童骑甲牛回来用时1分钟，最后甲丁牛过河用时8分钟。5次过河共用时 2 + 1 + 5 + 1 + 8 = 17分钟。

由此可见，对于四头牛分别需要1、4、5和8分钟的组合，口诀失灵，因为四牛过河所需的最短时间不会超过17分钟。

我们仔细比较一下两种方案，可以发现两个方案的最大区别在于丙牛的过河方式。

1 如果丙牛和丁牛结伴过河，那么丙牛过河的时间c不会被计入，取而代之的条件是河对岸需要预留一头牛，使得牧童可以骑回来。这样，在丙丁牛过河之前，牧童必须将某头预留牛X赶到河对岸，然后再骑一头牛Y回到河这边；在丙丁牛过河之后，牧童再骑上预留牛X回到河这边。

因此，除了丙丁牛过河这一次，牧童需要额外过河三次，所需时间为牛X和牛Y结伴一次，以及牛X和牛Y单独各一次。显然，使用甲牛和乙牛担任牛X和牛Y的任务用时最少，这样四次过河共需时间b + b + d + a = a + 2b + d。

2 如果丙牛和丁牛分别和甲牛结伴过河，那么丙牛过河的时间c将被计入。方案为：甲丙牛过河，牧童骑甲牛回来，甲丁牛过河，牧童骑甲牛回来。

这个方案也由四次过河组成，四次过河共需时间c + a + d + a = 2a + c + d。

比较两种方案的时间计算公式，决定孰大孰小的决定性因素为2b和a + c的大小。如果2b< a + c，例如组合一，4 < 1 + 5，那么就应该采用丙丁牛结伴过河的方案；如果2b > a + c，例如组合二，8 > 1 + 5，那么就应该采用丙丁牛分别和甲牛结伴过河的方案。

进一步，我们可以把上述判别应用到n头牛过河的一般情况，n≥ 4。两牛和三牛过河的情况比较简单，不存在不同组合的情况，这里不再赘述。

牧童赶n头牛O₁, O₂, …, O_n过河，每头牛过河所需时间分别为t₁ ≤ t₂ ≤ … ≤ t_n。

从牧童始终骑O₁过河的方案出发，即其他牛分别和O₁结伴过河。具体的步骤为：

“O₁O₂过河，牧童骑O₁回来，O₁O₃过河，牧童骑O₁回来，……，O₁O_{n – 1}过河，牧童骑O₁回来，O₁O_n过河”

该方案一共过河(n – 1) + (n – 2) = 2n – 3次，其中，(n – 1)次两头牛去往河对岸，(n – 2)次牧童骑O₁回来。因此，该方案所需的总时间为：

t₂ + t₁ + t₃ + t₁ + … + t_{n – 1} + t₁ + t_n= (n – 2)t₁ + t₂ + ∑t_i, 3 ≤ i ≤ n

然后，比较2t₂和t₁ + t_{n – 1}的大小。

如果2t₂ ≥ t₁ + t_{n – 1}，那么目前方案已经是最优方案。

如果2t₂ < t₁ + t_{n – 1}，那么将上面方案中的最后4次过河

“牧童骑O₁回来，O₁O_{n – 1}过河，牧童骑O₁回来，O₁O_n过河”

改为：

“O₁O₂过河，牧童骑O₁回来，O_{n – 1}O_n过河，牧童骑O₂回来”

并将它们放在整个方案的最前面：

“O₁O₂过河，牧童骑O₁回来，O_{n – 1}O_n过河，牧童骑O₂回来，O₁O₂过河，牧童骑O₁回来，O₁O₃过河，牧童骑O₁回来，……，O₁O_{n – 3}过河，牧童骑O₁回来，O₁O_{n – 2}过河”

这样，新方案所需的总时间为：

t₂ + t₁ + t_n + t₂ + t₃ + t₁ + … + t_{n – 2} = (n – 3)t₁ + 3t₂ + ∑t_i + t_n, 3 ≤ i ≤ n – 2

继续比较2t₂和t₁ + t_{n – 3}的大小。

如果2t₂ ≥ t₁ + t_{n – 3}，那么目前方案已经是最优方案。

如果2t₂ < t₁ + t_{n – 3}，那么类似地，将目前方案中的最后4次过河

“牧童骑O₁回来，O₁O_{n – 3}过河，牧童骑O₁回来，O₁O_{n – 2}过河”

改为：

“O₁O₂过河，牧童骑O₁回来，O_{n – 3}O_{n – 2}过河，牧童骑O₂回来”

并将它们放在目前方案的最前面：

“O₁O₂过河，牧童骑O₁回来，O_{n – 3}O_{n – 2}过河，牧童骑O₂回来，O₁O₂过河，牧童骑O₁回来，O_{n – 1}O_n过河，牧童骑O₂回来，O₁O₂过河，牧童骑O₁回来，O₁O₃过河，牧童骑O₁回来，……，O₁O_{n – 5}过河，牧童骑O₁回来，O₁O_{n – 4}过河”

这样，新方案所需的总时间为：

t₂ + t₁ + t_n + t₂ + t₃ + t₁ + … + t_{n – 2} = (n – 4)t₁ + 5t₂ + ∑t_i + t_{n – 2} + t_n, 3 ≤ i ≤ n– 4

如此继续比较，直到某个k满足2t₂ ≥ t₁ + t_{n – 2k + 1}，或者k ≥ (n – 1)/2，那么目前方案已经是最优方案。

简单来说，我们可以先设定一个阈值t_T，令t_T = 2t₂ – t₁。

对于1 ≤ k < (n – 1)/2，如果t_{n – 2k + 1} > 2t₂ – t₁，那么就在方案中安排O_{n – 2k + 1}和O_{n – 2k + 2}结伴过河；否则安排O_{n – 2k + 1}和O_{n – 2k + 2}分别和O₁结伴过河。

假设按照上述判别共有m对非O₁牛结伴过河，那么所需的总时间最短为：

以五牛过河为例。

如果五头牛过河所需时间分别为1, 2, 6, 7, 8分钟，因为4 < 1 + 7，所以O₄和O₅结伴过河，m = 1，这样所需总时间为2t₁ + 3t₂ + t₃ + t₅ = 22，即口诀23101。

如果五头牛过河所需时间分别为1, 5, 6, 7, 8分钟，因为10 > 1 + 7，所以O₄和O₅分别和O₁结伴过河，m = 0，这样所需总时间为3t₁ + t₂ + t₃ + t₄ + t₅= 29。

如果是六牛过河问题，那么就可能存在三种方案。

例如，六头牛过河所需时间分别为1, 2, 6, 7, 8, 9分钟，因为4 < 1 + 8，且4 < 1 + 6，所以O₅和O₆结伴过河，O₃和O₄结伴过河，m = 2，这样所需总时间为2t₁ + 5t₂ + t₄ + t₆ = 28。

又如，六头牛过河所需时间分别为1, 4, 6, 7, 8, 9分钟，因为8 < 1 + 8，但8 > 1 + 6，所以O₅和O₆结伴过河，O₃和O₄分别和O₁结伴过河，m = 1，这样所需总时间为3t₁ + 3t₂ + t₃ + t₄ + t₆= 37。

再如，六头牛过河所需时间分别为1, 5, 6, 7, 8, 9分钟，因为10 > 1 + 8，所以O₅和O₆分别和O₁结伴过河，O₃和O₄分别和O₁结伴过河，m = 0，这样所需总时间为4t₁ + t₂ + t₃ + t₄ + t₅+ t₆ = 39。

往期精彩文章：

数学科普：

• 2024年中国数学会三大数学奖揭晓
  

• 提灯过河问题
  

• 奶酪和黄油
  

• 来一道古早的轮换对称题
  

• 共顶点的正多边形

数学竞赛：

• 2024阿里巴巴全球数学竞赛获奖名单及情况说明
  

• 第四届丘成桐女子中学生数学竞赛试题及解答
  

• 2025 年台湾女子数学奥林匹亚培训班名单
  

• 6名华裔女生并列第一，EGMO冠军屈居第七
  

• 第四届丘成桐女子中学生数学竞赛于9月30开启报名

数学教育：

• 从丘成桐女子竞赛到江苏竞赛成绩引发的思考
  

• 刷题VS不刷题，这是个好问题
  

• 与牛顿擦肩而过：一个偶然的故事
  

• 热爱和坚持，比天赋更为重要
  

• Part III 我们这一年的读书和申博

数学文化：

• 75周年国庆趣题
  

• 中秋节快乐！
  

• 低地国家的达芬奇
  

• 2025年第66届IMO宣传片内容解析
  

• 罗巴切夫斯基几何——数学史上最伟大的杰作（之一），人类思想的里程碑

敬请关注“唯思客俱乐部”，分享、点赞、在看我们的文章：