You have 50 coins which each weigh either 20 grams or 10 grams. Each is labelled from 0 to 49 so you can tell the coins apart. You have one weighing device as well. At the first turn you can put as many coins as you like on the weighing device and it will tell you exactly how much they weigh.
However, there is something strange about the weighing device. If you put coins $x_1, x_2, ..., x_j$ on the device the first time, then you have to put coins $(x_1+1) \bmod 50, (x_2+1) \bmod 50, ..., (x_j+1) \bmod 50$ on the scale the next time, and coins $(x_1+2) \bmod 50, (x_2+2) \bmod 50, ..., (x_j+2) \bmod 50$ the next time and so on. In other words, all the weighings are defined by the choice of coins you choose to weigh the first time.
Under this rule, what is the smallest number of weighings that will always tell you exactly which coins weigh 10 grams and which weigh 20?
Clearly you could just put one coin on the device in the first turn and then it would take exactly $50$ weighings to solve the problem.
Here is an example when you have only $4$ coins that takes only $3$ weighings. First put coins $1$,$2$ and $3$ on the scale. For the next weighing you will have coins $0$, $2$ and $3$. For the last weighing you will have coins $0$, $1$ and $3$ and you will then know exactly which coins are real and which are fake.
Here is another example when you have $9$ coins that takes only $6$ weighings. First put coins $2,5,7,8$ on the scale (indexing from $0$ again).
Answers so far (smaller is better)
- 38 by san
- 35 by Tad
- 31 by Tad
- 26 by joriki
- 25 by joriki (A very impressive record!)
For $n\gt3$ the least number of weighings is $n-1$. All versions use the combinations of $n-1$ coins missing one, and a repeated weighing of the remaining coin.
If we analyse the original example, we can add up the total of the $3$ weighings. This gives us:
$2\times$(weight of coin $0$+weight of coin $1$+weight of coin $2$) $+3\times$weight of coin $3$. (I have used weights of $1$ and $2$ instead of $10$ and $20$.)
The sum of the first $3$ coins is from $\{3,4,5,6\}$ and so may take the values $\{6,8,10,12\}$, and the final coin provides either $3$ or $6$, giving the final set of possible weighings as $\{9,11,13,15,12,14,16,18\}$, or sorted: $\{9,11,12,13,14,15,16,18\}$.
So we take the $3$ weighings and add up the totals. Now because we have an even number of the first $3$ coins, we can determine the weight of the last coin as odd or even. This value can be removed from the original equations giving $3$ equations in $3$ unknowns, which have a solution.
For example if our three weighings give $5,5,6$, the totals weight is $16$. If the final coin weighed $1$, we would have $2\times(c_0+c_1+c_2)=13$, which is impossible. We infer the final coin must weigh $2$, so we have:
$$ c_0+c_1=3$$ $$ c_0+c_2=3$$ $$ c_1+c_2=4$$
which has the unique solution $c_0=1, c_1=2, c2=2$.
To generalize this, we can see that a solution set comes from:
$$(n-2)\{n-1,\dots,2n-2\}+(n-1)\{1,2\}$$
A possible weighing is unique modular $(n-2)$, and so we can determine the weight of the last coin by leaving a total weighing $0\mod(n-2)$, which leaves $(n-1)$ equations in $~(n-1)$ unknowns, which has a unique solution.
For example, with $5$ coins, we have the possible weights $\{4,5,6,7,8\}$ from the $4$ coins, and the total weighing is $3\times(c_0+c_1+c_2+c_3)+4\times c_4$. So the final total weighing will be either $3k+1$ or $3k+2$, telling us the value of $c_4$.
Because the range of coin wieghts is limited, a solution with more coins can often be achieved with less weighings than this. The variables are the number of coins used in weighings, the number of weighings and the possible weights of the coins.