Suppose $n$ coins are available that their mass is unknown. We have a pair of balances and every time we can choose an even number of coins and put half of them on one side of the balance and put another half on the other side, therefore a comparison will be done. Our aim is determining that the mass of all coins is equal or not. Show that at least $n-1$ comparisons are required.
Problem
Source: Iran TST 2006
Tags: combinatorics proposed, combinatorics
17.04.2006 17:05
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.
30.04.2006 12:28
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?
30.04.2006 13:38
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.
30.04.2006 19:20
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.