2
$\begingroup$

Let $n > 2$ be an integer.

a) There are $2n + 1$ batteries. We don’t know which batteries are good and which are bad but we know that the number of good batteries is greater by 1 than the number of bad batteries. A lamp uses two batteries, and it works only if both of them are good. What is the least number of attempts sufficient to make the lamp work?

b) The same problem but the total number of batteries is $2n$ and the numbers of good and bad batteries are equal.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Or are there any parts in particular that you’re stuck on? $\endgroup$ – boink Jun 14 at 1:03
  • $\begingroup$ Wouldn't the least amount of attempts just be 2 if you get both batteries that are good? And by attempts, do you mean picking one battery at random? $\endgroup$ – JC12 Jun 14 at 1:03
  • 2
    $\begingroup$ @JC12 I think it’s least amount to guarantee? Seems like the answer should be $n+2$ for the first one at least. And maybe $n+3$ for the second one? I’ll admit I’m not quite up for writing a solution though...sorry! $\endgroup$ – boink Jun 14 at 1:08
  • 1
    $\begingroup$ @boink I haven't been able to do any better than $n+4$ for the second. How do you do it in $n+3$? $\endgroup$ – saulspatz Jun 14 at 1:28
  • $\begingroup$ @saulspatz Ahh whoops, you're right! We only need $n+3$ to determine a good pair, but I just forgot that we actually need to put the correct pair into the lamp as well (which obviously makes it $n+4$, like you said). Thanks! $\endgroup$ – boink Jun 14 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.