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 empty and and 15 are full) and then only way to test if the battery is full or empty is to put them in the Walkman and try it out. We cannot tell which one is empty or full if we put inside one full and one empty.
The question is to find the minimum needed step to run the walkman (to find 2 full batteries)
I modelledmodeled the problem like that : let s that the Walkman is a function f which take two arguments 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\}$$
Let the Walkman br a function $f$ which take two arguments and returns 1 if the walkman works, and 0 otherwise. $$ f\colon \{b_1,b_2 \dots b_{30}\} \times \{b_1,b_2 \dots b_{30}\} \rightarrow\{0,1\}$$
It gave meI was given a hint to use the Turán lemma;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} $$
When a graph $G=(V,E)$ with $V$ the vertex set and $|V|=n$ does not contain a $k$-clique with $k >1$, then $$ |E|\leq \left(1-\frac{1}{k-1}\right)\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 adversary argument I have to prove that the lower bound to find the battery must be 18, so any help how to solve this?
