Batteries

The annoying part of this problem is that $a$ is hidden. The clean part is that we can use a strategy that works for every possible $a$ at once.

Place batteries $1,2,\dots,n$ around a circle in that order.

For a distance $d$, define a query pattern:

$$(j, j+d)$$

where indices wrap around modulo $n$. So for fixed $d$, we ask all $n$ pairs that are exactly $d$ steps clockwise apart.

The algorithm is just:

• try all pairs at distance $1$,
• then all pairs at distance $2$,
• then all pairs at distance $3$,
• and so on.

Stop immediately when the answer is 1.

Why this has to find a working pair

Suppose the true number of working batteries is $a$.

Take any valid configuration of $a$ working batteries and list them in clockwise order:

$$b_1,b_2,\dots,b_a.$$

Now look at the circular gaps between consecutive working batteries:

$$b_2-b_1,\ b_3-b_2,\ \dots,\ b_a-b_{a-1},\ b_1+n-b_a.$$

These $a$ gaps are positive integers, and together they wrap around the whole circle, so their sum is exactly

$$n.$$

Therefore, at least one gap is at most

$$\left\lfloor \frac n a \right\rfloor.$$

Otherwise, if all gaps were bigger than $\left\lfloor \frac n a \right\rfloor$, their sum would exceed $n$. Not happening.

So among the working batteries, there is some consecutive pair whose clockwise distance is at most

$$\left\lfloor \frac n a \right\rfloor.$$

Our algorithm tests every pair at distance $1$, then every pair at distance $2$, and so on. By the time it finishes distance

$$\left\lfloor \frac n a \right\rfloor,$$

it must have tested that consecutive working pair. The flashlight turns on, and we are done.

Why adaptivity does not break this

The interactor can adapt, but it still has to keep some configuration of exactly $a$ working batteries consistent with every 0 answer so far.

If the algorithm finished all distances up to $\left\lfloor \frac n a \right\rfloor$ with only 0s, then every valid set of $a$ batteries would have all circular gaps larger than $\left\lfloor \frac n a \right\rfloor$. But we just proved that is impossible.

So before or during that point, the interactor is forced to answer 1. The adaptive part sounds scary, but the circle gap argument pins it down anyway. Nice try, jury.

Query count

For each distance $d$, we ask exactly $n$ queries.

For the real value $a$, success happens by distance

$$\left\lfloor \frac n a \right\rfloor.$$

So the number of queries is at most

$$n\left\lfloor \frac n a \right\rfloor.$$

And since

$$\left\lfloor \frac n a \right\rfloor \le \frac n a,$$

we get

$$n\left\lfloor \frac n a \right\rfloor \le \frac{n^2}{a}.$$

The left side is an integer, so

$$n\left\lfloor \frac n a \right\rfloor \le \left\lfloor \frac{n^2}{a} \right\rfloor.$$

That is exactly the required limit.

Complexity

At most $n(n-1)$ possible directed distance queries are attempted, and $n\le 40$, so this is tiny. The real limit is the interactive query bound, and we satisfy it.