سوال ۶۱ کنکور ارشد علوم کامپیوتر ۱۴۰۵

This is an adversary (worst-case) argument. We must decide whether $A$ is Kind 1 (exactly $\frac{n}{2}$ zeros and $\frac{n}{2}$ ones) or Kind 2 (exactly $\frac{2n}{3}$ zeros and $\frac{n}{3}$ ones) by probing individual bits.

Suppose we have probed some cells and seen $a$ ones and $b$ zeros. The observations stay consistent with each kind as long as the seen counts do not exceed that kind's totals:

• Consistent with Kind 1 iff $a \le \frac{n}{2}$ and $b \le \frac{n}{2}$.
• Consistent with Kind 2 iff $a \le \frac{n}{3}$ and $b \le \frac{2n}{3}$.

Both kinds remain possible as long as the tighter bound on each bit value holds, namely $a \le \frac{n}{3}$ and $b \le \frac{n}{2}$.

Adversary strategy. For each probe, answer $1$ while $a < \frac{n}{3}$ and answer $0$ while $b < \frac{n}{2}$, keeping both kinds alive. This can be sustained for

$\frac{n}{3} + \frac{n}{2} = \frac{2n+3n}{6} = \frac{5n}{6}$

probes (reaching $a=\frac{n}{3},\; b=\frac{n}{2}$). After exactly $\frac{5n}{6}$ probes the observations are still consistent with both kinds, so no algorithm can decide yet.

One more probe forces the answer. At the state $a=\frac{n}{3},\, b=\frac{n}{2}$ there are $n-\frac{5n}{6}=\frac{n}{6}$ unprobed cells. For Kind 1 every one of them must be a $1$ (we still need $\frac{n}{2}-\frac{n}{3}=\frac{n}{6}$ ones and $0$ more zeros); for Kind 2 every one must be a $0$ (we still need $\frac{2n}{3}-\frac{n}{2}=\frac{n}{6}$ zeros and $0$ more ones). So the very next probe returns $1 \Rightarrow$ Kind 1, or $0 \Rightarrow$ Kind 2 — either way the kind is now certain.

Hence the worst case requires

$\frac{5n}{6} + 1$

probes, which is option 4.

Exam trick: In a two-hypothesis identification problem, the ambiguous region lasts while the counts respect the tighter bound on each symbol ($a\le \frac{n}{3}$, $b\le \frac{n}{2}$); sum those to $\frac{5n}{6}$, then add the single decisive probe: $\frac{5n}{6}+1$.