6
$\begingroup$

We are given 100 bags, each with 200 coins. All but one of the bags are filled with identical gold coins, but the other bag contains fake coins. The fakes all weigh the same as each other, but weigh different than a true gold coin. Both of these weights are unknown.

We have a digital scale. How can you identify the fake bag with a minimum number of weighings?

$\endgroup$
  • $\begingroup$ I'm sure that this has been asked before, but the "Related" section is only pulling up variations on the problem. $\endgroup$ – phroureo Nov 9 '17 at 19:39
  • 2
    $\begingroup$ @phroureo The most similar one appears to be this. $\endgroup$ – Apep Nov 9 '17 at 19:51
  • 1
    $\begingroup$ While I did point out that the other question is similar, the fact that the weights need to be discovered makes it a distinct question, in my opinion. $\endgroup$ – Apep Nov 9 '17 at 21:12
  • 3
    $\begingroup$ @Rubio “Ignore” is the wrong word, Tom meant the weights of the true and fake coins are both unknown. This makes the puzzle quite nontrivial. (If the true weight were known, but the fake was unknown, then it would be only more trivial weighing needed). I know because I had fun solving it and have an interesting solution... I’ll edit to clarify, I really hope this can be reopened since it is a genuinely new and interesting puzzle. $\endgroup$ – Mike Earnest Nov 10 '17 at 13:48
  • 1
    $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$ – Rubio Nov 27 '17 at 1:49
4
$\begingroup$

Numbering the bags from 1 to 100, here is the weighing strategy:

You can succeed using three weighings, and cannot succeed in two:

1. Weigh one coin from each bag.
2. Weigh $i$ coins from the $i^{\,\text{th}}$ bag, for $i=1,2,\dots,100$.
3. Weigh a single coin from bag 51.

To deduce the true bag, let...

  $t$ be the weight of a true coin.
  $\delta$ be the difference between weight of a fake and true coin.
  $i$ be the index of the bag which is full of fakes.
  $W_k$ be the outcome of $k^{\,\text{th}}$ weighing.

The weighings give us the following system of equations:

$$\begin{align}W_1&=100t+\delta&\\W_2 &= 5050t+i\delta \\W_3 &= \begin{cases}t & i\neq 51\\t+\delta&i=51\end{cases}\end{align}$$

You can then check that

$$ \frac{5050W_1 - 100W_2}{\hspace{1cm}W_1 - 100W_3} = \begin{cases}5050-100i & i\neq 51\\\frac{50}{99}&i=51\end{cases} $$

Finally, let $R=\frac{5050W_1 - 100W_2}{W_1 - 100W_3}$.

  • if $R=50/99$, you conclude that the fake bag is 51.

  • Otherwise, the fake bag is $i=(5050-R)/100$.

To prove optimality, note that

two weighings would give you a system of two equations, which is not enough to force a unique solution with three unknowns, $t,\delta$ and $i$.

$\endgroup$
  • $\begingroup$ About the optimality proof though: as long as i is fixed, we don’t really care about the other variables. $\endgroup$ – Bass Nov 10 '17 at 20:26
  • $\begingroup$ @Bass You are right, that part is lacking. Not sure how to fix at the moment... $\endgroup$ – Mike Earnest Nov 10 '17 at 21:33
  • $\begingroup$ Hi, thanks for your help, but i didn't understand how do you get your formula for R ? $\endgroup$ – Tom92 Nov 12 '17 at 23:17
  • $\begingroup$ First, I solved the first two equations to get $(t,\delta)$ in terns of $i,W_1$ and $W_2$. Then did the same with first and last equations to get $(t,\delta)$ in terms of $i,W_1,W_3$. Then I set those solutions equal to each other and rearranged until that formula appeared. @Tom92 $\endgroup$ – Mike Earnest Nov 13 '17 at 14:08
3
$\begingroup$

take one from the first bag, two from the second bag, three from the third bag and so on....
if they are normal coins they should weigh $(1+2+3+...+99+100)$$*$ weight of one coin but if it became less than that you have to divide the differences by the weight of one coin to find out the number of fake coin and then the bag number.

$\endgroup$
  • $\begingroup$ This is the usual answer to the computer science interview form of this question and is probably as close as one can get to a solution, but as asked, I don't think OP's question is answerable. If the fake coins weigh identical to the real ones or weigh an integer multiple of the real ones, the answer won't work. $\endgroup$ – John Kossa Nov 9 '17 at 22:14
  • 1
    $\begingroup$ @JohnKossa, I understand your points, but, 1- If a coin is fake that means it is not made of the same material (gold, silver ...) as the real coins then it can not have the identical weigh with the same shape and size. 2- If a fake coin weighs an integer multiple of the real coins then it should weigh either half the real coin or less, or weigh double the real coin or more, which in both cases it can be easily identified without weighing it. $\endgroup$ – Seyed Nov 9 '17 at 23:53
  • $\begingroup$ The fake coins could have the same weight and volume as the real coins if the fakes are made of a mix of two or more materials with different densities. $\endgroup$ – N. P. Nov 10 '17 at 18:17
  • $\begingroup$ @N.P., No we can't, because it is against the Archimedes' principle. $\endgroup$ – Seyed Nov 10 '17 at 19:22
  • 1
    $\begingroup$ @Ibrahim mahrir You are correct. As I said in my comment, we had strayed from the scope of the original question and were discussing the possibility of two coins of the same density with different compositions. $\endgroup$ – N. P. Nov 10 '17 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.