Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items
You are missing a condition – no two elements have exactly the same set of properties. Consider for example the extreme case in which no item has any properties – any query will get either all elements or none of them. We can also assume that $n&gt;1$.

A simple iterative procedure constructs such a query. Let the properties be $P_1,\ldots,P_k$.


Let $x_1$ be the setting of $P_1$ which maximizes the number of elements satisfying $P_1=x_1$.
Let $x_2$ be the setting of $P_2$ which maximizes the number of elements satisfying $P_1=x_1$ and $P_2=x_2$.
And so on.


Denote by $N_i$ the number of elements satisfying $P_1=x_1,\ldots,P_i=x_i$. Thus $N_0 = n$ and $N_k = 1$ (by the missing condition). Let $i&gt;0$ bet the minimal index such that $N_i &lt; 2n/3$ (such an index exists since $N_k=1 &lt; 2n/3$). Thus $N_{i-1} \geq 2n/3$. By construction, $N_i \geq N_{i-1}/2 \geq n/3$. It follows that $n/3 \leq N_i &lt; 2n/3$.