0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Does $B$ know $n$? If so, why would he ever ask $(1,2)$? He already knows the answer to that is Yes. $\endgroup$
    – Jens
    Oct 25, 2018 at 15:38
  • $\begingroup$ @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. $\endgroup$
    – aroma
    Oct 25, 2018 at 18:22

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

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