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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .