※ 引述《m06 (桂冠汤圆)》之铭言： : 推文提到 : 推 rehearttw:有教授证明过了，依原题目，确实要四次。有计算公式 05/27 07:52 : 很好奇证明是怎麽证的.. : 前面有12个金币的分别法 : 感觉13个应该也可行耶.. : 不知道有没有教授的证明可以参考＠＠? 我好像看过那个证明，但有点抽象，用我的方法讲讲看。 首先要澄清题目。我现在要证的题目的要求，除了必须找出假硬币，还必须知 道这个假硬币是轻或重。像最近又讨论起来的题目是只要找到假硬币即可，在13 个金币时正好会有差。 先考虑三个金币的情况，先行编号後，只有六种可能： 1轻 1重 2轻 2重 3轻 3重 假设我们把 1 2 拿去秤，有三种结果，那它们对应到的可能就变成： A. 1 > 2 1重 or 2轻 B. 1 < 2 1轻 or 2重 C. 1 = 2 3轻 or 3重 注意到秤一次之後，原来的六种可能被划分成三组二种可能，下一步就可以找 出假硬币「并且」知道它是轻或重。例如刚刚得到 1<2 就拿 1 3 去秤： B a. 1 = 3 2重 B b. 1 < 3 1轻 如果是四个金币，有八种可能：1轻 1重 2轻 2重 3轻 3重 4轻 4重 同样把 1 2 拿去秤，但这时对应到的就变成： A. 1 > 2 1重 or 2轻 B. 1 < 2 1轻 or 2重 C. 1 = 2 3轻 or 3重 or 4轻 or 4重 在 case C 里面，有四种可能。但你不管如何安排下一次比较，都只有 > = < 三种结果，是不够区分出四种可能的。至少会有两种可能给你相同的结果。最好 的安排是拿 1 3 去秤，变成 C a. 1 > 3 3轻 C b. 1 < 3 3重 C c. 1 = 3 4轻 或 4重 <= 这里就失败了 因此在只秤两次的情况下，最多只能有三个金币。 在只剩最後一次秤的机会的时候，最多只能有 3 个情况，不然一定会有一种 结果让你失败。同样的道理，只剩最後两次秤的机会时，最多只能有 9 个情况 ，不然分下去後会有一堆有 4 个以上，而那堆就可能会失败。 在 12 个金币的问题里，拿 1234 和 5678 去秤，会得到 A. 1234 > 5678 1重 2重 3重 4重 5轻 6轻 7轻 8轻 B. 1234 < 5678 1轻 2轻 3轻 4轻 5重 6重 7重 8重 C. 1234 = 5678 9轻 9重 10轻 10重 11轻 11重 12轻 12重 刚刚好每组有 8 个可能，不超过 9 个。 若有 13 个金币，那有 26 种可能，看似可以分成 9 9 8，但其实没办法，最 好的秤法仍然是拿 1234 和 5678 去秤： A. 1234 > 5678 1重 2重 3重 4重 5轻 6轻 7轻 8轻 B. 1234 < 5678 1轻 2轻 3轻 4轻 5重 6重 7重 8重 C. 1234 = 5678 9轻 9重 10轻 10重 11轻 11重 12轻 12重 13轻 13重 这样 case C 里面有 10 种可能，是没办法在秤两次内找出是哪个情况的。所 以说，若要同时找出假硬币「并且」知道是太轻或太重的话，13 个金币需要秤 四次。 -- Just because you deserve this doesn't mean they're gonna give it to you. Sometimes you gotta take what's yours. ── Kenny Ray Carter --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.49 ※ 编辑: eieio 来自: 140.112.30.49 (06/01 06:39) ※ 编辑: eieio 来自: 140.112.30.49 (06/01 06:42)