※ 引述《DreamYeh (天使)》之铭言： : 你要测试电池是否好的，只有一个办法，就是把电池装 : 入手电筒内（一次要装两颗），开启手电筒，只有两颗 : 电池都是好的才能使手电筒亮。 : 然而在黑暗之中，把电池装入手电筒、并打开是很耗时 : 的。你评估一下正妹的怒气值..... : 你只能装七次，装电池（并打开手电筒）到第七次，都 : 没成功，女生就会失去耐心地赏你一巴掌离去。 : 请问你要采取什麽策略？（想到七次就想看有没有六次 : 解或证明无法更简单） : 挑战题：2N个电池、N个是好的，则你需要最少几次？ 给一下这一题的预设答案： 将八颗电池，以三个为一组分组，假设为 A B C， 其中AB有三颗电池，C有两颗。 挑Ａ这一组，三颗电池，任选两颗轮流测试，如此共会 测试三次。共三次。 若都没有亮，挑Ｂ这一组，同样三颗电池，任选两颗轮 流测试，如此共会测试三次。共六次。 若仍然都没有亮，则挑Ｃ这一组，也就是第七次测试， 必亮。 解析： 当Ａ这一组怎麽样都没亮时，则可能Ａ这一组包含两个 、或三个坏电池。 如果Ａ包含三个坏电池，Ｂ最多含一个坏电池，则Ｂ这 一组三颗彼此测试，必定能亮。 如果Ａ、Ｂ都进行「三颗轮流测试」，都是不亮，必定 是能是Ａ、Ｂ都含有两个坏电池。。 此时，Ｃ只能是两个好电池，测Ｃ组必亮。 挑战题： 若有2N个电池，内有N个好电池，则最佳策略为N+3次可测得。 方法是 四颗电池，则需测满四取二的所有组合 六颗电池或以上。则 1.三个为一组为A、三个为一组为B，其余两个两个为一组 2.A组内任选两个进行交互测试，若亮则结束测试。如此三次组内测完 3.B组内任选两个进行交互测试，若亮则结束测试。如此三次组内测完 4.第三组开始，两个为一组进行测试，若亮则结束测试， 不亮则继续下一组 5.如此测试到亮为止 6颗电池，最多测 3 + 3 = 6次 8颗电池，最多测 3+3+1 = 7次 10颗电池，最多测 3+3+2 = 8次 ......以此类推 证明： 由於听众是国中生，因此尽可能不用图论，虽然其实也是讲图论那一套.... case 1.六颗电池情况 无论用什麽策略，我们尝试将「彼此之间不互相测试的集合」进行分组。 例如策略为： 先测试其中两颗电池（标为AB） 再将剩下四颗电池彼此拿来测试一次（CDEF） 後面测试AB都不参与CDEF这组别测试，则将 AB列为第一组 CDEF列为第二组 那这样，是否允许有第三组呢？ 答案是不允许的。因为假如有三组（至少含一个），彼此互相不进行测试。 则好的电池若刚好是三组内各有一颗，根据定义，不可能测到，此策略失败。 那如果只有一组，组内所有电池都彼此参与测试呢？ 则该组含有六颗电池，最少的测试策略为 A-B-C-D-E （即A、B相测试，B、C相测试....、F可跟BCDE接） 无论F跟谁接都一样，这样至少有五次测试。 但这种情况，若A、C、E刚好为好的电池，则此策略将不能测到 若需考虑，则必定需要增加测试状况，也就是六次以上 （虽然我们其实知道只有一组、六次测试也是不行，但不需用到此） 那如果有两组呢？考虑一组至少有两个电池， 那可能为 4 - 2 或 3-3 在4-2这一种分组状况，若四个电池那包，有两颗以上电池未彼此 测试（图形上画四颗为成长方形、另两颗彼此相连） 则挑选该两颗，与两颗一组的电池选一颗，假如这三颗都是好的电 池，此种策略无法挑出该状况 最後，如果是三个-三个 分两组测试。同样，若其中有一组， 有两颗以上电池未彼此测试（图形上画三颗排成一列） 则选该两颗、另外一组任选一颗，可发现此策略依旧会无法挑选出。 因此只有分两组、每组三颗电池 每一组都是「三颗之间彼此测试」，才能保证所有情况都能测出 case 2.6+2颗电池情况 证明六颗电池，必须测六次後，後面反而好证明了。 当我们加入「一好一坏的两颗电池」 则非常显然，无论什麽策略，该两颗电池都必须参与测试， 也就是少也要多测一次，因此 6颗电池，最多测 3 + 3 = 6次 8颗电池，最多测 3+3+1 = 7次 後面就用数学归纳法，就能完成证明了 ＝＝＝＝ 说明：打起来很复杂，实际上画图说明能使对方更好理解。 若有能帮助人理解的更好方式，欢迎打出 至於实际把妹........ 机会只有一次，请不要把用过电池与一般电池混淆！ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.115.158.137 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1701696319.A.59B.html