Battery Optimization

Hi all,

Suppose we have nn batteries, gg good ones, and a flashlight that takes cc batteries. And you don't know which are the bad ones.

And, let f(n,g,c)=f(n,g,c) = The minimum number of attempts (insertions of cc batteries into the flashlight) you need in order to get your flashlight working.

And assume that the only way the flashlight will work is if all cc batteries you put in the flashlight are good. Otherwise, it won't work, and there is no way to distinguish between any combination that contains one or more bad batteries.

What I am wondering is how to show/prove the general solution for f(n,g,c)f(n,g,c).

We have a few trivial cases:

  • f(n,g,1)=ng+1f(n,g,1) = n - g +1
  • f(n,g,g)=(ng)f(n,g,g) = \binom{n}{g}
  • f(n,n,c)=1f(n,n,c) = 1
  • f(4,3,2)=2f(4,3,2) = 2

So, I think the first non-trivial case becomes:

  • f(5,3,2)f(5,3,2)

This one can be done in four moves, (1 vs 2, 3 vs 4, 4 vs 5, 3 vs 5) but can we prove that it can't be done in fewer?

And, does anyone have any idea about how we can solve this problem for the general case?

Thanks!

Geoff

Note by Geoff Pilling
2 years, 9 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

@Brian Charlesworth In a previous thread you had suggested that for f(n,3,2)f(n,3,2) you might want to split the group into two, one of which is guaranteed to have two good batteries, and run through each of the combinations in each group, giving:

f(2n,3,2)=2(n2)f(2n,3,2) = 2\dbinom{n}{2} and f(2n+1,3,2)=(n2)+(n+12)f(2n + 1,3,2) = \dbinom{n}{2} + \dbinom{n + 1}{2}

One generalization of that for g>3g>3 might be to split up the batteries into the greatest number of groups (g1g-1?) such that at least one is guaranteed to have at least two good batteries and then go through all the combinations in each group. Without showing that this is the best approach, it certainly seems like a promising one.

So, for example if we take g=4g=4, then we would split into 3 groups, yielding:

f(8,4,2)=(22)+(32)+(32)=1+3+3=7f(8,4,2) = \binom{2}{2} + \binom{3}{2} + \binom{3}{2} = 1 + 3 + 3 = 7

So for f(100,50,2)f(100,50,2) we would have:

f(100,50,2)=2(32)+47(22)=53f(100,50,2) = 2\binom{3}{2} + 47\binom{2}{2} = 53

Recognize that answer? :0)

A couple more examples using the above algorithm gives:

  • f(100,10,2)=8(112)+(122)=506f(100,10,2) = 8\binom{11}{2} + \binom{12}{2} = 506
  • f(100,25,2)=4(52)+20(42)=160f(100,25,2) = 4\binom{5}{2} + 20\binom{4}{2} = 160

@Calvin Lin Thoughts on how one might go about proving that these could be optimal approaches (outside of using a computer)?

Geoff Pilling - 2 years, 9 months ago

Log in to reply

Once you summarize the approach it does look quite promising. :)

As far as I can tell, with f(n,g,2)f(n,g,2) your goal is to form the sum

a(ng12)+b(ng1+12)a\dbinom{\lfloor\frac{n}{g - 1}\rfloor}{2} + b\dbinom{\lfloor\frac{n}{g - 1}\rfloor + 1}{2}

so as to maximize aa given a+b=g1a + b = g - 1.

I can see one other approach to get f(100,10,2)=506f(100,10,2) = 506, where we have 99 groupings of 1111 and one singleton left over. Then if after 9(112)=4959\binom{11}{2} = 495 tests with no success we can conclude that the singleton is good and that each of the 99 groups has one good battery as well. So we then choose one of these groups and pair all 1111 in the group with the good singleton to finally get a working pair after a grand total of 495+11=506495 + 11 = 506 trials. This isn't an improvement but it does suggest that the g1g - 1 paradigm may not be exclusively optimal.

Brian Charlesworth - 2 years, 9 months ago

Log in to reply

Without a proof, I suspect that the general solution for f(n,g,c)f(n,g,c) might be given by this:

1) Divide the nn batteries up into the maximum number of groups you can (minimizing the maximum number for any group) so that at least one group contains at least cc batteries. I think this number is given by:

  • Number of groups =g1c1= \lfloor {\frac{g-1}{c-1}} \rfloor

2) Perform all possible iterations within each group.

So, for example, for f(100,50,3)f(100,50,3) you would split it up into 2020 groups of 44 and 44 groups of 55, guaranteeing that at least one group has 33.

    f(100,50,3)=20(43)+4(53)\implies f(100,50,3) = 20\binom{4}{3} + 4\binom{5}{3}

@Brian Charlesworth @Calvin Lin

Geoff Pilling - 2 years, 9 months ago

Log in to reply

@Geoff Pilling That looks good. The values ramp up quite quickly with cc, with

f(100,50,4)=12(64)+4(74)=320,f(100,50,5)=8(85)+4(95)=952f(100,50,4) = 12\binom{6}{4} + 4\binom{7}{4} = 320, f(100,50,5) = 8\binom{8}{5} + 4\binom{9}{5} = 952

and f(100,50,6)=8(116)+(126)=4620f(100,50,6) = 8\binom{11}{6} + \binom{12}{6} = 4620.

We could probably write out a messy general formula now but I think the description of the process suffices. The optimization proof remains elusive, however ...

Brian Charlesworth - 2 years, 9 months ago

Log in to reply

Yes. Looks like a good generalization/summary for c=2c=2... Now we just gotta figure out a proof and/or generalize it for c>2c>2... Hmmmm....

Geoff Pilling - 2 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...