Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:
- If one of the sets is bigger than the other, we say that its sum is larger.
- If the two sets have equal size, we say that their sums are equal.
We can represent each comparison as a vector of length $n$: the comparison $\sum_{i \in A} w_i \gtrless \sum_{i \in B} w_i?$ (where $w_i$ are the weights) corresponds to the vector $1_A - 1_B$, i.e., the vector having value $1$ at the $A$-coordinates, having value $-1$ at the $B$-coordinates, and having value $0$ elsewhere.
Let $\mathbf{x}_1,\ldots,\mathbf{x}_m$ denote the vectors corresponding to comparisons of sets of equal size (so $m < n-1$), and let $\mathbf{1}$ be the constant $1$ vector. Since $m+1 < n$, there is a non-zero vector $\mathbf{v}$ orthogonal to all of $\mathbf{x}_1,\ldots,\mathbf{x}_m,\mathbf{1}$. We can assume that $|v_i| \leq 1$ for all $i$.
Consider the vector $\mathbf{w}_\delta = \mathbf{1} + \delta \mathbf{v}$, where $|\delta| < 1/n$. It is not hard to check that $\mathbf{w}_\delta$ is consistent with our replies to the algorithm. Yet $\mathbf{w}_\delta$ and $\mathbf{w}_{-\delta}$ have different maximal values, so the algorithm will make a mistake on at least one of them.
This argument even works when we are allowed to ask arbitrary queries of the form $\operatorname{sgn}(\sum_i x_i w_i)$.
