2
$\begingroup$

This is an extension of a previous three-pan balance puzzle.

I give you a bag containing 27 coins, which look exactly the same. Among them are two fake coins. All genuine coins weigh the same. The fake coins are very little heavier than the genuine ones, and they may have a different weight from each other. You cannot distinguish the weight of genuine and fake coins by hand.

You have no own utility to weigh coins, so I suggest you use my impossibly precise 3-pan balance.

The three-pan balance

The balance implements the "lightest-pan-detection-rule" (LPDR) and works like this:

  • Put any selection of coins on the three pans, and press the activation button.
  • After activation, the balance lifts the unique pan with the lightest load.
  • If there is no unique lightest pan, none of the pans will rise.

You may only weigh the coins I gave you.

The problem

How can you identify the two heavy coins with at most 5 weighings?


Bonus question: Can you extend your solution to 3^n coins?

$\endgroup$
  • 2
    $\begingroup$ You've asked a lot of these questions. $\endgroup$ – mmking Jun 27 '15 at 23:27
  • $\begingroup$ Are you allowed to mark the ones that you know are real and use them as standard weights? $\endgroup$ – mmking Jun 28 '15 at 1:56
  • $\begingroup$ I ask a lot of these questions because my interest in this topic sparked again. I'll try and wait longer between questions. $\endgroup$ – Christian Semrau Jun 28 '15 at 8:10
  • $\begingroup$ Like in a standard 2-pan balance puzzle, you can remember which coins you already weighed, or mark them, and reuse them in subsequent weighings. You may assume that the marking does not change weighing results, even though the balance is impossibly precise. :-) $\endgroup$ – Christian Semrau Jun 28 '15 at 8:14
1
$\begingroup$

Since my other answer is already so long, I'll post this as a separate answer.

Generalizing to $3^n$

There are ${3^n\choose 2} =3^n (3^n-1)/2 \approx 3^{2n}/2$ possible combinations. Each weighing has 4 possible outcomes, so this requires at least $\lceil \log_4 {3^n\choose 2}\rceil \approx \lceil\log_4{(3^{2n}/2)}\rceil = \lceil 2n\log_4 3 - 1/2\rceil$ weighings. (The approximation breaks down for $n=1$). My algorithm below requires $\lceil n + \lceil(n-1)\log_4 3\rceil$ weighings.

Phase 1

Take all $3^n$ coins and put them in one tall stack. Then split: put the bottom third on Pan 1, the middle third on Pan 2, the top third on Pan 3. Weigh and note the results.

Then repeat the split for each stack: put the bottom third of each stack onto Pan 1, the middle third on Pan 2, the top third on Pan 3. Repeat for a total of $n$ weighings, yielding at the end $3^n$ stacks of 1 coin each.

Each weighing is orthogonoal to the others $-$ each time you are splitting stacks, there is a roughly equal chance of each heavy coin ending up on each Pan, the only proviso being that the two heavy coins cannot be at the same height in the same stack.

Thus, each division splits the options as: $1/3$: no pan rises, $2/9$: Pan 1 rises, $2/9$: Pan 2 rises, $2/9$: Pan 3 rises. Each split goes one level deeper into the stacks, so they are essentially independent.

The only correlation between the weighings is that it is not possible for all $n$ weighings to come out flat. That would require both coins to be at the same location in the first stack, which is impossible.

So, after $n$ weighings, we have at least one weighing where a pan rose. Name that the "alpha" weighing. Pick one pan that sank on the alpha weighing and call those the "A" coins, and name the coins on the other pan that sank the "B" coins. The remaining coins are the "C" coins, and we know all of them are normal.

There are $3^{n-1}$ coins in each group. Thus, there are $3^{n-1}\times3^{n-1} = 3^{2n-2}$ options remaining, considering only the result of the alpha weighing.

For each candidate heavy coin in the "A" group, any coin in the "B" group is a potential matching candidate heavy coin. Each weighing after the alpha weighing splits that group into 3 equal parts, thus reducing the number of potential matching coins to at most $1/3$ of the number from before.

Thus, after the other $n-1$ predetermined weighings, the number of candidate matching "B" coins for each "A" coin is reduced by a factor of $3^{n-1}$ (or reduced to zero if that "A" coin was on a pan that rose and was itself eliminated). Since there are $3^{n-1}$ "B" coins, this means after $n$ weighings, each remaining candidate "A" coin matches up with only one candidate "B" coin. Using the same logic in reverse, each "B" coin is matched up with at most one "A" coin.

So, after $n$ weighings, the remaining possibilities are all non-overlapping sets of one "A" coin and a matching "B" coin. There are at most $3^{n-1}$ "A" coins left.

Phase 2

For this phase, we take the set of $x$ matching pairs and divide it into four groups of $x/4$ matching pairs (if 4 does not divide $x$, let the fourth group be smaller). We then split each pair in the first group and put one coin on Pan 1 and one on Pan 2. The second group we split, putting on on Pan 1 and one on Pan 3. The third gets split onto Pans 2 and 3.

If a pan rises, then all the candidate pairs that had a coin on that pan are eliminated, and so are the coins in the fourth group. If no pan rises, then the heavy coins are in the fourth group. This reduces the number of candidates to $\lceil x/4\rceil$. Repeating this to reduce $3^{n-1}$ down to 1 requires $\lceil (n-1) \log_4 3\rceil$ weighings. (On the final weighing, there might be only 2 options remaining; in that case, fill in with extra known normal coins, of which we have $3^n-4$.)

Optimality

Since the first $n$ weighings are orthogonal, this algorithm gathers the most possible information from them. The best division from any of these weighings is $2/9$,$2/9$,$2/9$,$1/3$. It is not possible to reduce the number of options by a factor of $4$ during any of the first $n$ weighings, no matter the algorithm. The rest of the weighings do reduce the number of options by a factor of $4$ each time, so they must be optimal. Thus, this algorithm is an optimal algorithm, and no other algorithm can answer the question in fewer steps.

Summary

Thus, the total number of weighings is $n$ for Phase 1 and $\lceil (n-1) \log_4 3\rceil$ for phase 2. Since $\log_4 3 \approx 0.79$, the solution approximates to: $W \approx \lceil n + 0.8(n-1)\rceil$. This comes to, for $n=1,2,...$: $W=1,3,5,7,9,10,12,...$. For example, for $3^6$ coins, the first 6 weighings leave us with at most $2^5 = 243$ possibilities, which can be distinguished in $4$ weighings, since $243 < 256 = 4^4$. Thus, $W=10$ weighings are required for $3^6$ coins.

For $n=1$, the first weighing is also the $n^{th}$ weighing is the alpha weighing. After that the "A" and "B" groups have 1 coin each, thus requiring 0 more weighings.

For $n=2$, at least one of the first two weighings had a pan rise. That gave us an "A" and a "B" group of 3 coins each. On the second weighing, the three "B" coins are split up, so each "A" coin matches with at most one "B" coin. On the third weighing, the three options are split and we determine the final pair. If there were only two remaining options after the second weighing, we would need to fill in with two extra normal coins, of which we have five.

For $n=3$, this yields the exact same algorithm as for my other answer, without all the relabeling.

$\endgroup$
  • $\begingroup$ Wow! If this is correct, your solution is better than mine, which needs $2n-1$ weighings for $3^n$ coins. $\endgroup$ – Christian Semrau Jul 8 '15 at 18:52
3
$\begingroup$

Determining two heavy coins out of 27 can be done in 5 weighings. It's been several hours, so I'll skip the spoiler tags (also, i don't know how to spoiler large sections of text). I don't have a generalization, yet, but if i come up with one, I'll edit it in.

Label the coins 1-27. Take three weighings:

First: $1$-$9$ vs $10$-$18$ vs $19$-$27$

Second: $1,2,3,10,11,12,19,20,21$ vs $4,5,6,13,14,15,22,23,24$ vs $7,8,9,16,17,18,25,26,27$

Third: $1,4,7,10,13,16,19,22,25$ vs $2,5,8,11,14,17,20,23,26$ vs $3,6,9,12,15,18,21,24,27$

If the two heavy coins are on the same pan, then the pans will balance. Otherwise the one pan with no heavy coins will rise. Since there is no combination of two coins that are on the same pan for all three weighings, for at least one of the three weighings, one of the pans must rise.

Name a weighing where one pan rose as weighing "alpha".

Alpha: Considering weighing alpha, relabel the coins on one of the heavy pans as A1 - A9, the coins on the other heavy pan as B1 - B9, and the coins on the light pan as C1 - C9. (Preserve order on the numberings). We know that one of the heavy coins is an "A" coin and one is a "B" coin and all the "C" coins are normal. This leaves us with 81 possibilities, picking one each from two sets of 9 elements.

One of the weighings performed had a pan with A1,A2,A3,B1,B2,B3,C1,C2,C3. Name that weighing "beta". The other weighing had a pan with A1,A4,A7,B1,B4,B7,C1,C4,C7. Label that weighing "gamma".

Beta: No pan rises: If no pan rose for weighing beta, then both heavy coins were on the same pan for that weighing. The combinations that satisfy this are: $$\{A1,A2,A3\}\times\{B1,B2,B3\}\text{, or}$$ $$\{A4,A5,A6\}\times\{B4,B5,B6\}\text{, or}$$ $$\{A7,A8,A9\}\times\{B7,B8,B9\}$$

For a total of 27 possibilities.

If no pan rose for weighing gamma, then the possibilities are Ax,Bx, where x is the same for both, for 9 options remaining. If the third pan rose, then there are 6 options: A1B2, A2B1, A4B5, A5B4, A7B8, or A8B7. In any case, there are 6 or 9 options, which do not overlap.

Split 3 pairs onto the first two pans and split 3 pairs onto the first and third pans. If you have 9 pairs, split the last 3 pairs onto the second and third pan. Otherwise, add 3 other coins to each of the second and third pans.

During this fourth weighing, you have definitely split the two heavy coins, so a pan will rise. That will leave you with 3 pairs for possibilities. Split one pair on first and second pans, second pair on first and third pans, third pair on second and third pans. The fifth weighing will tell you your answer.

For example, weighing gamma was flat, then weigh: A1,A2,A3,A4,A5,A6 vs B1,B2,B3,A7,A8,A9 vs B4,B5,B6,B7,B8,B9. Each of the 9 pairs are split, 3 for each combination of two pans.

If the second pan rose, the remaining options are A4B4 or A5B5 or A6B6. On the fifth weighing, compare A4,A5 vs B4,A6 vs B5,B6. If the first pan rises now, the heavy coins are A6 and B6.

Beta: One pan rose. If one pan rose in weighing beta, there are 18 remaining possibilities. Consider the case where the third pan rose (the others are symmetrically solved). The remaining options are: $$\{A1,A2,A3\}\times\{B4,B5,B6\}\text{, or}$$ $$\{A4,A5,A6\}\times\{B1,B2,B3\}$$

If no pan rose for weighing gamma, there are 6 options remaining: A1B4 or A2B5 or A3B6 or A4B1 or A5B2 or A6B3. If the third pan rose, there are 4 options remaining: A1B2 or A2B1 or A4B5 or A5B4. Similarly, there are 4 options if either of the other two pans rose.

In any case, there are either 4 or 6 options, with no overlap. Proceed as above, splitting the pairs evenly. If there are only 4 options, you can leave a pair out and complete in 4 weighings. For example, if the third pan rose on weighing gamma, then for the fourth weighing compare: A1, A2 vs B2,A4 vs B1,B5. If no pan rises, the heavy coins are A5B4. Otherwise, the fourth weighing would indicate which coins the heavy ones are.

So, in summary, it can be done in 5 weighings, and the arrangements of coins on the first three weighings can be determined ahead of time. The relabeling steps I took simplify the number of cases and minimize the "assume without loss of generality" steps.

$\endgroup$
2
$\begingroup$

Well, I didn't find a solution that used at most 5 weighings, but I found one nonetheless (though it is a bit long).

also, I can't seem to put the following in one spoiler tag?

First we split the 27 coins into three groups of nine. There are two cases:
1) Two groups each contain one fake, or
2) One group contains both fakes.

.

For case 1: the pan will lift up the group with no fakes, so now we choose to work with the two piles that contain the fakes. Divide each pile into three groups of three coins such that we have two groups of three smaller piles. Now we label these piles a, b, c, d, e, and f, and we know two such piles contain a fake coin. Without loss of generality (WLOG), let's say that a and d contain the fake coins (now labeled A and D).

.

We choose one pile to swap from each group, and weigh the "first" group each time:
Swap A with D, e, or f --> nothing happens.
Swap b/c with e or f --> nothing happens.
Swap b/c with D --> c/b raises; we know A and D contain the two fakes. [worst case is 6 weighings]

.

Now that we know A and D contain the fakes, we redistribute them into three piles of two, giving the following cases after weighing [o = normal, O = fake]:
Case 1.1: (oo | oo | OO) --> nothing happens
Case 1.2: (oO | oO | oo) --> one group is lifted

.

If case 1.1 happens, then we redistribute the coins such that no two are in the same pile again to arrive at Case 1.2. For case 1.2, we have WLOG coins w, X, y, Z (X and Z being fake). We swap a coin from each pile with each other, giving us either (wy | XZ) or (wZ | yX). If we get the latter arrangement, we switch one coin being swapped to arrive at the former arrangement.

.

Now we take one of the piles (wy or XZ) and split it between the remaining piles. Then we take three real coins and put them on the balance to weigh. If we split the pair wy, then the balance does nothing, and so the other pair must be the fake coins. If we split the pair XZ, then the balance would lift the three real coins we just added, and so the pair that we split must be the fake coins.

.

Through this method, we have at worst case: 6 + 2 + 2 = 10 weighings after the initial weighing.

.

Now for case 2: If we have one pile containing two fakes, then we can "deal" the coins into three new piles of 9 coins. To illustrate, we have coins A, b, c, D, e, f, g, h, i (a worst case arrangement). Dealing out this pile, we will get groups (ADg | beh | cfi). Once we finish dealing the rest of the coins and reweigh, we find that the balance does nothing again and will thus require another redealing. So at worst case, it will take 2 weighings to achieve the setup for case 1.

.

In this case, we have at worst case: 2 + 10 = 12 weighings after the initial weighing.

.

Thus overall, it will take at most 13 tries to find the fake coin.

.

$\endgroup$
  • $\begingroup$ I stumbled at your use of WLOG. I think you mean that you can identify the two heaps of 3 coins that each contain one fake, and you can rename these to A and D, after you identified them. Also, I don't follow your counting of the 6 weighings: "Swap A with D, e, or f" - 3 weighings, "Swap b or c with e or f" - 4 weighings, "Swap b or c with D" - 2 weighings, for a total of 9 weighings. Maybe you don't need all of these? $\endgroup$ – Christian Semrau Jul 7 '15 at 19:55
  • $\begingroup$ For WLOG, I was just using the fact that we know that two heaps contain a fake coin to apply labels (to reduce wordiness). As for the 6 weighings, I was explaining the worst case scenerio (and judging from your response it seems that my formatting made it confusing). I was trying to show that there are five cases where the balance wouldn't move: when the fake coin pile is exchanged for a real coin pile or another fake coin pile (D, e or f = 3 tries), and when a real coin pile is swapped with another real coin pile (b or c with e or f = 2 tries). $\endgroup$ – dzastergamer Jul 7 '15 at 20:22
  • $\begingroup$ I consider reducing wordiness by relabelling heaps or coins a good thing (and usually, I dont even use "WLOG" here, just "relabel the heaps/coins and remember the relabelling map"). What are the 6 weighings of the heaps a,b,c,d,e,f you would perform, that allow you to mark heaps A and D for the next step? $\endgroup$ – Christian Semrau Jul 7 '15 at 20:38
  • $\begingroup$ Yes, it would take at most 6 weighings to figure out which heaps are A and D. $\endgroup$ – dzastergamer Jul 8 '15 at 14:54
0
$\begingroup$

For comparison, I'll provide my own solution, which uses $2n-1$ weighings. It is optimal only for $n \leq 5$.

The base case $n=1$ (3 coins) is solvable with 1 weighing by putting 1 coin on each pan.

Split the $3^n$ coins in 3 groups of $3^{n-1}$ each, and put one group on each pan.

1) If one pan rises, we know the other two pans each contain one heavy coin. Solve puzzle Two heaps each with a heavy ball, and a 3-pan balance to find the two coins in $\lceil (n-1)\log_2 3 \rceil \leq 2(n-1)$ weighings.

2) I no pan rises, we know the two heavy coins are together in one heap. Temporarily remove one coin from two of the heaps, and weigh the remaining $3^{n-1}-1, 3^{n-1}-1, 3^{n-1}$ coins.

2.1) If a pan with less coins rises, we know the other pan with less coins contains at least one heavy coin, so we identified the heap of $3^{n-1}$ coins with two heavy coins (including its removed coin).

2.2) If no pan rises, we know the pan with more coins has the heavy heap.

In either case, we have used 2 weighings to reduce the problem from $3^n$ coins to $3^{n-1}$ coins. We can apply this solution recursively. Since the reduced problem is solved in $2(n-1)-1$ weighings, our problem is solved in $2n-1$ weighings.

$\endgroup$

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.