Hidden Single (Version 2)

This is an interactive randomized solution. The important detail is that the interactor is not adaptive: the hidden array is fixed before our queries. So random partitions behave like actual random partitions, not like some evil wizard moving the answer around after every query.

First cut: shrink the problem hard

Let $M = 2n-1 = 599$. Randomly shuffle the positions and split them into two parts $L$ and $R$ of sizes $299$ and $300$.

For every value $x$:

• Ask whether $x$ appears in $L$.
• If yes, also ask whether $x$ appears in $R$.

Now $x$ is classified as:

• split: appears in both sides, so it is definitely not the singleton;
• left-only: appears only in $L$;
• right-only: appears only in $R$.

Here is the Version-1 parity/count trick. Pretend every value appears twice. Then:

• a split value contributes $1$ fake element to each side;
• a left-only value contributes $2$ fake elements to $L$;
• a right-only value contributes $2$ fake elements to $R$.

For every normal value this fake count matches reality. For the singleton, the fake count overcounts its side by exactly $1$, because the singleton has one real occurrence but we pretend it has two.

So exactly one side has predicted size = real size + 1. That side contains the singleton. Keep that side as pool, and keep only the values that were wholly inside it as candidates.

Why is this good? For a doubled value, both copies land in the same random half with probability about $1/4$. So after one split, the candidate list is usually about $n/4$, around $75$ values. The first layer costs about $n + 3n/4 = 525$ queries.

How to reject one candidate cheaply

Now take one candidate $x$. We know all real occurrences of $x$ are inside pool:

• if $x$ is the answer, it has one occurrence in pool;
• otherwise, it has two occurrences in pool.

Shuffle pool once. We run a binary-search-like procedure on this order.

Maintain a segment that contains all occurrences of $x$. Split it into two halves $A$ and $B$.

• Ask whether $x$ appears in $A$.
• If no, then all occurrences are in $B$, so continue with $B$.
• If yes, ask whether $x$ appears in $B$.
• If yes too, then $x$ appears on both sides, so $x$ is doubled and rejected.
• If no, then all occurrences are in $A$, so continue with $A$.

If we reach a segment of size $1$, then $x$ must be the singleton. A doubled value cannot fit two different positions into one leaf; it would have been split at some earlier binary partition. Brutal, clean, done.

Expected query count

For a doubled candidate at a balanced split:

• with probability about $1/2$, its two copies split between the halves, costing $2$ queries and finishing;
• with probability about $1/4$, both are in the right half, costing $1$ query and continuing;
• with probability about $1/4$, both are in the left half, costing $2$ queries and continuing.

So if $E$ is the expected number of queries to reject a doubled candidate,

$E = (1/2) \cdot 2 + (1/4) \cdot (1 + E) + (1/4) \cdot (2 + E) = 7/2$.

The true singleton reaches a leaf, costing at most about $2\lceil \log_2 300 \rceil$ queries. We also shuffle the candidate order, so on average we find the singleton before checking all candidates.

Correctness

The first phase keeps the correct side because only the singleton causes the fake doubled-count to exceed the real side size by $1$.

Every value not wholly inside that side cannot be the singleton: if it appears on both sides, it has at least two occurrences; if it is wholly outside, it is obviously irrelevant.

For each remaining candidate, the binary procedure is exact: a doubled value is rejected once its two positions fall into different halves, while the singleton never appears in both halves. Therefore the first candidate that reaches a leaf is exactly the hidden single.

Randomness only controls the query count, not the logical correctness once the queries are answered. Since the hidden array is fixed and $n=300$, this stays under the $925$-query cap with very high probability.