What is the minimum number of questions to find the ring

Question

There are 11 rings around a circle numbered from 1 to 11. We know that exactly 9 of them are fake and exactly 2 of them are real rings. In each step, we can choose 5 consecutive rings and ask the number of real rings in that range.
What is the minimum number of questions that we need to ask to determine a real ring?

Answer 1

Let $r_1, ..., r_{11}$ be all different 11 rings, ordered by indices. There are 2 rings $r_i$ and $r_j$, with $i\neq j\in\{1,...,11\}$, that are real and the rest is fake. Select 5 consecutive rings. Now there are 3 cases.

Case 1 Suppose that we've picked 5 fake rings. This implies that the other 6 rings must contain the real rings. Again, pick 5 rings from the other 6 we did not already ask. Note that there must be at least 1 real ring in this new collection of rings. Now we have 2 subcases:
Subcase 1.1 If we now know that there must be 1 real ring in our last selection, we immediately know that the 1 ring we didn't choose must be a real one and we're done in 2 steps.
Subcase 1.2 If there were 2 real rings in our last selection,then we must apply a 'smart' algorithm. Say we now have $r_3, ..., r_7$ as our selection containing 2 real rings. Let's pick $r_4, ..., r_8$ and assume the worst case scenario: still 2 real rings ($r_3$ was fake). Then we take $r_5, ..., r_9$ and again assume worst case. Persume with $r_6, ..., r_{10}$ and now you know either $r_5$ is a real ring or both $r_6$ and $r_7$ are real rings, it depends on the answer (what answers?).
Case 1 took us 5 steps.

Case 2 We have picked a sequence containing 2 rings. Apply the algorithm from case 1.2.
Case 2 took us 3 steps.

Case 3 There's only 1 real ring. Apply case 1.2's algorithm. It takes at most 5 steps from now to find a real ring. Since we're looking for the worst case scenarios to determine the minimal steps it takes us to know with 100% certainty where at least 1 real ring is positioned, we apply this algorithm. Of course, we can produce a smarter algorithm for which the chance of picking a ring-sequence is bigger. But for now, we assume that we want to know the minimal amount of steps for finding a real ring in every case. Worst cases included. The very worst case is when $r_1$ and $r_6$ are real rings. If we chose rings $r_1, ..., r_5$ and thereafter rings $r_2, ..., r_6$, then we still got 1 real ring. Then continue the algorithm and it will take 6 steps in total to have found that ring. Case 3 took us 6 steps.

We conclude that the minimal steps necessary for finding a real ring (when every possible case is considered) is 6.

Special case It may happen to be 2 steps (to find a real ring) in the best case: select $r_1, ..., r_5$ and it contains 1 ring. Now select $r_6, ..., r_{10}$ and it contains no ring $\rightarrow r_{11}$ is a real ring.

Answer 2

I believe the OP's various comments are all correct. Therefore I cannot claim any credit for this answer, but I'm just writing it out more fully for the record, so that others can scrutinize it better.

Necessity: 8 queries are not enough for a win, because: an adversary can answer "1" to any 8 queries, and still have multiple solutions available where no location is guaranteed to have a real ring.

Let $Q_j$ denote the number of real rings in the range $\{j, j+1, j+2, j+3, j+4\}.$ (Obviously all indexing are mod $11$.) After 8 queries, let $Q_a, Q_b, Q_c$ be the 3 queries not asked, where $a,b,c$ are all distinct.

After answering "1" to the 8 queries, the answers so far are consistent with these 3 scenarios:

• $Q_a = 0, Q_b=Q_c=1,$ the real rings are at locations $R_a = \{a-1, a+5\}$.

• $Q_b = 0, Q_a=Q_c=1,$ the real rings are at locations $R_b = \{b-1, b+5\}$.

• $Q_c = 0, Q_b=Q_a=1,$ the real rings are at locations $R_c = \{c-1, c+5\}$.

The crucial observation is that $R_a \cap R_b \cap R_c = \emptyset.$ (Suppose on the contrary there is a common element, e.g. $x=a-1 = b+5 = c-1$, but this is impossible because $a\neq c$. Any "assignment" of the common $x$ to the $2^3$ choices result in a similar contradition.)

Because $R_a \cap R_b \cap R_c = \emptyset$, there is no location guaranteed to be a real ring. (To be even more explicit: any guessed location $x$ would satisfy $x \notin R_e$ for some $e \in \{a,b,c\}$, i.e. the adversary can claim $x$ is a fake ring by claiming that the real rings are at $R_e$.)

This proves that 8 queries are not enough for a win.

Sufficiency: Meanwhile, with a 9th query, we have only two unasked queries $Q_a, Q_b$ and, as the OP also pointed out, if we make sure $a+6=b$ (e.g. the unasked queries are $Q_1, Q_7$), then $a+5 \in R_a$ and $a+5 = b-1 \in R_b$ so that must be a real ring.

Therefore the optimal answer is 9.