Lets say you have 10 coins, any number of which may be fake. You know how heavy the fake and real coins are, and you have a digital scale. (so you'll know exactly how many of the coins are fake.) How many times do you need to weigh the coins to figure out which are fake and which are real? How does it scale for larger n?
4
-
$\begingroup$ Nope, this is a very different problem. There are no bags here, just 10 seperate coins. $\endgroup$– blademan9999May 18 at 14:49
-
2$\begingroup$ Do the real coins and fake coins all weigh the same as each other? And is that weight different? I.e. is it the case that each real coin weighs X, each fake coin weighs Y, and X does not equal Y. $\endgroup$– ShowsniMay 18 at 15:57
-
$\begingroup$ @Showsni if X == Y the puzzle isn't solvable by weighing. The question tells us that the weights are known, and that you can find out how many are fake by weighing (all the coins together). $\endgroup$– Weather VaneMay 18 at 16:39
-
$\begingroup$ at least one of them is fake? $\endgroup$– OrayMay 18 at 21:02
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Large enough numbers N can be solve arbitrary close to
5N/7 measurements
(And the approach below is not proven to be optimal)
Note: symmetry equivalent cases are often skipped.
measure groups of 5
if 0 or 5 fakes: 1 measurement was enough.
else combine 2 groups with the same number of fakes. Note: For large N, this can be done for in almost all groups (since there are only 4 such group types).
Case1: Assume A: coin 0..4 and B: coin 5..9 both have 1 fake:
C) Measure (0,1,5,6)
C has
0 fakes: measure (2),(3),(7),(8) => 7 measurements (and 7/10 < 5/7)
1 fakes: measure (0,1), then (0),(7),(8) OR (6),(2),(3) => 7 measurements
2 fakes: measure (0) and (5) => 5 measurements
Case2: Assume A: coin 0..4 and B: coin 5..9 both have 2 fakes:
C) Measure (0,1,5,6)
C has
0 fakes: measure (2),(3),(7),(8) => 7 measurements (and 7/10 < 5/7)
3 fakes: measure (0,1), then (0),(7),(8) OR (6),(2),(3) => 7 measurements
4 fakes: done
1 or 2 fakes: D) Measure (2,3,7,8)
C and D have
1,1 fake:
fakes are 2or3 5or6 4,9 OR 0or1, 7or8, 4,9 => +3= 7 measurements
2,2 fake:
fakes are 2,3,5,6 OR 0,1,7,8 OR 0or1,2or3,5or6,7or8
E) Measure (2,3,5)
0 fakes done
3 fakes done
1 fake: fakes are 0or1 2or3 6 7or8
==> 3 unknowns left after 5 measurements! use 0,2,7 recursively
2 fakes: fakes are 0or1 2or3 5 7or8
==> 3 unknowns left after 5 measurements! use 0,2,7 recursively
2,1 fake; possibilities:
2or3, 5, 6, 4
2or3, 0or1, 5or6, 9
7or8, 0or1, 5or6, 4
7or8, 0, 1, 9
E) Measure 239
0 fakes 7or8, 0or1, 5or6, 4
==> 3 unknowns left after 5 measurements! use 0,5,7 recursively
1 fakes 2or3, 5, 6, 4 OR 7or8, 0, 1, 9
==> 3 unknowns left after 5 measurements! use 2,5,7 recursively
2 fakes 2or3, 0or1, 5or6, 9
==> 3 unknowns left after 5 measurements! use 0,2,5 recursively
Using 3 out of 10 recursively after 5 measurements gives 5+5*(3/10)+5*(3/10)^2+... = 50 / 7 measurements per group of 10
i.e. an asymptote of 5/7 per coin
$\begingroup$
$\endgroup$
2
Maybe not optimal, but I will describe an algorithm that seems okay.
First weigh all the coins together. Proceed recursively where at each step we know the number of coins of each type. I will write $(a,b)$ to denote a state with $a$ coins of the more common type and $b$ coins of the less common type. The base case is when all the coins are the same, as have already identified all the coins. We will chose one of two strategies depending on the current state.
To "divide and conquer", split the coins evenly into two groups (or as close as possible if the number of coins is odd). Weight one group. By subtraction, we know the result of weighing the other group. Recurse on each group.
To "look for matches", first weight coins A and B. Then, if they don't match, weigh coins A and C. If they don't match, weigh coins A and D. Repeat until either 1) you find a coin that matches A; you then know the weights of all the tested coins; recurse on the remaining coins. Or 2) the number of coins not matching A is greater than the number of coins of the less-represented type. Then you also know the weights of all the tested coins; recurse on the remaining coins.
To determine precisely whether to "divide and conquer" or "look for matches", just analyze which gives the smaller number of tests in the worst case. For 10 or fewer coins, these cases should "look for matches": $(8,2), (4, 4), (4, 3), (4, 2), (3, 3), (3, 2)$.
No proof, but this seems to solve in around $4n/5$ even for larger $n$.
For example, with $n=5$:
If first test is $(5,0)$, we have finished in one test. If first test is $(4,1)$ we divide and conquer, splitting into $2+3$ which either gives $(2,0)$ and $(2,1)$ or $(3,0)$ and $(1,1)$. $(2,1)$ (the worse case) can easily be solved in two additional tests (e.g. test two coins individually and last by process of elimination) for a total of four. If first test is $(3,2)$, we look for matches. If we find the match right away, we have reduced in one test to $(3,0)$ or $(2, 1)$; worse is $(2,1)$ which takes two more tests for four total. Finding a match after two reduces to $(2,0)$ or $(1,1)$; worse is $(1,1)$ which takes an additional test for four total. Finding a match after three reduces to $(1, 0)$ which doesn't take an additional test. Not finding a match after three also reduces to $(1, 0)$.
For $n=10$ the algorithm should take this many tests in the worst case:
8
-
$\begingroup$ To make it easier for numbers divisible by 5, we can simply divide into groups of 5 and perform 4 tests on each group to achieve 4n/5. I assume it would be the ceiling then for other values? $\endgroup$– hexominoMay 19 at 9:46
-
1$\begingroup$ Indeed, you could always divide into groups of 5, with perhaps one leftover group of m < 5 which can be done in m, guaranteeing ceil(4n/5) - this is a good upper bound. Great answer! $\endgroup$– hexominoMay 19 at 10:38
$\begingroup$
$\endgroup$
1
It might be a bit boring and I could be completely wrong - but isn't the minimal worst-case scenario going to result in n different weighings.
Since we're using a digital scale as opposed to a comparative scale it costs us a lot more different weighing sessions to get information.
Although we can employ strategies that can help us have < n weighing sessions there's always going to be such a distribution of fake coins that results in us having to weigh ≥ n times
-
2$\begingroup$ Nope, I already figured out how to get 6 coins in 5 weighings, $\endgroup$ May 18 at 16:45