Let $x_1,\ldots,x_n$ be the masses of the coins. A comparison tells us whether $x_{a_1}+\ldots+x_{a_k}-(x_{b_1}+\ldots+x_{b_k})=0$ or not for some subset $\{a_i\}\cup\{b_j\}\subset\overline{1,n}$. Suppose we make $n-2$ comparisons. We want to prove that there can be two different situations, one in which all $x_i$ are equal and one in which they are not, which cannot be distinguished by the $n-2$ comparisons. These $n-2$ comparisons give us a homogeneous linear system with $n$ unknowns and $n-2$ equations, so its solution space has dimension $\ge 2$. This means that in addition to the family of solutions given by $x_1=x_2=\ldots=x_n$, it must have other solutions as well, and this is what we wanted.

what i dont understand is: why cant the exact same argument work to show that we need at least n-1 comparisions? since then we would have a solution space of 1, which is still not good enough since we can still have infinitely many solutions, i.e. if we have 2 equations and 3 unknowns we have infinitely many solutions over the reals. and what happens if you make one comparison and it turns out they are unequal? it straight away gives you the answer no and it takes 1 comparision .. so i think the correct version of the problem is: suppose a set of n masses are equal but we dont know that yet. at least how many comparisions does it take to confirm that they are equal?

epitomy01 wrote: what i dont understand is: why cant the exact same argument work to show that we need at least n-1 comparisions? since then we would have a solution space of 1, which is still not good enough since we can still have infinitely many solutions, i.e. if we have 2 equations and 3 unknowns we have infinitely many solutions over the reals. and what happens if you make one comparison and it turns out they are unequal? it straight away gives you the answer no and it takes 1 comparision .. so i think the correct version of the problem is: suppose a set of n masses are equal but we dont know that yet. at least how many comparisions does it take to confirm that they are equal? At least $n-1$ comparisons means that for the worst case we need $n-1$ comparisons, and it turns out where they are all equal is the worst case. But the problem statement is correct.

Being equal = infinitely many solutions as you can never pin down the weight of one particular coin, so a 1-dimensional solution space is what you want.