10 coins, 3 of them are fake

Question

Inspired by some great weighing puzzles here (This being one of my favorites), I just made another weighing puzzle - I'm not quite sure how difficult or easy this one is.

---

You are given 10 coins, 7 of which are genuine and weigh the same.
Of the fake coins, 2 are slightly heavier than a genuine coin (they both weigh the same), while the third fake coin is slightly lighter than a genuine coin.
The lighter coin together with one of the heavier coins weighs as much as 2 genuine coins.

Using a balance large enough to fit any number of coins in either pan, what is the minimum number of weighings necessary to figure out which of the coins are fake and which of the fake coins is the lighter one?

Answer 1

Found a solution requiring

6 weighings.

First, label the coins A,B,C,D,E,F,G,H,I,J. Then for the first 4 weighings, weigh:

A/B, C/D, E/F, and G/H (slash notation: "A/B" means "weigh A vs B"). After this, you will have 0, 1, 2, or 3 weighings where the scales differed. Handle each case.

For:

Zero imbalances: This can only happen if one of the weighings had a heavy on each side, and one of the unweighed coins is light. These enumerate (labeling the coins heavy-heavy-light) as: ABI, ABJ, CDI, CDJ, EFI, EFJ, GHI, GHJ. Weigh AI/CJ. If this balances, it's either ABI or CDJ. Weigh A/C to determine which. If AI > CJ, then the options are ABJ, EFJ, or GHJ. Weigh E/G to determine which. Likewise, if AI < CJ, the options are CDI, EFI, or GHI. Again, weigh E/G to determine which.

For (Update: fixed mistake, thanks to comments):

One imbalance: relabel the coins so A>B. The options now are AIJ, AJI, AIB, AJB, CDB, EFB, GHB, IJB. Weigh CI/EJ. If CI=EJ, then the options are GHB, IJB. Weigh G/I to determine which. If CI>EJ, the options are AIB, CDB, or AIJ. Weigh AB/CE to determine which (AIB will balance, the others will lean toward the heavy one). Likewise, if CI < EJ, the options are AJB, EFB, or AJI. Again, weigh AB/CE to determine which.

For:

Two imbalances: relabel the coins so A>B, C>D. The options are now ACB, ACD, ACI, ACJ, AID, AJD, CIB, CJB. Weigh I/J and then AB/CD to determine which of the 8 options is the solution.

For:

Three imbalances: relabel the coins so A>B, C>D, E>F. The only options are ACF, AED, or CEB. Weigh A/C to determine which.

In any case,

at most 6 weighings are required.

And as has been pointed out, there are 360 initial configurations, and $360 > 243 = 3^5$, so at least 6 weighings are required.

Answer 2

Not a solution but the theoretical minimum weighings required is 6. There are 360 combinations of coins. 10 locations for the smaller fake and then 2/9 locations for the larger fakes: 10*nchoosek(9,2) = 360. Each weighing provides a ternary bit of information. At a minimum, 6 weighings are sufficient to learn all fake coin locations: 3^6 = 729 > 360.

Note: the weighings only provide ternary bits when all three results are possible. In situations where there are an odd number of fake coins on the balance (and you knew that beforehand), an even result is impossible. These weighings only provide a binary bit of information. Only one of these can be used to still achieve an optimal solution.

(2^2 * 3^4) < 360 < (2^1 * 3^5)

Answer 3

I have a method that will identify the fakes in

seven

weighings:

Start by

Weighing single coins pairwise. Do it for all the 10 coins, using a total of 5 weighings this way.

There are three possible outcomes:

Either one, two or three weighings produced an unbalanced result.

Let's handle these separately, starting with the easiest case that has

two unbalanced results. All the fakes must be among the 4 coins involved, and the heavy fakes must be those that went down. The light fake is is the lighter one of the two coins that went up, so this case takes 6 weighings in total to solve.

Next, let's handle the case with

one unbalanced result only. We know that the heavy fakes were weighed against each other, so the light fake is the coin that rose up. Since the light fake is now ruled out, it only takes two more weighings to figure out which weighing had the heavy fakes, bringing the total to 7 weighings in total.

(If you pick one coin from each balanced pair, you have "from four coins, find the heavy one", which you can solve in a couple of pretty straightforward ways.)

And finally, there could be

three unbalanced results. One of the fakes must be involved in each of them. Weighing two of the suspected heavy coins against one another will reveal which kind of fakes caused the imbalances: If both were heavy fakes, the scale balances; otherwise the lighter coin is regular, and its pair was the light fake. So in this case, we were able to do with 6 weighings in total. (I originally had 7 for this, because reasons.)

Now, if only we were able to shave off one weighing from the "only 1 unbalanced" case..

Answer 4

Lets give it a try.

We name the coins $HHLGGGGGGG$ (Heavier Lighter, Genuine)

Weighing 1

Taking 5 coins for each side:
only 3 possible combinations (left side is heavier)

1. $HHLGG$ > $GGGGG$
2. $HHGGG$ > $LGGGG$
3. $HGGGG$ > $HLGGG$

Now we take 1 coin from the right side ("first pick") weighing it against all of the four remaing coins on that side individually:

Weighing 2-5

Combination 1: $GGGGG$ (One First Pick possible)
First pick is $G$:
- Weighing 2 $G = G$
- Weighing 3 $G = G$
- Weighing 4 $G = G$
- Weighing 5 $G = G$ (4x equal, EEEE)

Combination 2: $LGGGG$ (Two First Picks possible)
First pick is $G$
- Weighing 2 $G > L$ (1x greater, G)
- Weighing 3 $G = G$
- Weighing 4 $G = G$
- Weighing 5 $G = G$ (3x equal, EEE)
First pick is $L$
- Weighing 2 $L < G$
- Weighing 3 $L < G$
- Weighing 4 $L < G$
- Weighing 5 $L < G$ (4x less, LLLL)

Combination 3: $HLGGG$ (Three First Picks possible)
First pick is $G$
- Weighing 2 $G < H$ (1x less, L)
- Weighing 3 $G > L$ (1x greater, G)
- Weighing 4 $G = G$
- Weighing 5 $G = G$ (2x equal, EE)
First pick is $H$
- Weighing 2 $H > L$
- Weighing 3 $H > G$
- Weighing 4 $H > G$
- Weighing 5 $H > G$ (4x greater, GGGG)
First pick is $L$
- Weighing 2 $L < H$
- Weighing 3 $L < G$
- Weighing 4 $L < G$
- Weighing 5 $L < G$ (4x less, LLLL)

After making Weighings 2-5 you have a pattern with 4 results H (Higher), L (Lower), E (Equal), ordering is not important

From combination 1, first pick $G$: EEEE
From combination 2, first pick $G$: GEEE
From combination 2, first pick $L$: LLLL
From combination 3, first pick $G$: LGEE
From combination 3, first pick $H$: GGGG
From combination 3, first pick $L$: LLLL

Now, if your Pattern is ...

- EEEE the five coins must be $GGGGG$ (all genuine, done) the other five must be $HHLGG$ (it was combination 1 at Weighing 1), we have to go on with $HHLGG$

- GEEE the five coins must be $LGGGG$ (we know $L$ because it was the coin in the "greater-weighing" so we know all 5, done) , the other five must be $HHGGG$ (it was combination 2 at Weighing 1), we have to go on with $HHGGG$

- LGEE the five coins must be $HLGGG$ (we know $L$ and $H$ from the "less-weighing" and the "greater-weighing", $G$ from the "equal-weighing", the other five must be $HGGGG$ (it was combination 3 at Weighing 1), we have to go on with $HGGGG$

- GGGG the five coins must be $HLGGG$ (we know $H$ (first Pick), but not $L$), the other five must be $HGGGG$ (it was combination 3 at Weighing 1), we have to go on with $LGGG$ and $HGGGG$

- LLLL the five coins can be $LGGGG$ or $HLGGG$ (but we know $L$ from the first Pick), so we have to go on with either $GGGG$ and $HHGGG$ from combination 2 or $HGGG$ and $HGGGG$ from combination 3

So go on with what is left

- Pattern EEEE, GEEE and LGEE leaves us with 5 remaining unknown coins and a known genuine coin to weigh them against individually. So with Weighings 6-9 we can determine all 5 unknown coins.

- Pattern GGGG leaves us with $LGGG$ and $HGGGG$ and a known $H$
Weighing 6
known $H$ against one of $HGGGG$
$H = H$ and we know $GGGG$, done
$H > G$ and we know one $G$ leaving $HGGG$, continue 3 times with Weighing 7-9, done
to determine LGGG we have to make Weighing 10-12 with one known $G$ against 3 of $LGGG$ individually, done

- Pattern LLLL leaves us with a known $L$ and remaining $GGGG$ and $HHGGG$ or $HGGG$ and $HGGGG$
Weighing 6 we weigh the four coins against the five coins with one randomly taken off
$GGGG$ and $HHGGG$:
$GGGG < HGGG$ ($H$ taken off)
$GGGG < HHGG$ ($G$ taken off)
$HGGG$ and $HGGGG$:
$HGGG > GGGG$ ($H$ taken off)
$HGGG = HGGG$ ($G$ taken off)
so now we know
if Weighing 6 is less, we have determined $GGGG$ and can determine $HHGGG$ with 4 more Weighings against a known $G$ individually (Weighings 7-10)
if Weighing 6 is greater, we have determined $HGGGG$ ($H$ was taken off, $G$s remaining) and with 3 more Weighings (Weighings 7-9) we can determine $HGGG$ against a known $G$
if Weighing 6 is equal, we have determined a $G$ (taken off the right side) and we can determine $HGGG$ and $HGGG$ with 6 more weighings (Weighings 7-12) against a known $G$

Solution

We need at most $12 weighings$ to determine all coins.

Answer 5

Not sure if this is optimal, but with my strategy I need at most

7

balancing actions.

We use the following notation:

H for heavy (2/10)
L for light (1/10)
N for normal (7/10)

Here is the tactic:

First 5 turns:

Divide coins in pairs (randomly obviously).
For each pair, look if they are balanced or not.
There are only three options:

Case A: HN HN LN NN NN - 3 unbalanced, 2 balanced pairs
Case B: HL HN NN NN NN - 2 unbalanced, 3 balanced pairs
Case C: HH LN NN NN NN - 1 unbalanced, 4 balanced pairs
We now know which pairs are unbalanced, and which of the pair mates is heavier

There is no way that this step takes fewer turns using this tactic because:

There is always a possibility that in our first 4 turns we find:
3xBalanced, 1xUnbalanced
In that case we cannot be sure what the 5th pair would be.

Now that we figured out which case we have, we can do this:

Case A
Take 2 pairs and balance. (turn 6)
If balanced: these are the HN pairs. The 3rd unbalanced pair must be LN. Since we know which of the pair mates is heavier, we are done.
If unbalanced: The heavier pair is HN, the other is LN, the third one not on the balance in HN. we are done.

Case B:
We have to define unbalanced pairs HL and HN
Take one balanced pair (must be NN) and balance with any of the unbalanced pairs (HL or HN). If balanced, this is HL. If unbalanced, this is HN.
Since we already knew which of the unbalanced pairs is heavier, we are done.
6 steps in total

Case C (worst case):
There is one unbalanced pair, we know that these are LN, and the lightest one is L.
One of the balanced pairs is HH.
We need to balance pairs against each other. The are four, let's say pairs i-iv. First, put i and ii together, then iii and iv. These are steps 6 and 7.
In either step 6 or 7, we get and unbalanced result. The heaviest pair consists of HH.

We are done.

Answer 6

I can guarantee 7 weighings

As @jousle noted, there are 360 combinations that could be the final solution. "10 choose 3" times "3 choose 1" is the way I look at it. We want the balance to divide those solutions as equally as possible into smaller and smaller groups at we make our weighings.



I used a computer program to help generate these numbers, but the ideal weighing is to put 2 coins on each pan. The numbers in the chart represent how many of each combination would remain possible after the balance gave that outcome. This ideal weighing doesn't have to hold true as we progress into the later weighings, but it is the best starting point.



So next is to set up some tests. I know that pre-determined strategies do not typically perform as well as adaptive ones, but I'm also worried about how many branches an adaptive strategy would have. I noticed I could reasonably scramble up 5 weighings that don't have very much to do with one another. I didn't iterate on this to improve it, this is literally the first 5 tests I thought up. Note that "C" just means unused... I got used to that format in a different weighing problem.

So, when you run these 5 tests, what are you left with? I used a computer program, because this is well outside the realm of "doing things by hand". The program told me that some of the combinations became unique (meaning if that combination was the actual arrangement, then we could stop at 5 tests) but most were in groups or 2s and 3s. One group, however, was a bit bigger at 6 members. This is the worst case, specifically for this 5-test arrangement I designed.



The number on the left is the combination index so I can keep track of them. These combinations all agree in the sense that they are all possible if the 5 test outcomes are as follows: [ A < B , A < B , A > B , A = B , A = B ]. So this worst case isn't terrible, but since our balance can at best divide combinations into groups of 3, we know that we still need two more weighings to finally settle on a combination. Could a different set of 5 opening tests have done better? Maybe.

So "breaking apart" any set of 3 combinations in a single weighing is always going to be possible. Breaking up a set of 9 combinations in two weighings... that's not so easy. Based on my experience with these puzzles, it could be impossible. We only have to break apart 6, and this I strongly suspect is always possible. It certainly is in this case, here's an example of a test 6 and 7:



So I typically like to make one pan neutral first and go from there. This works out for us, because after test 6 we break the 6 remaining combinations into a group of 3, a group of 2, and a group of 1. The group of 3 is our new worst case scenario, so a simple test 7 can be devised to break apart those three. Note that we no longer need to follow the "2 coins per pan" guideline from earlier because our adaptive strategy is just better now.

So hopefully that convinces people that 7 weighings is surely good enough, with some mild adaptive effort. But could it do 6 weighings? I actually suspect this can be done, the problem is that you need to switch over to being adaptive sooner, maybe after 3 or 4 tests. That makes this problem a real monster, because suddenly we have to account for potentially dozens of nested scenarios based on what the first tests tell us. I've spent enough time on this problem already, I'm not getting into that mess

Fun problem, though. It has a different flavor to some of the ones I have played with.

Answer 7

I think 6 will workout.Let us divide the total coins in set of 3,3,3,1. Now when you compare 3(1),3(2)/ 3(1),3(3)/3(2)3(3) ypu will get various weights increasing order. I will use mathematical forms to represent the possible weights. Possibilities are +,0,- +,+,0 ++,0,- +,+,- 0,0,+ By internal comparison you will be able to get in 6 minimum chances.