3
$\begingroup$

Let $A=\{0,1\}^n=\{(a_1,a_2,\ldots,a_n)\mid a_i\in\{0,1\}\}$. Let $B\subseteq A$ be such that if $(b_1,b_2,\ldots,b_n)\in B$,$ (c_1,c_2,\ldots,c_n)\in A$, and $c_i\leq b_i$ for all $i$, then $(c_1,c_2,\ldots,c_n)\in B$.

You want to find out $B$. You may ask a number of queries, one after another, whether an element belongs to $B$ or not. What is the minimum number of queries you need to ask to find out $B$?

(For example: $n=2$. You first ask $(1,0)$. If it belongs to $B$, you know $(0,0)$ also belongs to $B$, and then you ask for $(0,1)$ and $(1,1)$. Else, if $(1,0)$ doesn't belong to $B$, you know $(1,1)$ also doesn't belong to $B$, and then you ask for $(0,1)$ and $(0,0)$. Hence you can find out $B$ in $3$ queries with this strategy.)

$\endgroup$
1
  • $\begingroup$ i read too quickly and oversimplified the problem. my answer was based on the assumption that B is an ideal, so that one needed to find the supremum. however i see now that this may not be unique. i will delete the answer lest it lead others astray. apologies $\endgroup$ Oct 23, 2014 at 19:26

1 Answer 1

3
$\begingroup$

$$\Omega(2^{n/2})$$

Let $C$ be the set of all elements $(a_1, \ldots, a_n) \in {0, 1}^n$ such that $\sum a_i = n/2$ (that is, exactly half of its elements is $1$). There are $\binom{n}{n/2} = \Omega(2^{n/2})$ such elements.

Consider the following $B$:

  1. It contains all $(a_1, \ldots, a_n) \in {0, 1}^n$ if $\sum a_i < n / 2$.
  2. Each element of $C$ is in $B$ independently with $1/2$ chance.

From these properties, it is clear that the nice subset property is satisfied. The problem is, the subsets included in all $B$ are the same, so the only way to detect the members of $C$ that is in $B$ is to ask each of them. Thus, we require at least $|C|$ queries to get $B$ exactly.

$\endgroup$
2
  • $\begingroup$ Is it true that $\binom{n}{n/2} = \Omega(2^n)$? $\endgroup$
    – boaten
    Oct 24, 2014 at 15:12
  • $\begingroup$ No no, I was wrong. It's $\Omega(2^{n/2})$. Point is we require exponential amount of queries. $\endgroup$
    – Irvan
    Oct 24, 2014 at 15:48

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.