8
$\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?

Improve this question
$\endgroup$
10
  • $\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, 2017 at 19:39
  • 2
    $\begingroup$ @phroureo The most similar one appears to be this. $\endgroup$
    – Apep
    Nov 9, 2017 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, 2017 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, 2017 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, 2017 at 1:49

2 Answers 2

Reset to default
6
$\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$.

Improve this answer
$\endgroup$
4
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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.

Improve this answer
$\endgroup$
7
  • $\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, 2017 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, 2017 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, 2017 at 18:17
  • $\begingroup$ @N.P., No we can't, because it is against the Archimedes' principle. $\endgroup$
    – Seyed
    Nov 10, 2017 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, 2017 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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