1
$\begingroup$

You have 10 bags of 100 coins, and in all of them except for one, every coin weighs exactly 10 grams. However, in the counterfeit bag, all coins weigh either 9 or 11 grams. You need to identify the counterfeit bag in just one weighing, and you have a digital scale that provides accurate weights. Can you successfully find the counterfeit bag in just one attempt?

In the above problem statement the coins in the counterfeit bag are either all 9s or all 11s which makes it easy to solve.

My question is that if the counterfeit bag contains an unknown mix of 9s and 11s, can we still find the bag in one weighing? If not how can we prove that no solution exists that identifies the counterfeit bag with just one weighing? Also, how do we find the minimum number of weighings needed to find the counterfeit bag?

$\endgroup$

2 Answers 2

1
$\begingroup$

If the weights in the fake bag can vary, you won't be able to do it with one weighing.

To see this, consider a possible weighing as a list $\{a_n\}_{n=1}^{10}$ of numbers of coins from each bag. Of course, all the $a_n$ must be distinct (though one of them might, in principle, be $0$).

Now, if two of the non-zero $a_n$ are even the problem can't be solved, as each such bag might contribute an equal number of $9's$ and $11's$ and hence weigh exactly as much as it would if they were all $10's$. Thus, you can assume that at least nine of the $a_n$ are odd. Any odd collection might contribute exactly $\pm 1$ gram off of it's fair allotment and, if the total weighing was off by $\pm 1$, you'd have no way to identify the offending bag.

$\endgroup$
3
  • $\begingroup$ How do we go about finding the minimum number of weighings? $\endgroup$
    – Cidatama 0
    Commented Apr 14 at 8:13
  • $\begingroup$ The argument I gave shows that there is no advantage to weighing more than one coin from a given bag at a time, so you are down to a binary search. Weigh one coin from the first $5$ bags, etc. $\endgroup$
    – lulu
    Commented Apr 14 at 10:50
  • $\begingroup$ Should have said: I am assuming you meant "guaranteed solution", so I am assuming worst case throughout. Probabilistically (assuming that each fake coin has an equal chance of being light or heavy) you can still do better. $\endgroup$
    – lulu
    Commented Apr 14 at 10:52
0
$\begingroup$

It doesn't follows the solution to the original question, which is taking $1$ coin from the $1^{st}$ bag,$2$ from the $2^{nd}$ and so on, and weighing them. Still if we conduct it, if they had been pure, we would have got $10+20+30+...100=550g$.

Let $a,a≤10$ be the number of $9g$ coins taken. Let $b,b≤10$ be the number of $11g$ coins taken. $a+b=c,c≤10$ which gives us the number of the bag. Note that we don't know any value , be it a,b, or c

After weighing, we would get a value which is equal to $550-a+b$. For each $9g$ coin, there is $1g$ decrease in the summation. Same goes for $11g$ but it's $1g$ increase.

We can't proceed from here. It can have a variety of values. For example

After weighing, we get $556 g$. $$556=550-1+7=550-2+8$$ So the coins can be from the $8^{th}$ bag or the $10^{th}$ bag.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .