lower bound proof with adversary argument

Question

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 modeled the problem like that :

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\}$$

I was given 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$, 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?

Answer 1

Here comes $A$ (is it Apass?), the simple smart adversary Walkman.

For the first 18 pairs of batteries you put into $A$ to test, $A$ will just not operate. So you will need at least 18 tests before finding 2 full batteries. On the other hand, the accepted answer to another question by OP shows 18 tests is enough. So the desired lower bound is 18 tests.

The real question is, of course, does this behavior of $A$ come from an actual combination of batteries regardless of whichever 18 pairs of batteries are chosen to be tested?

The answer is yes.

Instead of proving for the case of 30 batteries and 18 tests, let us prove the general cases, which is actually easier since we can use mathematical induction.

(Consistency of $A$) Let $n\ge2$ be a positive integer. $S=\{\{i,j\}\mid 1\le i\lt j\le 2n\}$ with $\#|S|\le n+3$. Let $B=\{i\mid1\le i\le 2n\}$. Then there exists a function $f: B\to \{0,1\}$ such that $|f^{-1}(0)|=n$ (and hence $|f^{-1}(1)|=n$ as well) and for each $\{i,j\}\in S$, if $f(i)\ne 0$, then $f(j)=0$ (If we interpret 0 as an empty battery, this means no pair in $S$ will make $A$ operate).

Proof by induction on $n$

• $n=2$. $|S|\le5$. Since there are 6 different pair of numbers can be drawn from $\{1,2,3,4\}$, there is one pair of numbers which is not in $S$. WLOG, let that pair of numbers be 1 and 2. Let $f(1)=f(2)=1$ and $f(3)=f(4)=0$. Case proved.

• Suppose it is true for $n$. Let us consider the case of $n+1$, where $S'=\{\{i,j\}\mid 1\le i\lt j\le 2(n +1)\}$ with $\#|S'|\le(n+1)+3$ and $B'=\{i\mid1\le i\le 2(n+1)\}$.
  Since $\#|S'|=n+4$ and each element of $S'$ has two numbers, the total number of appearances of numbers in all elements of $S'$ is $2(n+4)$, which is smaller than the double of $2(n+1)$. So there must be one number that appears less than 2 times. WLOS, let that number be $2n+2$. There are two cases.

  • If $2n+2$ appears in $\{j, 2n+2\}\in S'$ for some $j$, WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.
  • If $2n+2$ does not appear in any element of $S'$, choose any element $j$ that appear at least once in some element of $S$. WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.

  Consider $S=\{\{i,j\}\in S'\mid 1\le i\lt j\le 2n \}$. Since either $2n+2$ or $2n+1$ appears in one of elements of $S'$, $\#|S|\le\#|S'|-1\le n+3$. By induction hypothesis, we can define $f$ on $B$ such that $f^{-1}(0)=n$. Extend $f$ by letting $f(2n+2)=1$ and $f(2n+1)=0$. Now we can see that $f^{-1}(0)=n+1$ and for each $\{i,j\}\in S'$, if $f(i)\ne 0$, then $f(j)=0$, thus concluding our proof.

---

Apparently, Turán lemma is not needed if it can be useful here at all.

---

Here are several related exercises I designed for the interested readers.

Exercise 1. Check that the original question is the case when $n=15$.

Exercise 2. Verify the last statement of the above proof.

Exercise 3. (the case of 3 batteries) Another Walkman needs 3 full batteries to operate. Let's say we have a mixed set of 30 batteries, 20 of which are empty and the remaining 10 of which are full. The only way to test whether a battery is full or empty is to put 3 of them in the Walkman and try it out. However, we can not tell which one is empty or full when the Walkman does not operate. What is the minimum number of tests that guarantees to identify 3 full batteries? Prove your answer.

Exercise 4. What is the average number of steps for the testing strategy shown here? Can we do better (this last question is a research topic)?