Let's imagine that you have ten large bags of coins - nine of them real, one of them fake. You don't know how much the fake coins or the real coins each weigh, but you know that they differ. If you have an extremely precise and accurate digital scale, how many weighings does it take to figure out which bag contains the fake coins?
$\begingroup$
$\endgroup$
8
-
$\begingroup$ There's actually a great explanation about this, the only difference is that they use 12 coins instead of 10 🙂 $\endgroup$– ThePuzzler- or rather APuzzlerCommented May 18, 2023 at 11:01
-
$\begingroup$ @ThePuzzler-orratherAPuzzler There's actually a greater explanation about this and its superset problems, en.wikipedia.org/wiki/Balance_puzzle $\endgroup$– George MenoutisCommented May 18, 2023 at 11:04
-
$\begingroup$ @ThePuzzler-orratherAPuzzler This question uses a digital scale, not a balance scale. Also it has 10 bags of coins, not single coins. $\endgroup$– Jaap ScherphuisCommented May 18, 2023 at 11:05
-
$\begingroup$ @JaapScherphuis hmm, does it matter whether they're bags of coins or single coins? Also, why does it matter that a digital scale is used if we can find the weight difference anyway? 🤔 $\endgroup$– ThePuzzler- or rather APuzzlerCommented May 18, 2023 at 11:09
-
1$\begingroup$ @ThePuzzler-orratherAPuzzler A digital scale has one pan and just gives you the total weight of everything in it. It does not give the difference of two pans. Also, having bags of coins means you can take any amount of guaranteed identical coins from a bag, which makes for a very different kind of puzzle than comparing single coins. See the linked duplicate. $\endgroup$– Jaap ScherphuisCommented May 18, 2023 at 11:14
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
Well, it would take
at least 3 and at most 9 weighings to determine which bag is fake.
This is because
If you weigh 2, and they're different, you still wouldn't know which of the two is fake. So, you'd need a third bag to find out which bag is the outlier.
And
You would need at most 9. If you weigh 9, and they're all the same, you know that the 10th is the fake. All other possibilities are within this range.
$\begingroup$
$\endgroup$
You need 3 or 5 measurements, if you can weighing multiple bags each time and you are not allowed to take coins out of the bags.
Step 1) weighing 1 bag, and call it $B1$
Step 2) weighing another bag, and call it $B2$
You just made two measurements.
Case a:
$B1$ and $B1$ are equals, you know the weight of real coins bag, call it $Wr$
Divide the 8 remining bags in two 4-bags group.
Step 3a) Weighing first 4-bags group. If the size is $4*Wr$, you know the fake bag is in the other 4-bags groups, else it is the first 4-bag group.
Step 4a) Split the 4-bags group with fake bag in two 2-bags groups. Repeating the same logic, weighing first 2-bags group and if it is $2*Wr$ than the fake bag is in the other 2-bags group, else it lies in the first 2-bags group.
Step 5a) Take a bag from the 2-bags group with fake bag and weighing it. If the weight is $Wr$ then the fake one is the other bag in the 2-bags group, else it is the bag you just measured.
So in case a), the total weighings are 5.
Case b:
$B1$ and $B2$ are different. You know that one of them is the fake bag.
Step 3b) Measure one another bag. If it has the same weight of B1 then B2 is fake, else B1 is.
So in case b), the total weighings are 3.
