1
$\begingroup$

We have two lamps that only function if both have a functioning bulb in them. We also have 5 functioning and 5 non-functioning light bulbs in a drawer. How should we proceed in trying out the light bulbs, if we want to use the lowest amount possible to light the lamps up?

$\endgroup$
  • $\begingroup$ What are your thoughts? $\endgroup$ – saulspatz Oct 13 '19 at 18:33
  • $\begingroup$ Well, I would probably start by putting in two light bulbs, then taking one out and putting another one in, then taking the other one out, and so on. But I can't prove it and I am not even sure. $\endgroup$ – Pavol Komlos Oct 13 '19 at 18:43
  • $\begingroup$ I think the point of the question is which ones would you try? When it didn't light the first time, do you leave one bulb in and try and a new one? Or do you try two untested bulbs? In either event, what do you if the second test fails? Here is a somewhat similar question that may be related. $\endgroup$ – saulspatz Oct 13 '19 at 18:48
  • 2
    $\begingroup$ Could you try to give more details. Are you trying to minimize the expected value of light bulbs changes or are you trying to minimize the number of light bulbs changes that ensures you light them up. If you change the two light bulbs it counts twice as much as if you just switch one? $\endgroup$ – David Jaramillo Oct 13 '19 at 18:49
  • 1
    $\begingroup$ Why do you have the tag probability if you are looking for a guarantee? Also, what does this have to do with game theory? $\endgroup$ – saulspatz Oct 13 '19 at 22:04
1
$\begingroup$

The best I've been able to do is $12$ changes, but I don't know if that's the minimum. Here's my algorithm. In all cases, I assume the lamp doesn't light.

  1. AB (2 changes)
  2. AC
  3. BC
  4. DE (2 changes)
  5. DF
  6. EF At this point, we know there is at most one good bulb among A,B,C and at most one good bulb among DEF, so there are at least three good bulbs among G,H,I,J. So we test GH and if that fails, IJ is bound to succeed, giving four additional changes at most.
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Another way to get minimum $12$ changes. Try $3$ pairs (6 changes): $$AB, CD, EF$$ They can be double defective or mixed.

Then, the rest $2$ pairs ($GH,IJ$) must have at least $2$ normal light bulbs. Try: $$GH \ (2 \text{ changes})\\ GI \ (1 \text{ change})\\ GJ \ (1 \text{ change})$$ If they don't light, then: $$HJ \ (2 \text{ changes})$$ will definitely light.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But then you're nowhere near done. $\endgroup$ – David G. Stork Oct 14 '19 at 6:09
  • $\begingroup$ @David G. Stork, what do you mean? $\endgroup$ – farruhota Oct 14 '19 at 6:23
  • $\begingroup$ How have you found all five working bulbs? And it is unclear how many "tests" you've made. Could you please specify the maximum number of tests to find all 5? $\endgroup$ – David G. Stork Oct 14 '19 at 6:24
  • $\begingroup$ It does not ask to find all $5$, but the $2$ working so that the lamps light up. The "tests" are the "changes", which add up to $12$. I followed the notations of @saulspatz to be consistent (therefore I started "Another way to..."). $\endgroup$ – farruhota Oct 14 '19 at 6:28
  • 1
    $\begingroup$ Alright. I think the OP should have been clearer on the nature of the problem, but if it is just to light up the room, then your answer seems fine. $\endgroup$ – David G. Stork Oct 14 '19 at 6:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.