we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full) and then only way to test if the battery full or empty is to put them in the Walkman and try it out.we can not tell which one is empty or full (one we put inside one full and one empty).

The question is to find the minumum needed step to run the walkman (to find 2 full batteries)

I modelled the problem like that : let s that the Walkman is a function f which take two argumments and it return 1 it the walkman works ,and 0 otherwise. $$ f: \{b_1,b_2 \dots b_{30}\} \times \{b_1,b_2 \dots b_{30}\} \rightarrow\{0,1\}$$

It was given me a hint to use the Turán lemma;

when a graph G=(V,E) with V the vertex set and|V|=n does not contain a K-clique with $k >1 $ $$ |E|\leq (1-\frac{1}{k-1})\frac{n^2}{2} $$

The idea was to consider the batteries as vertex and create a Complete graph and then when $ f(b_i,b_j)=0$ we delete the edge between $b_i$ and $b_j$

using the adversay argument i have to prove that the lower bound to find the battery must be 18, so any help how to can solve this ?