8

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?

Mike Earnest
  • 32,336
  • 6
  • 92
  • 237
Tom92
  • 81
  • 2
  • I'm sure that this has been asked before, but the "Related" section is only pulling up variations on the problem. – phroureo Nov 09 '17 at 19:39
  • 2
    @phroureo The most similar one appears to be this. – Apep Nov 09 '17 at 19:51
  • Welcome to puzzling! This does appear to be a simplified wording of Coin Weighing Problem. If You take the tour it may help explain some guidelines for posts. If your puzzle is meant to be different than the one in the link above, maybe try changing the wording and giving more specific instructions how you want us to come to the solution. – Hawkeye Nov 09 '17 at 21:06
  • 1
    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. – Apep Nov 09 '17 at 21:12
  • Since there is no guarantee that the fake coins have a different weight than the real coins, this does not seem solvable with just a scale. On the other hand, perhaps I could do it in zero weighings by a visual examination of the coins. – Hellion Nov 09 '17 at 21:33
  • I want to emphasize Apep's comment. The weights of a gold coin and fake coin are not known, making this a harder variant. – Mike Earnest Nov 09 '17 at 21:40
  • Yes, Apep we ignore the weights of gold coins and fake coins, so as Mike said it's a harder variant than the one which boboquack showed to me – Tom92 Nov 09 '17 at 22:20
  • It's not clear what you mean by "we ignore the weights". If a real coin and a fake coin weigh the same, then weights can be ignored, but now you've removed weighing as a mechanic for solving the puzzle and left it entirely Too Broad as people now must guess at how to distinguish them. If they're not the same, then "ignoring" the weights leaves us with nowhere to go, making it Unclear What You're Asking. If they differ and we use that information, this likely devolves to a Duplicate of the previous question but requiring one trivial additional weighing. Which close reason is it? :) – Rubio Nov 10 '17 at 07:08
  • 3
    @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. – Mike Earnest Nov 10 '17 at 13:48
  • 1
    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. – Rubio Nov 27 '17 at 01:49

2 Answers2

6

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$.

Mike Earnest
  • 32,336
  • 6
  • 92
  • 237
  • About the optimality proof though: as long as i is fixed, we don’t really care about the other variables. – Bass Nov 10 '17 at 20:26
  • @Bass You are right, that part is lacking. Not sure how to fix at the moment... – Mike Earnest Nov 10 '17 at 21:33
  • Hi, thanks for your help, but i didn't understand how do you get your formula for R ? – Tom92 Nov 12 '17 at 23:17
  • 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 – Mike Earnest Nov 13 '17 at 14:08
3

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.

ABcDexter
  • 7,262
  • 4
  • 42
  • 84
Seyed
  • 2,234
  • 1
  • 13
  • 17
  • 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. – John Kossa Nov 09 '17 at 22:14
  • 1
    @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. – Seyed Nov 09 '17 at 23:53
  • 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. – N. P. Nov 10 '17 at 18:17
  • @N.P., No we can't, because it is against the Archimedes' principle. – Seyed Nov 10 '17 at 19:22
  • @Seyed Consider a mixture of silver and platinum. Silver has a density lower than gold, while platinum has a density higher than gold. In a ratio of about 1:4 (exact amounts can be calculated), this blend should have the same density as gold. I think we might be straying from the scope of the original question, though, so if a mod thinks it appropriate, feel free to delete this. – N. P. Nov 10 '17 at 19:44
  • @N.P. OP clearly states that the fakes weigh different than the real ones: The fakes all weigh the same as each other, but weigh different than a true gold coin. – ibrahim mahrir Nov 10 '17 at 19:54
  • 1
    @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. – N. P. Nov 10 '17 at 19:58