Lamp with batteries
You have a lamp and 2n+1 batteries (n>2), when exactly n of the batteries doesn't work (You don't which are which). To make the lamp work, you need to put 2 working batteries inside it (you can put only 2 batteries inside at a time). What is the minimal amount of tries possible to make sure the lamp works?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
If we have 2 n + 1 batteries in total, and n of them do not work, this means that n + 1 of them do work.
First, separate the batteries into n piles of two (you will have one extra battery every time, because 2 n + 1 is odd. Just place this battery to the side for now). Try each pile of two batteries. This will take you n tries total. Worst case scenario, none of them work. The only way that this can happen is if each pile has at least one dead battery in it. But because there are exactly n piles and n batteries, each pile MUST have exactly 1 dead battery (using the pigeonhole principle ). All of the dead batteries are accounted for: there is one in every pile. Therefore, the lone battery that was not placed into a pile is a working battery.
Now, to find the second, take any one pile, and try your working battery with both of the ones in the pile. The first try is your working battery with the dead battery in the pile. One the second try, it must be your working battery with the working battery in the pile.
It takes you n tries to find one working battery, and 2 tries to find the second (worst case scenario). Therefore, it takes you n + 2 tries total.