※ 引述《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