手电筒装两个好电池才能亮，现有 4 个好电池 4 个坏电池，试几次才能保证手电筒点亮？

Nicolas2050

1，4个好电池 4个坏电池 至少试几次,保证手电筒能亮？

2，a个电池,有b个是好的，其他都坏了。一手电筒要c个好电池才能亮，至少试几次才能保证该手电筒一定能亮？

已知a≥b,b≥c。

Nicolas2050

每次打开开关看手电筒有没有亮算一次测试。包括最后保证能亮的那一次。

lihp2020

我还真的被盛趣时代 面试过  

lihp2020

记得答案 有点像  \(\frac{c}{c-1}\cdot\log_{c }{ (a+b)}\)

luyuanhong

题  手电筒装两个好电池才能亮，现有 4 个好电池 4 个坏电池，试几次才能保证手电筒点亮？

答  先取 3 个电池，将三种不同的两电池配对都试一次，共试 3 次。

    如果 3 次都不亮，说明这 3 个电池中至少有 2 个坏电池。

    再取另外 3 个电池，将三种不同的两电池配对都试一次，也试 3 次。

    如果 3 次都不亮，说明这 3 个电池中也至少有 2 个坏电池。

    因为已知只有 4 个坏电池，上面已经把 4 个坏电池都找到了，剩下 2 个未试过的电池，必定是好电池。

王守恩

lihp2020 发表于 2022-1-4 17:21
记得答案 有点像  \(\frac{c}{c-1}\cdot\log_{c }{ (a+b)}\)

下面是答案吗(还是还可以更少)?什么规律？

手电筒装 2 个好电池才能亮，现有 A 个好电池 B 个坏电池，试几次才能保证手电筒点亮？

A=02,03,04,05,06,
00:01,01,01,01,01,
01:03,02,02,02,02,
02:06,04,03,03,03,
03:10,07,05,04,04,
04:15,11,07,06,05,
05:21,16,10,08,07,
06:28,22,13,10,09,
07:36,29,17,13,11,
08:45,37,21,16,13,
09:55,46,26,19,16，

朱裕德

上面的\(\frac{c}{c-1}\cdot\log_c(a+b)\)是错的，这问题我在知乎里有回答\(c=2\)的情况，\(\ c=3\)会变得异常复杂，好像目前还没有被解决出来，可惜了我还没有发链接的权限，可以查math.stackexchange中的Generalized solution to batteries and torch problem，里面有一篇论文里有提到。

这是个图论问题，如有k个好电池，我就把电池编好号，分成k-1个组，使得一定有其中的一个组至少有2颗好电池，以保证该组一定能把手电筒点亮。我们可以设计一个图兰图（Turán Graph）把各组间的实验表示出来，然后用完全图将其减去（因为我们一会儿实验的时候只会在组内进行实验，用以找到组内那2颗好电池）。即，问题中4好4坏的时候可以这么设计实验：

1. GraphDifference[CompleteGraph[8],TuranGraph[8,3(*好电池数量-1*)],VertexLabels->"Name"]

复制代码

边数为7，可见4好4坏的时候需要做7次实验就能确保手电筒亮起来，类似的，如果有3个好电池，5个坏电池时需要做12次实验：

1. GraphDifference[CompleteGraph[8],TuranGraph[8,2],VertexLabels->"Name"]

复制代码

拓展一下，n个电池中有k个好电池时需要多少次实验能保证手电筒亮起来呢？公式如下：
\[\frac{n(n-1)}{2}-\left\lfloor \frac{n^2(k-2)}{2(k-1)}\right\rfloor\]

王守恩

朱裕德 发表于 2022-6-4 12:24
上面的\(\frac{c}{c-1}\cdot\log_c(a+b)\)是错的，这问题我在知乎里有回答\(c=2\)的情况，\(\ c=3\)会变得 ...

谢谢朱裕德！6楼错啦！！改正过来！！！

手电筒装 2 个好电池才能亮，现有 A 个好电池 B 个坏电池，试几次才能保证手电筒点亮？

A=02,03,04,05,06,
00:01,01,01,01,01,
01:03,02,02,02,02,
02:06,04,03,03,03,
03:10,06,05,04,04,
04:15,09,07,06,05,
05:21,12,09,08,07,
06:28,16,12,10,09,
07:36,20,15,12,11,
08:45,25,18,15,13,
09:55,30,22,18,15，

朱裕德

王守恩 发表于 2022-6-5 11:05
谢谢朱裕德！6楼错啦！！谢谢朱裕德！！！

手电筒装 2 个好电池才能亮，现有 A 个好电池 B 个坏电池， ...

c=2的时候我下面已经给出具体的公式了啊，我的n就是你的A+B，k就是你的A

王守恩

朱裕德 发表于 2022-6-5 14:13
c=2的时候我下面已经给出具体的公式了啊，我的n就是你的A+B，k就是你的A

谢谢朱裕德！你是对的。6楼错啦！6楼错啦(8楼已改正)所以找不到规律了。

手电筒装 3 个好电池才能亮，现有 3 个好电池 B 个坏电池，试几次才能保证手电筒点亮？

1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286，.....

打不开：math.stackexchange中的Generalized solution to batteries and torch problem