0
$\begingroup$

This question comes from the 27th Brazilian Mathematical Olympiad (2005).

We have four charged batteries, four uncharged batteries, and a radio which needs two charged batteries to work. We do not know which batteries are charged and which ones are un harged. What is the least number of attempts that suffices to make sure the radio will work? (An attempt onsists of putting two batteries in the radio and cheking if the radio works or not).

$\endgroup$
4
$\begingroup$

Consider the graph whose vertices are batteries and whose edges correspond to pairs of charged batteries. The edges form a $K_4$ clique, so the question becomes

What is the smallest number of edges in an $8$-vertex graph whose complement contains no $K_4$ clique?

We answer this by considering its dual:

What is the largest number of edges in an $8$-vertex graph with no $K_4$ clique?

By TurĂ¡n's theorem, the answer to this dual question is $K_{3,3,2}$, which has $21$ edges. Thus, the least number of trials we need is the number of edges in $K_8$ minus this, or $28-21=7$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ good answer to a crap question. I'm conflicted with my desire to not upvote answers on questions that should clearly be deleted, but also my desire to support quality solution methods $\endgroup$ – Brevan Ellefsen Aug 15 '19 at 5:33
  • 2
    $\begingroup$ @Brevan Ellefsen: Then the question (which I thought was an interesting one) added value to MSE by provoking a novel answer. $\endgroup$ – quasi Aug 15 '19 at 5:47
  • 3
    $\begingroup$ You might also try and translate the idea into high school math contest language. Split the collection of 8 batteries into three groups:3+3+2. One of those groups will have two charged batteries, so testing $\binom 32+\binom 32+\binom21=7$ pairs suffices. Of course, it does not follow that 7 is optimal. Leaving that as an exercise :-) $\endgroup$ – Jyrki Lahtonen Aug 15 '19 at 6:17
  • 1
    $\begingroup$ @JyrkiLahtonen Well, you just translated my answer into high-school language, except for the Turán part, I guess... $\endgroup$ – Parcly Taxel Aug 15 '19 at 6:23
  • 1
    $\begingroup$ @JohnBentin By the rules of this question, that would be $8$ trials. $\endgroup$ – Parcly Taxel Aug 15 '19 at 6:44

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