经典智力题推广——过桥问题(一)

经典智力题推广经典智力题推广 过桥问题 一 过桥问题 一 一 问题一 问题 在漆黑的夜里 四位旅行者来到了一座狭窄而且没有护栏的桥边 如果不借助手电筒 的话 大家是无论如何也不敢过桥去的 不幸的是 四个人一共只带了一只手电筒 而桥 窄得只够让两个人同时过 如果各自单独过桥的话 四人所需要的时间分别是1 2 5 8 分钟 而如果两人同时过桥 所需要的时间就是走得比较慢的那个人单独行动时所需的时 间 问题是 如何设计一个方案 让这四人尽快过桥 假设这四人分别为 A B C D 很明显 开始两人拿着手电筒过桥后 手电筒就在 桥的另一边了 此时需要已经过桥的那两人中的一个再把手电筒送回桥这边 送手电筒回 来过桥也要化时间 所以要选一个跑得比较快的 一个很自然的想法就是 每次让跑得最 快的 A 陪着另一个过桥 然后 A 快速地跑回来 再陪下一位过去 最后所有人就都可以过 桥了 让我们来算一下这要多长时间 为了方便起见 我们把旅行者出发的桥的这一边称为 此岸 而把旅行者想要到达的那边叫 彼岸 在表达一个过桥方案时 我们用 来表 示从彼岸到此岸的移动 用 表示从此岸到彼岸的移动 前面 A 护送大家过河 的方案 就可以写成 右边数字为完成此步骤所需时间 A B 2 A 1 A C 5 A 1 A D 8 一共就是2 1 5 1 8 17分钟 但其实有更快的办法 A B 2 A 1 C D 8 B 2 A B 2 一共是2 1 8 2 2 15分钟 这个办法的聪明之处在于让两个走得最慢的人同时过桥 这样 花去的时间只是走得最慢的那个人花的时间 而走得次慢的那位就不用另花时间过桥了 可以把所有可能的方案都列举一遍 就会发现这是最快的方案了 现在我们把这个问题推广到 N N 4 个人过桥的情况 如果有 N 个旅行者 假设他们 有各自所需的过桥时间 正实数 在只有一只手电筒的情况下 要过上述的一条桥 怎样 才能找到最快的过桥方案 假设最快地把 N 个旅行者从此岸移动到彼岸需要 f 分钟时间 那么我们把所有在 f 分 钟时间内把 N 个旅行者从此岸移动到彼岸的方案称为 最佳方案 最佳方案很有可能不止 一个 我们的目的是要找到一个最佳方案 但是并不需要把所有的最佳方案全都找出来 二 一个合理的假设二 一个合理的假设 为了讨论的方便起见 这一节我们要说明的是 事实上我们可以假设每个旅行者的速 度都是不一样的 这样当我们说一些人中 最快的那个 次慢的那一个 时 都不会有歧义 了 因为每个人的速度都是独一无二的 这个假设在讨论中并非必要 只是为了在证明的 叙述过程中避免不断地啰嗦类似 我们让两人中最快的那个过桥 如果两人一样快 那就随 便选一人 我们选在彼岸最快的那个人回来 如果上一步刚从此岸到彼岸的人中 其中有 一个是现在彼岸走得最快的之一 我们就特别选择让他回来 之类的话 为什么我们可以假设每个旅行者的速度都是不一样的 原理就在于 我们可以把原来 过桥时间相同的旅行者的过桥时间分别加上一个不同的但是非常非常小的量 这样就能保 证旅行者的速度是不一样的了 但是因为加上去的量都非常小 所以对最终总的过桥时间 的影响也非常小 所以这样改动过后得到的最佳方案在原来的条件下实施的话 也该是原 来条件下的最佳方案 如果你对上面的说明满意了 就完全可以跳过这一节直接看第三节 这一节后面啰哩 叭嗦的都是为了向一些对严格性要求比较高的朋友解释上面所说的方法的确可行 首先对于任何一组 N 个旅行者 假定他们过桥所需的时间分别为 a1 a2 aN 它们都是大于零的实数 假设这个序列已经从小到大排列了 当然不排除其中有数相等 每次都由第一个旅行者陪同一个人过桥 然后第一个旅行者回来 这样一个方案所需要的 时间是 S N 2 a1 a2 an 第一个旅行者要返回 N 2次 所以最佳方案所需要的时间一定不会比 S 大 我们把一个过桥方案中让一个或者两个人拿着手电筒从桥的一边走到另一边的一次移 动叫做这个方案中的一次移动或者 一步 就是前面解四个人的题中使用 或 来表 示的一个步骤 因为一次移动所需要的最少的时间是 a1分钟 所以最佳方案中所需的移动 步数一定不会多于 K S a1 步 这里 是取整运算 让我们考虑一下所有在 K 步以内完成的方案 上面的例子表明这样的方案至少有一个 而且这样的方案显然只有有限多个 假设一共有 M 个 我们又设这些方案执行时要花的时 间是 t1 t2 tM 我们还可以假设上面这些时间已经从小到大排列了 t1就是最佳方案所需要的时间 现在是关键的步骤 我们要选取一个很小的正实数 0 它有多小呢 它必须满足下 面的条件 1 对于任何两个过桥时间不同的旅行者 假设他们的过桥时间是 a 和 b 分钟 必须满足 a b N 换句话说 N 要小于不同的旅行者过桥时间之间的差别 2 对于任何两个所需的完成时间不同的 K 步以内的方案 假设它们的所需时间是 t 和 s 分 钟 必须满足 t s K 换句话说 K 要小于不同的方案完成时间之间的差别 因为旅行者的数目和方案的数目都是有限的 所以我们必然可以选取这样一个 至于这 两个条件有什么用 我们马上就可以看到 假设若干个旅行者过桥的时间都是一样的 a 分钟 我们就把题目改一下 使得他们的 过桥时间分别为 a a N a 2 N a 3 N 如果有其他的旅行者过桥时间相互一样 也按照同样方式修改题目 这时在修改后的题目 中 如果原来两个旅行者所需的过桥时间相同 那么现在就变得不同 差一个非常小的量 不会超过 如果原来两个旅行者所需的过桥时间不同 那么根据上面的条件1 现在 还是不同 而且原来谁比较快 现在仍旧是他比较快 我们看看这个修改后的题目的最佳方案和原来的题目的最佳方案有什么联系 假设我们已经有一个关于修改后的题目的最佳方案 那么它所需要的时间必定是这个 模样的 a b 我们知道 b 部分是修改时把旅行者过桥时间 微调 了以后造成的 而且每走一步这部分的 改变不会超过 所以我们有0 b K S a1 如果我们把这个最佳移动方案照搬到原来的题目中去 所需要的时间就是 a 分钟 这 个方案应该同样是原来题目中的最佳方案 否则的话 假设我们有另一个方案 所需时间 为 a 而且 a a 根据上面取 时候的条件2 我们有 a a K 把这个耗时 a 的方案搬到改动过的题目里去的话 所需的时间就会是 a b 其中0 b K 所以根据 a a K a b a b 这就和 a b 是改动后题目的最佳方案所需的时间矛盾了 所以只要找到一个修改过的题目中的最佳方案 我们就得到了原来题目中的一个最佳 方案 于是我们只要考虑所有旅行者的速度都不同的题目就可以了 三 一个三 一个 很显然很显然 的结论的结论 编个计算机程序 把所有步数少于上一节中所计算的 K S a1 的可能的过桥方案都列 举一遍 然后找出最快的 当然是一种方法 这理论上也是可行的 因为少于 K 步的方案 只有有限多个 计算机程序必定能够将它们全部列举出来 只是当人数 N 增大时 过桥方 案数会增加得很快 事实上 如果我们只考虑 每次过去两个人 然后这两个人中其中一个 人回来 这类方案的数目的数量就已经远远超过 N 个了 想像一下如果 N 1000的话所需要 的计算量 况且还有更多数量的其他类型方案 特别是 我们是在做智力题 不是在学编 程 当然你还可以说 如果人多的话 所需要的时间超过了12小时 那时天已经亮了 不 再需要手电筒 大家可以直接过桥 唉 我们是在做智力题 不是在做抬杠式的脑筋急 转弯 我们可以假设是在有漫长极夜的极地嘛 要不然 这桥是在一个黑暗山洞里 就 象电影 指环王 中的那样 但是如果不用列举法的话 我们有一个重要的任务要做 就是不仅要说明如何找到一 个我们自以为最快的方案 而且还要证明这样的方法的确给出了一个最佳方案 在我们的直觉当中 最快的方案必然有这样一个特征 每次过桥去彼岸的一定是两个 人 然后一定只有一个人把手电筒送回此岸 当然要除去最后一次过桥的情况 那时就不 需有人把手电筒送回来了 但是为什么一定是这样的呢 为什么不可能有一个意想不到的 巧妙方案 在那里有某一步居然需要一个人单独过到彼岸去 或者需要有两个人把手电筒 送回此岸来 这是个看起来很显而易见但是我们不能支吾不回答的问题 在讨论中我们经常需要说明 在某一时刻 桥的两边分别有哪些人 手电筒又在哪一 边 这样的说明称为一个 局面局面 当然 一个局面必须是合理的 比如说 不能够所有人 都在桥的一边 而手电筒却在桥的另一边 一个人必须处在桥的某一边 而且只能处在桥 的某一边 比如说 在四个旅行者的问题里 如果某一个时刻 A B 和 C 在此岸 而 D 在彼岸 手电筒也在彼岸 这就给出了一个局面 这个局面看起来有点奇怪 大概是 D 拿着手电筒 一个人跑过桥去了 接下去除了他再拿着手电筒回来别无它法 所有人和手电筒都在此岸 就是一个特殊的局面 叫作初始局面初始局面 而所有人和手电筒都在彼岸 也是一个特殊的局面 叫完结局面完结局面 所有其他的局面我们称为中间局面中间局面 想像一下现在有两种局面 在两种局面中 手电筒都在桥的同一边 都在此岸或都在 彼岸 而且在第一种局面里所有在彼岸的旅行者 在第二种局面里也都在彼岸 而且有这 样的旅行者 在第一种局面中他在此岸 而第二种局面中他在彼岸 那么我们就说第二种 局面 优于优于 第一种局面 比如说 在四个旅行者的问题里 第一种局面是 A B 和 C 在此岸 而 D 在彼岸 手 电筒也在彼岸 第二种局面是 A 和 B 在此岸 C 和 D 在彼岸 手电筒也在彼岸 那么第二 种局面就优于第一种局面 很显然 除了初始局面以外 所有手电筒在此岸的局面都优于 初始局面 除了完结局面本身外 完结局面要优于所有手电筒在彼岸的局面 但是要注意 的是 并不是任意给两个局面都能比较哪个优于哪个 比如说初始局面和完结局面 谁都 不优于谁 如果现在有两个局面 第二种局面要优于第一种局面 假设现在我已经有了一个方案 从第一种局面开始 通过符合题目要求的方法来移动旅行者 最多只能同时移动两个旅行 者 手电筒必须和他们一起移动 在 t 分钟内能够使所有旅行者到达彼岸 也就是说转变 成完结局面 或者说 解决 了这种局面 那么我们可以保证我们同样也有了一个方案 从 第二种局面开始 在不多于 t 分钟内使它转变成完结局面 为什么呢 假设第一种局面的方案中的第一步是要把某个 或某两个 旅行者从此岸移动到彼岸 这时手电筒开始一定在此岸 1 如果被移动的这个 或这两个 旅行者 在第二种局面里也在此岸 那么我们同样把他 们从此岸移动到彼岸 这时两个局面化了同样多的时间转化成另两个局面 而且仍旧是第 二种局面优于第一种局面 严格说来应该是 从第二种局面演化来的局面要优于从第一种 局面演化来的局面 不过这样也太拗口了 所以在下面我都用前面那种虽然不严格但是比 较简明的方法来叙述 2 如果被移动的有两个旅行者 但是只有一个在第二种局面里是在此岸 那么我们把他从 此岸移动到彼岸 如果这个旅行者是两个中跑得比较快的 那么这一步所化时间会比第一 种局面要少 如果他是跑得比较慢的那个 那么这一步所化时间就和第一种局面一样 而 且经过这一步转化后 第二种局面或者和第一种局面一样 或者仍旧优于第一种局面 3 如果被移动旅行者都不在此岸 那么情况要稍微复杂点 如果在第一种局面中经过这步 移动后就变为完结局面 那么这意味着第二种局面中所有人早已到达彼岸 而这是不可能 的 此时第二种局面中手电筒不可能在此岸 所以在第一种局面中经过这步移动后 还会 有接下去的一步 把某个 或某两个 旅行者从彼岸移动到此岸 我们很容易看到 第二 种局面无需任何耗费时间的移动 要优于第一种局面经过两次移动后演变得到的结果 因 为经过两步移动后 第一种局面里在彼岸多出来的旅行者 在第二种局面里早已都在彼岸 假设第一种局面的方案中的第一步是要把某个 或某两个 旅行者从彼岸移动到此岸 这时手电筒开始一定在彼岸 那么这就很简单 在第二种局面里这个 或这两个 旅行 者一定也在彼岸 所以我们用相同的一步移动 花费一样的时间 把这个 或这两个 旅 行者移动到此岸 这样得到的结果还是第二种局面要优于第一种局面 于是总而言之 无论第一种局面中采取什么样的移动 我们总可以采取花费同样多的 时间 甚至更少或者根本不花费时间 的移动 使得第二种局面或者变为和第一种局面相 同 或者仍旧优于第一种局面 于是当第一种局面演变为完结局面时 第二种局面也一定 演变为完结局面了 而花费的时间不会多于第一种局面所需的时间 于是我们得到了很显然的结论 结论一 如果有两种局面 第二种局面优于第一种局面 那么我们总可以用少于解决第一 种局面的时间来解决第二种局面 这说明 优于 这个词的使用是合理的 四 更多的结论四 更多的结论 通过结论一我们立刻得到 结论二 一定有这样一种最佳方案 在这个方案里 所有从彼岸到此岸的移动只需一个人 如果最佳方案中有一步中需要两个人从彼岸移动到此岸 那么我们可以把这一步改为 只移动比较快的那个人 在这一步后 我们花费了最多和原来相同的时间 得到的局面却 优于按原先方案执行完这一步后的局面 所以剩下的解决步骤不会比原方案花费更多的时 间 所以必定是个最佳方案 现在我们知道 我们可以要求在最佳方案中 每次只回来一个人 在下面我们要得出 另一个结论 结论三 一定有这样一种符合结论二的最佳方案 在这个方案里 所有从彼岸到此岸的移 动中 回来的这个人一定是当时在彼岸所有人中速度最快的 假设在所有满足结论二的最佳方案中 都没有符合结论三的方案 也就是说 任何一 个最佳方案中 总有某一步从彼岸到此岸的移动中 回来的那个人不是当时在彼岸所有人 中速度最快的 那么我们在这些最佳方案中选取一个这样的 坏 步骤最晚出现的方案 假 设这个步骤首先出现在第 n 步 我们特别假设在这第 n 步中回来的这个人是 B 他的过桥所需的时间为 b 分钟 而当 时在彼岸所有人中速度最快的是 A 他的过桥所需的时间为 a 分钟 现在我们开始把第 n 步 让 B 回来 改为 让 A 回来 原来的方案 修改后的方案 第 n 步 B A 现在两种局面的唯一区别在于 前一种是 A 在彼岸 B 在此岸 而后一种是 B 在彼岸 A 在 此岸 但是前一种局面要比后一种局面多耗时 b a 分钟 在第 n 步后面接下去的移动步骤中 只要不牵涉 A 或 B 那么可以在原来方案中进行 的移动仍旧可以在改变了的方案中进行 而第 n 步后第一次牵涉到 A 或 B 的在原方案中的 行动 我们假设它是第 n i 步 只能是 1 把 A 从彼岸移动到此岸 此时我们在改造方案中的移动就是 把 B 从彼岸移动到此岸 这时局面就变成和原来的完全一样了 上一次由于用 A 来换 B 节省的 b a 分钟也在这步中 耗费掉了 接下去我们使用原方案完成其他移动 所以改造后的方案同样是个最佳方案 原来的方案 修改后的方案 第 n 步 B A 第 n i 步 A B 省略号部分表示此部分两个方案相同 2 把 B 从此岸移动到彼岸 可能还有另一个过桥时间为 c 分钟的 C 和他一起移动 这就 比较简单 第 n i 步我们在改造后的方案中还是用 A 来代替 B 然后局面就恢复到原来的 情况 接下去我们使用原方案完成其他移动 原来的方案 修改后的方案 第 n 步 B A 第 n i 步 B C A C 这里括号内的 C 表示有可能另有旅行者 C 同行 省略号部分表示此部分两个方案相同 但 我们发现这个移动所花费的时间一定要比原来的少 第 n 步修改后的方案就已经要比原方 案耗时少 而第 n i 步中 如果 c 比 a 和 b 都大的话 修改后的方案和原方案耗时相同 否则的话修改后的方案照样比原方案耗时少 所以我们得到了一个比 最佳方案 还要 佳 的方案 所以这种情况其实是不会发生的 现在我们得到了一个修改过的方案 它仍旧是个最佳方案 虽然我们并不能保证它是 满足结论三的方案 但是这并不是关键 关键在于它一直到第 n 步还是满足结论三的要 求 这就和我们开始的假设 即被选取的这个方案是 这样的步骤最晚出现的方案 矛盾 所以我们的原先 假设在所有满足结论二的最佳方案中 都没有符合结论三的方案 是错误 的 这样我们就得到了结论三 在这里我要插一句题外话 上面的推理方法在数学中被称为 变分方法 这是最重要 的数学方法中的一种 我们可以在所有的数学分支中看见它的应用 它一般被用来证明存 在一个具有某种特点的对象 首先我们选取一个使得某个特征 或者函数 达到最大或者 最小的对象 然后用反证法证明这样的对象就是我们要找的对象 我们假设如果它不是我 们要找的对象 那么我们总是还能把这个对象修改 使得这个特征 或者函数 更大或更 小 这就和原来最大或最小的假设矛盾 下面我们会不断地用到这种方法来得出许多结论 一定存在某一个最佳解法 符合如 此这般的性质 一旦我们知道有一个最佳解法满足一些非常具体的性质以后 这个解法也 就很容易被具体写出来了 根据结论三我们立刻推出 结论四 一定有这样一种符合结论二 三的最佳方案 在这个方案里 每当出现手电筒在 此岸的局面时 速度最快的那个人总是在此岸 如果是初始局面 所有人都在此岸 当然没什么好说的 如果是手电筒在此岸的中间 局面 那么根据结论三 前一步有一个彼岸最快的人刚过来 如果这个人不是所有人中最 快的 那么说明最快的原来就已经在此岸了 如果这个人是所有人中最快的 那么他刚刚 过来 现在也已经在此岸了 所以结论四成立 如果在符合结论四的最佳方案方案中 有一步是只有一个人 B 从此岸走到彼岸 我们 会有什么推论 如果在此岸另有一个 A 他的速度比 B 快 那么 A 完全可以跟着 B 一起到 彼岸去 这样就在耗费相同时间的情况下 得到了一个优于原先局面的局面 根据结论一 这也是最佳方案 如果 B 是此岸最快的 根据结论四 他也是所有人中最快的 过到彼岸 后 根据结论三 他马上一个人又要回来 这就使这两步移动毫无意义 徒费时间 所以 我们得到 结论五 一定有这样一种符合结论二 四的最佳方案 在这个方案里 所有从此岸到彼岸 的移动都需两个人 下面我们要给出一个不那么显然的结论 结论六 一定有这样一种符合结论二 五的最佳方案 在这个方案里 每次从此岸到彼岸 移动两人 要么这两人里有一个是所有人中最快的那个 要么这两人到达彼岸后都再也不 回来 上面这个结论的意思是 在这个方案里不会出现这样的情况 有一步两个人跑到彼岸 去 但两人都不是跑得最快的 但是后来其中一个 或者两个都 又跑回此岸来 仍旧使用变分法 假设在所有满足结论二 五的最佳方案中 都没有符合结论六的方 案 也就是说 其中的每个最佳方案 总都有某一步从此岸到彼岸的移动中 被移动的那 两个人没有一个是最快的 而且其中一个在后面的步骤中又回到此岸来 那么我们在这些 最佳方案中选取一个这样的步骤最晚出现的方案 假设这个步骤首先出现在第 n 步 我们假设在这第 n 步中过去的两个人是 Y 和 Z 他们过桥所需时间分别是 y 和 z 分钟 而在后面的第 n i 步中 Y 又回到此岸来了 设 A 是走得最快的那个人 过桥所需时间为 a 分钟 由结论四知道 他当时一定同 Y 和 Z 一起在此岸 现在我们开始修改这个方案 把第 n 步 让 Y 和 Z 过去 改为 让 A 和 Z 过去 原来的方案 修改后的方案 第 n 步 Y Z A Z 如果 y z 那么改过的步骤消耗的时间和原来的一样 如果 z y 那么修改后的步骤消耗 的时间还会更少 现在两种局面的唯一区别在于 前一种是 A 在此岸 Y 在彼岸 而后一种 恰好相反 而且我们看到 经过这样修改的第 n 步现在符合 两人里有一个是所有人中最快 的那个 这个结论六中的要求 剩下的工作就是要理顺后面的步骤 使得修改过的方案仍旧 是一个最佳方案 那时我们就用变分法推出了矛盾 从而证明结论六 下面我们的技 巧和前面所用过的略微不同 我们要修改的不是一个移动而是一串移动 假设原来的第 n 1步是 让 Y1回来 其中 Y1是在彼岸的某人 他是在彼岸最快的 我们把这第 n 1步改为 让 A 回来 原来的方案 修改后的方案 第 n 步 Y Z A Z 第 n 1步 Y1 A 这样修改后的步骤消耗的时间少于原先方案 因为 Y1必定跑得比 A 慢 如果 Y1恰好就是 Y 自己 也就是说 i 1 那么从这步以后修改前后两种情况的局面又恢复成一样了 如果 i 1 也就是说 Y1和 Y 不同 那么执行第 n 1步后 原先的局面和修改过后的局面的唯一 差别在于前一种是 Y1在此岸 Y 在彼岸 而后一种恰好相反 我们注意到 根据结论三 Y1一定走得比 Y 快 更一般地 任何一个在 n 1步到 n i 步之间从彼岸回此岸来的人都比 Y 要走得快 如果原先方案中从 n 2步一直到 n i 步里的移动都不牵涉到 Y1 那么我们只要把第 n i 步的 Y 回来 改成 Y1回来 就理顺了所有的步骤 原来的方案 修改后的方案 第 n 步 Y Z A Z 第 n 1步 Y1 A 第 n i 步 Y Y1 修改后的步骤消耗的时间少于原先所需的 因为 Y1走得比 Y 快 如果不幸地在原先方案中的第 n j 步 j i Y1又要和某个人 M 一起到彼岸去 而第 n j 1步是 Y2回此岸来 那么我们把第 n j 步改为 A 和 M 一起到彼岸 去 而把第 n k 1 步改为 A 回此岸来 原来的方案 修改后的方案 第 n 步 Y Z A Z 第 n 1步 Y1 A 第 n j 步 Y1 M A M 第 n j 1步 Y2 A 这样修改后的步骤消耗的时间也要比原先的少 因为 A 是最快的 如果 Y2恰好就是 Y 自 己 也就是说 m k 1 那么从这步以后修改前后两种情况的局面就恢复成一样了 如果 m k 1 也就是说 Y2和 Y 不同 那么执行第 n k 1步后 原先的局面和修改过后的局面的 唯一差别在于前一种是 Y2在此岸 Y 在彼岸 而后一种恰好相反 这样我们有一个序列 Y1 Y2 依次修改下去 每次修改后的步骤消耗的时间 不会多于原先所需的 经过最多 m 2 次修改 总会有一刻某个 Yt 和 Y 相同 结束我们的 这串修改 这样我们就得到了修改后的最佳方案 它的第 n 步也是符合结论六的要求的 所以和 我们的反证假设矛盾 和结论三的证明方式相同 我们证明了结论六 在本节的结尾我们给出一个不那么显然的结论三的加强版 结论七 一定有这样一种符合结论二 六的最佳方案 在这个方案里 所有从彼岸到此岸 的移动中 回来的这个人一定是当时在彼岸所有人中速度最快的 而且他只能是所有人中 最快的或者次快的 换句话说 所有返回此岸的任务都可以只由跑得最快和跑得次快的人来担当 所有其 他人一旦到达彼岸 就留在那里 再也不回来 我们还是使用变分法 假设结论七是错的 所有 满足结论二 六的 最佳方案中 都必须至少有一次需要一个跑得不是最快或次快的人回来 那么我们选取一个这样的事情 发生得最晚的最佳方案 假设在第 n 步 有一个 C 从彼岸跑回了此岸 但他不是跑得最快 或次快的人 我们假设 A 是跑得最快的人 他所需过桥时间为 a 分钟 B 是跑得次快的人 他需要 b 分钟 而 C 需要 c 分钟 我们有 a b c 因为在第 n 步 C 从彼岸跑回了此岸 所以在 那之前一定有一步 C 从此岸到达彼岸 而且根据结论六 那一步一定是 A 和 C 同行 我 们假设此步为第 n i 步 又根据结论三 接下去一步是 A 回到此岸 在第 n i 步和第 n 步间 没有有关于 C 的移动 考虑第 n 1步 根据结论五 这一步必定有两人从此岸移动到彼岸 这两人中没有 A 或 B 否则根据结论三 第 n 步回此岸来的就该是比较快的 A 或 B 另外 这两人中也没有 C 因为在在第 n i 步和第 n 步间 C 不移动 所以我们根据上面的分析可以写出方案中的有关步骤 原来的方案 第 n i 步 A C 第 n i 1步 A 第 n 1步 Y Z Y 和 Z 未知 但非 A B 或 C 第 n 步 C 因为第 n i 步和第 n 步之间没有关于 C 的移动 而第 n 1步时 A 和 B 一定在此岸 否则根 据结论三 第 n 步回此岸来的就该是比较快的 A 或 B 所以我们可以把第 n i 步和第 n i 1步移到第 n 1步前 方案仍旧可以合理进行 换句话说 第 n i 和第 n i 1步的唯一作用 就是把 C 运送到了彼岸 但是直到第 n 步之前这个 C 并不起什么作用 所以我们可以把这 次运送搬到第 n 1步前而不影响其他步骤 修改后的方案 原来第 n i 步前的步骤 原来处于第 n i 1和第 n 步间的步骤 第 n 3步 A C 原来第 n i 步 第 n 2步 A 原来第 n i 1步 第 n 1步 Y Z Y 和 Z 未知 但非 A B 或 C 第 n 步 C 现在有问题的步骤都聚在了一起 所以我们可以用 B 来代替 C 进一步修改方案 进一步修改后的方案 原来第 n i 步前的步骤 原来处于第 n i 1和第 n 步间的步骤 第 n 3步 A B 第 n 2步 A 第 n 1步 Y Z Y 和 Z 未知 但非 A B 或 C 第 n 步 B 这个修改是可行的 因为根据上面的分析 进行第 n 3步前 B 在此岸 这样得到的方案不 但直到第 n 步还符合结论七 而且所需要的时间也比原方案短 明显违反了假设 所以我 们得到矛盾 也就是说 满足结论七的最佳方案是存在的 于是结论七成立 五 过桥的模式五 过桥的模式 结论七是非常强大的 事实上它描述了除了最快和次快以外所有其他旅行者的过桥模 式 任取一个满足结论七的最佳方案 假设 A 为最快 B 为次快 而 Z 是任意一个其他旅行者 根据结论七 他只过一次桥 然后就留在彼岸再不回来 考虑一下和他同行的另一位旅行者 这里有两种可能性 1 另一位旅行者还会回到此岸来 那么根据结论六 另一位一定是 A 所以 Z 过河的模式是这样的 A Z A 也就是 由 A 护送到对岸 A 返回 称作 模式一 2 另一位旅行者也不回来了 假设这两位旅行者过桥是在第 n 步 如果方案一共就是到第 n 步结束 那么根据结论四 在未执行第 n 步时 A 应该在此 岸 而在执行完第 n 步时 所有人都到了彼岸 所以那另一个旅行者就是 A 所以如果出 现这种情况 Z 过桥的模式实质上和1 中相同 由 A 护送到对岸 只不过 A 不用再返回而 已 如果方案中还有第 n 1步 我们考虑一下第 n 1步是什么 根据结论七 这步应该是 A 或者 B 回到此岸 但是根据结论四 我们知道在第 n 步时 A 在此岸 所以第 n 1不步可 能是 A 回来 所以只能是 B 回来 但是 B 在彼岸说明第 n 步前已经有一步使得 B 过了桥 根据结论六和结论三 那一步一定是 A 和 B 同行 然后 A 回来 我们就可以写出 Z 的过 桥模式 设另一位旅行者是 Y 他必不同于 A 和 B A B A 第 n 步 Y Z 第 n 1步 B 同结论七中的证明一样 我们可以修改这个方案为 第 n 2步 A B 第 n 1步 A 第 n 步 Y Z 第 n 1步 B 看了这个方案片断大家也许会有似曾相识的感觉 事实上 这就是本文开始四位旅行者问 题中需时5分钟和8分钟的旅行者过桥的模式 这个模式是 由 A 和 B 护送到对岸 A 和 B 返回 称作 模式二 结论八 一定有这样一种符合结论二 七的最佳方案 在这个方案里 所有除了最快和次 快的旅行者都以上面两个模式过桥 并且再不回来 六 最慢两人的过桥方式六 最慢两人的过桥方式 现在我们来考虑走得最慢和走得次慢的人是如何过桥的 假设走得最慢的是 Z 需时 z 走得次慢的是 Y 需时 y 我们要证明 结论九 所有符合结论八的最佳方案中 最慢两人过桥的模式必须相同 而且如果使用的 都是模式二 那么他们一定在一起过河 特别地 无论他们以什么模式过河 我们总可以在开始的4步里将他们移动到彼岸 1 假设 Z 以模式一过河 但是 Y 却以模式二过河 步骤旁为此步所需时间 A Z z A a A B b A a X Y y X 是另一不为 A 或 B 的旅行者 需时 x B b 我们可以把 X 和 Z 对换 变成 A X x X 是另一不为 A 或 B 的旅行者 需时 x A a A B b A a Z Y z B b 这时修改过的方案比原先的耗时短 y x 分钟 和原先的 最佳方案 假定矛盾 2 假设 Z 以模式二过河 但是 Y 却以模式一过河 步骤旁为此步所需时间 A Y y A a A B b A a X Z z X 是另一不为 A 或 B 的旅行者 需时 x B b 我们可以把 X 和 Y 对换 变成 A X x X 是另一不为 A 或 B 的旅行者 需时 x A a A B b A a Y Z z B b 这时修改过的方案比原先的耗时短 y x 分钟 和原先的 最佳方案 假定矛盾 所以 Z 和 Y 必定用同一模式过河 假设他们都以模式二过河 却不在一起 A B b A a W Y y W 是另一不为 A 或 B 的旅行者 需时 w B b A B b A a X Z z X 是另一不为 A 或 B 的旅行者 需时 x B b 我们可以把 X 和 Y 对换 变成 A B b A a W X t t 是 w 和 x 中比较大的那一个 B b A B b A a Y Z z B b 这时修改过的方案比原先的耗时短 y t 分钟 Y 是跑得次慢的 所以 y 比 w 和 t 都要大 和原先的 最佳方案 假定矛盾 于是最慢两人过桥的模式必须相同 而且如果使用的都是模式二 那么他们一定在一 起过河 现在我们来考虑在方案的前4步就将他们移动到彼岸 这非常简单 如果两人都是以模式一过