14
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A scale or a balance? $\endgroup$ – Mathaddict Jun 13 at 17:52
  • $\begingroup$ A balance, I edited the question. $\endgroup$ – shoopi Jun 13 at 17:55
  • 1
    $\begingroup$ This is a very interesting puzzle, thank you! $\endgroup$ – Bass Jun 13 at 19:20
  • 1
    $\begingroup$ Pardon me, what is the difference between scale and balance? $\endgroup$ – athin Jun 13 at 20:36
  • 1
    $\begingroup$ I wasn't quite sure myself, so I googled it and found quite a few answers. In short, scale measures weight, while balance measures mass. But more importantly, balance is used to compare two objects (or multiple objects) against each other, which is the intention here. source $\endgroup$ – shoopi Jun 13 at 20:45
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hi! First of all, fantastic work. I really hope this is correct since it is much cleaner than my solution. Now, unless I'm mistaken, I think in the one imbalance case, when you weigh I/J, If I=J, then the options are CDB, EFB, GHB like you say, but also IJB right? Regardless, I have to go to sleep, so I'll be back again tomorrow evening and check your answer again. If it's correct I'll mark it! Good job! $\endgroup$ – shoopi Jun 17 at 19:43
  • $\begingroup$ Yeah weighing I/J doesn't work. (also IJB and JIB are both listed when they are the same permutation). I think weighing C/I works here. If equal: AJB, EFB, or GHB (weigh A/E). if C<I: AIB, AIJ, or IJB (weigh J/C). If C>I: CDB or AJI (weigh B/I). There are a lot of ways to do it but weighing I/J can't be right since that's just weighing the last pair and would turn into Bass's solution. $\endgroup$ – jousle Jun 18 at 16:15
  • 1
    $\begingroup$ Thanks for the catch. Updated with the correction. $\endgroup$ – user3294068 Jun 18 at 17:03
  • $\begingroup$ Weighing C/I is indeed enough but CI/EJ works as well. Well done! $\endgroup$ – shoopi Jun 18 at 17:20
6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Fantastic! I wasn't sure how to calculate this myself. So would you say with confidence that it cannot be done with less than 6 weighings? $\endgroup$ – shoopi Jun 14 at 17:27
  • 2
    $\begingroup$ Yes, shoopi, it is so. $\endgroup$ – George Menoutis Jun 14 at 19:40
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What about 4 balanced outcomes in the first 5 tests? $\endgroup$ – Dark Thunder Jun 14 at 15:21
  • 3
    $\begingroup$ @DarkThunder that would be the case with one unbalanced result, in the next-to-last spoiler block. $\endgroup$ – Bass Jun 14 at 15:23
  • $\begingroup$ Oh I misread it. I can also confirm your starting tests can solve the problem in 7 weighings. Makes me feel silly bothering with 2 coins per pan in my answer. $\endgroup$ – Dark Thunder Jun 14 at 15:44
  • $\begingroup$ Could you clarify your answer for one unbalanced result please? You have isolated the light fake in one group. You are left with four equal groups. One of the four has two heavy fakes. What are the two weighings that you do to find the fake weighing? $\endgroup$ – LeppyR64 Jun 14 at 16:29
  • 1
    $\begingroup$ Fantastic answer Bass. What I really like about this is the strategy is clear and it is easy to follow the logic. I'm currently working on a 6 weigh solution, so I'll keep you updated! $\endgroup$ – shoopi Jun 14 at 22:19
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Good job! 7 is currently the highest anyone found. $\endgroup$ – shoopi Jun 14 at 22:25
2
$\begingroup$

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.

enter image description here

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.

enter image description here

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.

enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ While Bass's solution is shorter and easier to follow, I highly appreciate the analyse and work you've done with the program. Well done! I'm currently working on an adaptive 6 weigh solution. By hand. Yes I have a lot of free time... $\endgroup$ – shoopi Jun 14 at 22:23
  • $\begingroup$ @shoopi well don't hurt yourself. If you are shooting for 6, my analysis suggested that an adaptive strategy should start after the third test. It would also seem at least two of those three tests should be 2 coins per pan. So the best start would be "1+2 vs 3+4", then "5+6 vs 7+8" and then to round out the coins run just "9 vs 10". That's the best I can figure... worst case scenario has 24 combinations (and there's a few of them). Daunting! $\endgroup$ – Dark Thunder Jun 15 at 0:43
  • $\begingroup$ Oops. I keep making mistakes. 1 coin per pan gets you a lot farther than I thought. Oh well. $\endgroup$ – Dark Thunder Jun 17 at 18:18
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Hi, I'm not sure I follow exactly what you mean. Could you give a practical example so that I could understand better? Are you giving a formula to solve or just general insight? $\endgroup$ – shoopi Jun 16 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.