a) There are $n+1$ good batteries and $n$ bad batteries. We divide the batteries in sets of three. We need $C_3^2=3$ attempts to verify all possible pairs of these three batteries. If the lamp don't works, we test the next set of three batteries and continue this process. Under the most unfavourable circumstances, each set contains $1$ good battery and $2$ bad batteries. For $n$ even, is necessarily the test of $\dfrac{n}{2}$ sets to eliminate all bad batteries, which means $\dfrac{3n}{2}$ attempts. All remained $\dfrac{n}{2}+1\ge 3$ batteries are good. Results, for $n$ even, we need at least $\dfrac{3n}{2}+1$ attempts to make surely the lamp to work. For $n$ odd, after the test of $\dfrac{n-1}{2}$ sets $\left( \dfrac{3(n-1)}{2} \textnormal{attempts} \right)$, remains $1$ bad battery and the other $\dfrac{n+3}{2}\ge 3$ batteries are good. In this case, we need at least $\dfrac{3(n-1)}{2}+3=\dfrac{3(n+1)}{2}$ attempts to make surely the lamp to work. Using a closed form, the least number of attempts is $N=\dfrac{3n+2}{2}+\dfrac{1+(-1)^{n+1}}{4}$. b) In this case, there are $n$ good batteries and $n$ bad batteries. We use the same method. For $n$ even, after $\dfrac{3n}{2}$ attempts remain $\dfrac{n}{2}\ge 2$ good batteries. For $n$ odd, after $\dfrac{3(n-1)}{2}$ attempts remains $1$ bad battery and the other $\dfrac{n+1}{2}\ge 2$ batteries are good. The result is the same, $N=\dfrac{3n+2}{2}+\dfrac{1+(-1)^{n+1}}{4}$.

algorithm works better (although I can't prove this is the best).

Yes, you are right! In case a), $n+2<N, \forall n>2$. And we can use your method, also, in case b). Divide the batteries in $n$ groups of $2$. If none of the groups works, each of those groups has one good and one bad battery. Then we test $2$ groups, which contain $2$ good and $2$ bad batteries and this last step needs at most $6$ trials. In this way, the total number of attempts is maximum $n+6$. Only for $n\in\{3,4,5,6,7,8\}, N<n+6$; for $n=9$ and $n=10$, the two methods are similar. For $n>10$, your method is better. Final result for case b): $\begin{cases} \dfrac{3(n+1)}{2} \; \textnormal{for n} \in \{3,5,7\}\\ \dfrac{3n}{2}+1 \; \textnormal{for n} \in \{4,6,8\} \\n+6 \; \textnormal{for n} \ge 9. \end{cases}$

And a more efficient sequence for case b): We test the first $n-2$ groups of $2$ batteries. If none of the groups works, each of those groups has one good and one bad battery and remain $2$ good and $2$ bad batteries. For the last $4$ batteries we need $6$ trials. In this way, the total number of attempts is maximum $n+4$. Final result for case b): $\begin{cases} 6 \; \textnormal{for} \; n=3\\ 7 \; \textnormal{for} \; n=4 \\n+4 \; \textnormal{for} \; n\ge 5. \end{cases}$

a) The answer is $n+2$. Check the pairs $(2k-1,2k)$ for all $1\le k\le n$ and then check the pairs $(2k-1,2k+1)$ and $(2k,2k+1)$. Assume that the first $n$ checks fail. Since there are exactly $n$ bad lamps, every pair $(2k-1,2k)$ consists of a bad lamp and a good lamp and $2n+1$ is a good lamps. Hence one of $(2n-1,2n+1)$ and $(2n,2n+1)$ is a pair of good lamps and we are done. For minimality, assume for contrary that we performed $n+1$ checks. We can assume that the strategy doesn't rely on the results of the checks, since we are only interested in the case that every lamp doesn't turn on. By PHP, there exists a lamp which was used twice. Take this lamp, and also take every lamp from every other check. We took at most $n$ lamps, so we can assume that all these lamps are bad. Hence it can happen that all checks fail, contradiction.

It turns out that the same idea works for both parts (only the computations are different).

Solution with Aahan, Aatman Supkar, Aibek, Anshul, Archit, Arindam, Ethan Liu, G, Grant Yu, Maximus Lu, Naruto. D. Luffy, Paul Hamrick, R. Correaa , Rohan Goyal, yuanfeng: Part (a) We claim $n+2$ trials is the answer. To show $n+2$ steps are sufficient start by trying the batteries in disjoint pairs $A_1 B_1$, $A_2 B_2$, \dots, $A_n B_n$. If none of them work, the last battery $Z$ is good and there is exactly one good battery in each pair we tried. Now use $ZA_1$ and $ZB_1$. To show $n+1$ steps is insufficient, we will prove for a graph $G$ on $2n+1$ vertices with at most $n+1$ edges there is a vertex cover with $n$ vertices. First cover any vertex of degree at least $2$ (it must exist); then cover any uncovered edges one by one (choosing the endpoint arbitrarily). Part (b) We claim the answer is $n+3$. First, try three batteries $AB$, $BC$, $CA$ in that order. If none of them work, at least two batteries are good and then we can apply the previous odd case to $N = 2n-3$. This takes $3 + \left( (n-2)+2 \right) = n+3$ steps. The proof of necessity is similar: given a graph $G$ on $2n$ vertices with at most $n+2$ edges, we take any vertex of degree at least $2$, cover it, and then apply the previous odd case.

Part a) I claim that our answer is $n+2$. We can divide the batteries into $n$ pairs with one left over. If one of the pairs works, then we are done. Suppose otherwise. With $n$ pairs, come $2n$ batteries. If no pair has two good batteries, then each pair has at most one good battery, hence a total of at most $n$ good batteries. This means we must have $\geq n$ bad batteries, but since there are exactly $n$ bad batteries, we must have $n$ good and $n$ bad batteries among the $n$ pairs. Furthermore, each pair must have exactly one good and one bad battery or else some pair has both good batteries. The remaining battery must be good. Comparing the $n$ pairs takes $n$ attempts. Lastly, we take the remaining battery and compare it with both batteries of a chosen pair. One of the batteries in that pair is good, so $2$ more attempts suffices. Hence, $n + 2$ tries is sufficient. Now we show that $n+1$ attempts is not enough. Consider a graph on $2n+1$ vertices, where a vertex represents a battery. Notice that among the total $\tbinom{2n+1}{2} = 2n^2 + n$ possible edges, exactly $\tbinom{n+1}{2} = \tfrac{n(n+1)}{2}$ of them are good and the remaining are bad. Suppose that testing $n+1$ times is enough. Now let each test represent a connection; we have $n+1$ connections. I claim that there must be a $K_{n+1}$ of all non-connected vertices. Since it is impossible to tell which batteries are good or not, we cannot locate the $n+1$-clique of all good batteries. So in fact, our claim suffices. Consider the complementary graph, with $\tbinom{2n+1}{2} - (n+1) = 2n^2 -1$ edges. By a certain Turan's Theorem, the largest number of edges for a graph on $2n+1$ vertices without $K_{n+1}$ is $$\left(1 - \frac{1}{n}\right)\cdot \frac{(2n+1)^2}{2} = 2n^2 - \frac{3}{2} - \frac{1}{2n} < 2n^2 - 1$$ hence the complementary graph on $2n^2 - 1$ edges must have a $K_{n-1}$, as desired. No matter how the $n+1$ tests are performed, among the remaining edges, there must exist a $K_{n+1}$ clique, as desired. $\blacksquare$ Part b) I claim that our answer is $n+3$. Take three batteries and perform three tests, pairwise. If none of them work, then we either have all three batteries bad, or one of them good and two of them bad. Either way, we throw out all three batteries and perform the above argument on $2n-3$, yielding a total of $((n-2) + 2) + 3 = n+3$ tries. The proof that $n+2$ tries doesn't work also follow from Turan's. Suppose that if two batteries are tested we connect them. We want to show there is a $K_n$ in the $\tbinom{2n}{2} - (n+2) = 2n^2 - 2n - 2$ edges of the complementary graph. Indeed, we check that $$\frac{n-2}{n-1} \cdot \frac{4n^2}{2} < 2n^2 - 2n - 2$$ so we are done. $\blacksquare$ Remark: GRAF THERY. YUH!

The equivalent graph theory analog of this problem is: What's the minimum number of edges required such that in a graph of $2n+1$ (or $2n$) vertices there is no isolated group of $n+1$ (or $n$) vertices. Here's a few somewhat obvious facts that are important for this proof: Observation: Any tree of at least $2$ edges must contain two isolated vertices, any graph with a cycle must contain two isolated vertices, and any tree of at least $4$ edges must contain three isolated vertices. The answer for part $a$ is $n+2$, acheived by letting our graph be the disjoint union of $n-1$ $K_2$ and $1$ $K_3$. Pigeonhole says we must have two vertices in a $K_2$ or $K_3$ subgraph, which then must be adjacent. WLOG we only need to prove the existence of an isolated group of $n+1$ vertices in any graph with $n+1$ edges and $2n+1$ vertices. If our graph has at least $n+1$ connected components, we'd be done. Otherwise, we have exactly $n$ connected components which are all trees. One connected component must have at least $2$ edges, and thus contain $2$ isolated vertices. Every other connected component has at least $1$ isolated vertex, giving $n+1$ isolated vertices in total. Moving on to part $b$, the answer is $n+3$, acheived by letting our graph be the disjoint union of $n-3$ $K_2$ and $2$ $K_3$. Pigeonhole says we must have two vertices in a $K_2$ or $K_3$ subgraph, which then must be adjacent. WLOG we only need to prove the existence of an isolated group of $n$ vertices in any graph with $n+2$ edges and $2n$ vertices. If our graph has at least $n$ connected components, we'd be done. Otherwise, we either have $n-2$ connected components which are all trees or $n-1$ connected components with $1$ cycle among them. In the first case, we either have two trees with at least $2$ edges or $1$ tree with at least $4$ edges, and either way we can find $n$ isolated vertices. In the second case, we can also find $n$ isolated vertices.

The answer is $\tfrac{N+3}{2}$ when $N$ is odd and $\tfrac{N}{2}+3$ when $N$ is even. First we show these bounds are achievable; if $N=2k+1$ is odd, then separate the batteries into $k-1$ pairs and a single group of $3$ batteries. There must be some group with at least two batteries; thus by testing every group we can find a good pair in at most $k+2$ attempts. If $N=2k$ is even, then separate the batteries into $k-3$ pairs and two groups of $3$ batteries. Again, there must be some group containing at least two good batteries, so by testing all the groups, we can find a good pair in at most $k+3$ attempts. Now we show this is the best we can do; consider the complete graph $K_N$ on $N$ vertices, where each battery is a vertex, and we color an edge red if it corresponds to two good batteries. There's a red complete subgraph of at least $\lceil \tfrac{N}{2} \rceil$ vertices. It's clear that the minimum number of attempts we need is thus the minimum integer $t$ such that we can remove $t$ edges from $K_N$ and the remaining graph has no $K_{\lceil N/2 \rceil}$. By Turan's theorem, we get $$\binom{N}{2}-t \le \frac{\lceil N/2 \rceil-2}{\lceil N/2 \rceil - 1} \cdot \frac{N^2}{2}$$ and from here it's not hard to get $t > \tfrac{N+1}{2}$ when $N$ is odd and $t > \tfrac{N}{2}+2$ when $N$ is even.

Can you check if this is true? a) We claim that we need at least $n+1$ moves to guarantee finding two good lamps. (So the answer is n+2) Assume that with $x \le n$ moves are sufficent. These moves are between two bad lamps or one bad, one good lamp. Otherwise $x-1$ moves would be sufficient. Assume that we are sure that $u,v$ are good lamps. Let $A$ be the set of lamps we performed a move, let $B$ the set of other lamps. $|B|\ge 1$ because of our assumption. Call two lamps friends if we performed a move to this pair. $\textbf{Claim:}$ We cannot guarantee that all lamps in $B$ are good. Proof: Assume otherwise. If there exists a bad lamp $b$ in $A$ such that all friends of $b$ are bad, then we can change $b$ with a lamp in $B$, contradicting with second assumption(not the main one). Otherwise any bad lamp is friend with exactly one good lamp. We can change $u$ with his friend in $A$ without affecting the results, contradicting with main assumption. $\square$ We can change $u$ with a bad lamp in $B$ without affecting the results. Contradiction.

We will solve the problem for $N$ batteries for all $N\geq3$. This is equal to finding the smallest number of edges needed to be removed from a $K_N$ to be left with no $K_{\left\lceil\frac N2\right\rceil}$. If $N=2n$, then by Turan's Theorem, the optimal graph is $K_{2,2,\ldots,2,3,3}$, which removes $6+(n-3)=n+3$ vertices for $n\geq3$. If $n=2$, then the answer is $\binom42=6$. If $N=2n+1$, then the optimal graph is $K_{2,2,\ldots,2,3}$, which removes $3+(n-1)=n+2$ vertices. Therefore, the least number of attempts needed is $\boxed{\begin{cases}6&N=4\\n+3&N=2n\\n+2&N=2n+1\end{cases}}$.