1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Your question is well written. I would like us to pay attribute to the original source. If it comes from an online programming contest or course, could you please add a URL? If it comes from a book or a paper, a reference. All that information also motivates and helps people answer the question faster and better. Please add those information in the question since people and search engine are not expected to look at comments. (You did not provide url nor reference in the other question about the same or a similar problem, either.) $\endgroup$ – Apass.Jack Oct 22 '18 at 14:19
  • 1
    $\begingroup$ In fact, you should also add an reference to the other question of yours that is about the same or a similar problem, where you have got a nice answer. That will save time and effort of people who want to answer your question, thus helping you better and faster. You are certainly not here to test the collective competence of CS users by holding back useful information, right? :) $\endgroup$ – Apass.Jack Oct 22 '18 at 14:24
  • $\begingroup$ Actually that question was an assignment from my universtiy, and to access the pdf file is unfortunately private and not written in english $\endgroup$ – Mohbenay Oct 22 '18 at 15:39
  • 1
    $\begingroup$ Thanks for the info. To forestall similar inquiries next time, you might add those negative access info in your later questions. Even if you have enough reputation, people may still ask you for those reference if you have not included them, considering you might just forget. $\endgroup$ – Apass.Jack Oct 22 '18 at 16:48
  • $\begingroup$ How far have you made on the adversary argument? Is your adversary designed by you able to enforce 15 queries? 16 queries? 17 queries? $\endgroup$ – Apass.Jack Oct 22 '18 at 16:52
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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