※ 引述《DreamYeh (天使)》之铭言： : 你和心仪已久的正妹女生去登山，经过一个黑暗的隧道， : 忽然照明熄灭了，正妹害怕尖叫。 : 你赶紧有男子气概地说：「别怕！我有准备手电筒！」 : 结果一拿出手电筒，却发现电池没电，正妹叹一口气。 : 你不慌不忙说：「别怕！我有准备备用电池！还准备了 : 四颗！」 : 慌忙拆开手电筒後，你手电筒里那两颗电池却混入了你 : 备用的电池堆中。你赶紧整理一下，发现背包里居然有 : 八颗电池，正妹又叹一口气。 : 你只得赶紧回想，你确定新买了四颗电池是好的，另外 : 两颗是手电筒掉出的，还有两颗....啊！是之前留下的 : 电池，大概也没电了....想这麽多干嘛於事无补。 : 你要测试电池是否好的，只有一个办法，就是把电池装 : 入手电筒内（一次要装两颗），开启手电筒，只有两颗 : 电池都是好的才能使手电筒亮。 : 然而在黑暗之中，把电池装入手电筒、并打开是很耗时 : 的。你评估一下正妹的怒气值..... : 你只能装七次，装电池（并打开手电筒）到第七次，都 : 没成功，女生就会失去耐心地赏你一巴掌离去。 : 请问你要采取什麽策略？（想到七次就想看有没有六次 : 解或证明无法更简单） : 挑战题：2N个电池、N个是好的，则你需要最少几次？ 因为只有失败与成功两种结果 我们相当於是按照某一套固定的配对法试过一遍，甚至先後次序也没差 （尝试结果不会影响策略，因为成功之前一定全部都是失败） 问题可抽象化成： 建构一个 2N 个顶点的图，边越少越好， 使得其 independent number α < N 顶点就代表电池 每条边的顶点则是对应我们要拿去尝试的电池配对 这样的策略如果试不出来，代表可以找到 N 个顶点（好电池） 使其两两不相邻，也就是 independent set 而 independent number α < N，就表示任取 N 个顶点必定会有其中两者相邻 这样的话就比较好想了 例如 N = 4 时可以采用这样的图 △　△　─ 还可推广到 △　△　─　─　…　─ 也就是 2N 颗电池，可以用 N+3 次挑出两颗好的 因为要两个三角形，所以 N = 2 时不成立 实际上也能发现 N = 2 时需要全试过一遍，也就是 6 次 证明为最佳： α 有下界 α≧(2v-e)/3，v 是顶点数，e 是边数 由於 N 会大於能成功挑选的图的 α，也就大於至少为 (4N-e)/3 的整数 便得到 e 至少要 N+3 了 至於该下界的证明，我自己试着造了一个： 采取贪婪法建造图 G 的一个 independent set S(G) 每次挑选所剩的图的顶点中 degree 最小一个 v，放进 S 中 并且删除 v、其邻边、其邻边相连的顶点与这些顶点的邻边 令所剩的图为 G'，根据对顶点个数的归纳法，我们假设其符合 |S(G')| ≧ ( 2 v(G') - e(G') )/3 令 deg v = d，有 v(G) - v(G') = d+1 (v 和其 d 个邻居) 以及 e(G) - e(G') ≧ d+d(d-1)/2 (v 有 d 条邻边，v 的邻居每个至少再添 d-1 条， 但这 d-1 条可能跟另一个邻居重复) 综上三式 |S(G)| = |S(G')| + 1 ≧ ( 2 v(G') - e(G') )/3 + 1 ≧ ( 2 (v(G)-d-1) - e(G) + d+d(d-1)/2 )/3 + 1 ＝ ( 2 v(G) - e(G) + (d^2 - 3d + 2)/2 )/3 ≧ ( 2 v(G) - e(G) )/3 归纳法过关 由於可以造出顶点数 ≧ ( 2 v(G) - e(G) )/3 的 independent set S(G) 故其上界 α(G) ≧ ( 2 v(G) - e(G) )/3 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.109.73.249 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1701373503.A.17C.html 一开始的想法： 两两分成四组 A, B, C, D A, B, C 各装一次 [3 次] 若都不亮，则 Case 1: 四组都恰含一颗好的电池 Case 2: A, B, C 其中一组全坏，其他两组都恰含一颗好的电池，D 全是好的 接着拿 A 中两颗去跟 D 的其中一颗一一配对 [2 次] 若都不亮 Case 1: D 选到的是坏的 Case 2: A 全是坏的 最後拿 B 中两颗去跟 D 中另一颗一一配对 [2 次] B 中至少有一颗好的，D 的另一颗也一定是好的，所以会成功 其实就相当於本文中 △　△　─ 的解法 订正个错误，没考虑到边可能重复算 ※ 编辑: arthurduh1 (140.109.73.249 台湾), 12/06/2023 21:54:19