A flashlight takes 2 (working) batteries.

26 views
Skip to first unread message

henh...@gmail.com

unread,
Aug 30, 2022, 3:37:43 PMAug 30
to

------ pls wait 3+ days (Longer if you find it easy or trivial) before posting answers or hints.



A flashlight takes 2 (working) batteries.

There are 8 batteries (on the Table), but some of them may be Dead (and Non-Conducting).

To guarantee that the flashlight gets turned on, what is the minimum number of battery pairs you need to test ?


(0) ... when you have Zero additional info

(1) ... when exactly 1 of the batteries is Dead.

(2) ... when exactly 2 of the batteries are Dead.

(3) ... when exactly 3 of the batteries are Dead.

(4) ... when exactly 4 of the batteries are Dead.

(5) ... when exactly 5 of the batteries are Dead.

(6) ... when exactly 6 of the batteries are Dead.

(7) ... when exactly 7 of the batteries are Dead.

Kerr-Mudd, John

unread,
Aug 31, 2022, 5:36:38 AMAug 31
to
On Tue, 30 Aug 2022 12:37:42 -0700 (PDT)
"henh...@gmail.com" <henh...@gmail.com> wrote:

>
> ------ pls wait 3+ days (Longer if you find it easy or trivial) before posting answers or hints.
>

Feh.
>
>
> A flashlight takes 2 (working) batteries.
>
> There are 8 batteries (on the Table), but some of them may be Dead (and Non-Conducting).
>
> To guarantee that the flashlight gets turned on, what is the minimum number of battery pairs you need to test ?
>
>
> (0) ... when you have Zero additional info
>
> (1) ... when exactly 1 of the batteries is Dead.
2

>
> (2) ... when exactly 2 of the batteries are Dead.
>
> (3) ... when exactly 3 of the batteries are Dead.
>
> (4) ... when exactly 4 of the batteries are Dead.
>
> (5) ... when exactly 5 of the batteries are Dead.
>
> (6) ... when exactly 6 of the batteries are Dead.

You'll probably need some stats nCx type combinatorics to get these.

>
> (7) ... when exactly 7 of the batteries are Dead.
0. It ain't gonna work.

--
Bah, and indeed Humbug.

Richard Heathfield

unread,
Aug 31, 2022, 6:20:44 AMAug 31
to
On 31/08/2022 10:36 am, Kerr-Mudd, John wrote:
> On Tue, 30 Aug 2022 12:37:42 -0700 (PDT)
> "henh...@gmail.com" <henh...@gmail.com> wrote:
>
>>
>> ------ pls wait 3+ days (Longer if you find it easy or trivial) before posting answers or hints.
>>
>
> Feh.
>>
>>
>> A flashlight takes 2 (working) batteries.
>>
>> There are 8 batteries (on the Table), but some of them may be Dead (and Non-Conducting).
>>
>> To guarantee that the flashlight gets turned on, what is the minimum number of battery pairs you need to test ?

Zero. (Be prepared. Always carry fresh torch batteries.)

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Edward Murphy

unread,
Sep 5, 2022, 8:48:33 PMSep 5
to
On 8/31/2022 2:36 AM, Kerr-Mudd, John wrote:

> On Tue, 30 Aug 2022 12:37:42 -0700 (PDT)
> "henh...@gmail.com" <henh...@gmail.com> wrote:
>
>>
>> ------ pls wait 3+ days (Longer if you find it easy or trivial) before posting answers or hints.
>>
>
> Feh.
>>
>>
>> A flashlight takes 2 (working) batteries.
>>
>> There are 8 batteries (on the Table), but some of them may be Dead (and Non-Conducting).
>>
>> To guarantee that the flashlight gets turned on, what is the minimum number of battery pairs you need to test ?
>>
>>
>> (0) ... when you have Zero additional info
>>
>> (1) ... when exactly 1 of the batteries is Dead.
> 2
>
>>
>> (2) ... when exactly 2 of the batteries are Dead.
>>
>> (3) ... when exactly 3 of the batteries are Dead.
>>
>> (4) ... when exactly 4 of the batteries are Dead.
>>
>> (5) ... when exactly 5 of the batteries are Dead.
>>
>> (6) ... when exactly 6 of the batteries are Dead.
>
> You'll probably need some stats nCx type combinatorics to get these.

Some of these are simpler. Label the batteries A through H, then test
AB CD EF GH in that order:

(2) 3. Worst-case scenario is that the dead batteries are (one of AB)
and (one of CD).

Similarly, (3) 4. Worst-case scenario is (one of AB), (one of CD), and
(one of EF).

(4) and (5) are the most complex of the bunch.

* There are C(8, 2) = 28 unordered pairs of batteries.

* For (4), if we test AB CD EF GH and they all fail, then the dead
batteries are (one of AB), (one of CD), (one of EF), and (one of
GH). So then we can test AC AD BC BD in that order, and the
worst-case scenario is that A and C are dead. So we can succeed
with at most 8 tests; there may be a more efficient approach,
though I don't know what it would be.

* For (5), if we test the C(7, 2) = 21 unordered pairs that *don't*
contain H, then we can succeed with at most 21 tests. (Even if H
works, so do two others.) Again, there may be a more efficient
approach, though I don't know what it would be.

(6) 28. The worst-case scenario is that, whichever pair we try last,
those two are the only two working batteries.

henh...@gmail.com

unread,
Sep 5, 2022, 10:14:04 PMSep 5
to
(on the Net) i only see flashlight(2, 8, 4) being asked, mentioned
(in the many Web pages and Youtube clips)

but (i think) flashlight(2, 6, 3) is interesting too.

henh...@gmail.com

unread,
Sep 6, 2022, 1:15:25 AMSep 6
to
On Monday, September 5, 2022 at 5:48:33 PM UTC-7, Edward Murphy wrote:
(5 dead) ... when exactly 5 of the batteries are Dead. (and 3 are Alive)


method 5A requires 12 moves in the worst case.

method 5B requires 13 moves in the worst case. ---- could this one be BETTER in some way ?



in these problems, we are trying to reduce the # of moves in the worst case.

Do we have interesting (new) genre of problems, if we instead
tried to reduce the # of moves in the average case ?

Edward Murphy

unread,
Sep 11, 2022, 9:09:08 PMSep 11
to
I don't understand what specific methods you're labeling as 5A and 5B
here. (If they're different methods to approach the same scenario, then
clearly 5B could "be better": you could replace it with 5A.)

Taking the same sort of constructive approach that I labeled (4) above
(4 dead / 4 alive), and applying it to the case of 5 dead / 3 alive:

* Test AB CD EF GH. Worst case is that they all fail, meaning that the
5 dead batteries include one from AB, one from CD, one from EF, and
one from GH.

* Test AC AD BC BD. Worst case is that they all fail, meaning that the
5 dead batteries include either (both A and B) or (both C and D).

* Test EG EH FG FH. Worst case is that the first three fail, meaning
that E and G are dead, in which case FH succeeds (test #12).

I'm guessing that this is what you meant by 5A. 5B remains unclear.

> in these problems, we are trying to reduce the # of moves in the worst case.
>
> Do we have interesting (new) genre of problems, if we instead
> tried to reduce the # of moves in the average case ?

Interesting to someone, I'm sure; but while I would not be confident of
(worst case 4 of 8 dead) or (worst case 5 of 8 dead) without running a
brute-force computer analysis, I wouldn't even attempt this new type of
problem without such an analysis.

In each case, if there are X batteries (Y of which are dead), then we
have:

* C(X, Y) possibilities for the subset of all dead batteries. These
are the possible scenarios that we could start in.

* N = C(X, 2) possibilities for pairs of batteries to test, thus
factorial(N) permutations of those pairs. These permutations are
the possible search strategies that we could follow.

Then compare every strategy in the second part to every scenario in the
first part, and calculate each strategy's worst case and average case.

henh...@gmail.com

unread,
Sep 11, 2022, 10:00:22 PMSep 11
to

> >>>> ------ pls wait 3+ days (Longer if you find it easy or trivial) before posting answers or hints.

> >>>>
> >> A flashlight takes 2 (working) batteries.
> >>
> >> There are 8 batteries (on the Table), but some of them may be Dead (and Non-Conducting).
> >>
> >> To guarantee that the flashlight gets turned on,
what is the minimum number of battery pairs you need to test ?



flashlight-2 ( 8 batteries, 4 dead ) ------ the answer to this problem (above) is all over the Web pages and Youtube.



For a few minutes, i thought this guy (below) had a solution that's ONE better than the standard correct answer (7 tries, --- 3,3,2 split or grouping)


He's just counting the tries (or [defining the prob.] ) differently.

The flashlight must actually turn on... So he'd still need the 7th try.


https://www.quora.com/You-are-given-a-flash-light-which-takes-2-good-batteries-to-run-and-8-batteries-4-good-ones-and-4-used-up-What-is-the-minimal-number-of-trials-needed-to-get-the-flashlight-running

Profile photo for Saish Datta Data Scientist 5y

I think we can do it in 6:

Try AB, BC and AC. If none of the pairs work at most one out of ABC is working.

That leaves at least three working among DEFGH.

Try DE, EF and DF. If none of the pairs work(1 out of DEF is working)then remaining 2 should work for sure.

henh...@gmail.com

unread,
Sep 12, 2022, 12:56:31 AMSep 12
to
(yes)
that's the (4-4) split or grouping, and the (5-3) split or grouping may require 13 moves.




flashlight-2 ( 5 batteries, 2 dead )
flashlight-2 ( 6 batteries, 3 dead ) are also interesting.

also ...
flashlight-3 ( 6 batteries, 2 dead )
flashlight-3 ( 7 batteries, 2 dead )
flashlight-3 ( 7 batteries, 3 dead )



i'm trying to think.... what another problem (genre) is similar to this
(a bit like Tower of Hanoi) in that you 're basically building up a table from Below,
and bigger problems use earlier (smaller) problem(s) as subroutines.

---------- is this how you typically solve the [Fox, Sheep across the river on a boat] puzzle ?


> Fox eats goose and goose eats corn if left alone. Farmer can row the boat himself and doesn't …


> A farmer is travelling with a fox, a sheep and a small sack of hay. He comes to a river with a small boat in it. The boat can only support the farmer and one other animal/item. If the farmer leaves …

Reply all
Reply to author
Forward
0 new messages