# How to solve this Yes/No query problem where we need to find the number of sets satisfying the given condition?

So let's say we have 2 people playing a game. Let the first person be $$A$$ and the second person be $$B$$. So $$A$$ guesses a number between $$1$$ and $$n$$ ( say $$x$$) and $$B$$ gives queries to $$A$$ in form of $$(L,R)$$ and $$A$$ will answer with $$Yes/NO$$ if the number exists in the interval $$(L,R)$$ both inclusive.

$$B$$ will need to ask a set of queries before he can uniquely determine the number $$x$$. So the problem is to find the number of such distinct sets of queries such that $$B$$ will be able to uniquely determine $$x$$, irrespective of what the value of $$x$$ was.

for example lets say $$n$$ is $$2$$. so the sets of queries would be,

{(1,1)}, {(2,2)}, {(1,1),(2,2)}, {(1,1),(1,2)},
{(2,2),(1,2)}, {(1,1),(2,2),(1,2)}


So the answer would be $$6$$. How do we solve this for $$n$$?

EDIT: So all I could think was the we need to basically isolate all the possible numbers from $$1$$ to $$n$$ in some way, otherwise it's not possible to uniquely determine the number. But I have no idea what to do with this information.

• Does $B$ know $n$? If so, why would he ever ask $(1,2)$? He already knows the answer to that is Yes.
– Jens
Oct 25, 2018 at 15:38
• @Jens Yes, B knows n. The question is not whether he asks (1,2) or not, it's about what set of queries would make sure that he can definitely figure out the x. Oct 25, 2018 at 18:22

This is an answer for just $$n=2$$. I'm going to write the intervals as $$[x,y]$$ for some $$x\le y$$ instead of $$(L,R)$$, since they're inclusive anyways, and queries as sequences of closed intervals. Then the set of distinct queries for $$n=2$$ is actually

$$Q_2=\Big\{([1,1]),([2,2]),\Bigg\vert([1,1],[1,2]),([1,1],[2,2]),([1,2],[1,1]),([1,2],[2,2]),([2,2],[1,1]),([2,2],[1,2]),\Bigg\vert([1,1],[1,2],[2,2]),([1,1],[2,2],[1,2]),([1,2],[1,1],[2,2]),([1,2],[2,2],[1,1]),([2,2],[1,1],[1,2]),([2,2],[1,2],[1,1])\Big\}.$$

The vertical lines separate $$1,2,3$$-tuples. The special thing about $$n=2$$ is that you know the number after any query containing $$[1,1]$$ or $$[2,2]$$. Since the only choices for closed intervals are $$[1,1],[1,2],$$ and $$[2,2]$$, any $$2$$-tuple (and thus $$3$$-tuple) must contain either $$[1,1]$$ or $$[2,2]$$, i.e. every $$2$$ or $$3$$-tuple determines the number.

The number of $$2$$-tuples is $$3\cdot 2=6$$ and the number of $$3$$-tuples is $$3!=6$$ so $$Q_2$$ has $$2+6+6=14$$ queries.

I don't know any method for $$n>2$$. Say $$n=3$$, then you don't have the easy symmetry anymore. For $$n=3$$, assume the number is in one of the three possible pairs $$(1,2),(1,3),(2,3)$$ and by the above, $$Q_3$$ has at least $$3(12)=36$$ queries. But since there are up to $$6$$-tuples for $$n=3$$, there are more than $$36$$ queries. I'm guessing if you find a formula for $$\lvert Q_3\rvert$$, you can generalize that for a formula of $$\lvert Q_{n+1}\rvert$$ from $$\lvert Q_n\rvert$$.