Brazilian Math Olympiad question about batteries and a torch

Question

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).

Answer 1

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$.