Fifty-two genuine and two fake coins

Question

In the country Borgonia, there are only two types of coins: genuine ones and fake ones. All genuine coins have the same weight, and all fake coins have the same weight. The weight of a genuine coin is different from the weight of a fake coin, but nobody knows whether it is larger or smaller.

Cosmo puts 54 coins on the table and tells Fredo: "There are exactly 2 fake coins among these 54 coins. Please divide them into two groups of equal total weight!" Then Cosmo leaves the room. On the table, there is a balance with two pans.

Can Fredo find the desired division into two groups by using the balance at most five times?

Answer 1

This is essentially a modification of Waxwing's argument.

We will perform a sequence of weighings, each of of which puts 27 coins on each side of the balance. If ever the two counterfeit coins are of different sides, the scale will balance and we are done. At any point during the process, we will call two coins equivalent if they have ended up on the same side of the balance in every weighing so far (so at the start, every coin is equivalent to every other coin). For each weighing, we will split each equivalence class in half (or as close to half as possible, if the size of the class is odd), putting half the coins on one side of the balance and half on the other side. There are an even number of coins total, so the number of equivalence classes with an odd number of coins is even. For half of these classes, we will put the bigger part on the right of the balance, and for the other half, put the bigger part on the left of the balance. Each equivalence class get cut in half (or as close to half as possible) with each weighing. This means that if the largest equivalence class has $k$ coins before some weighing, then after that weighing the largest class will have $\lceil k/2\rceil$ coins. At the start, the largest (only) equivalence class has 54 coins. Cutting in half (and rounding up) six times, we get that after the sixth division, each equivalence class has only a single coin. We are only allowed five weighings, so if we haven't had a balance after the fifth weighing, we know that the sixth division is balanced.

Answer 2

Yes.

Updated strategy after Joe Z's comment.

The key idea I'm going to use is that each use of the balance weighs all 54 coins. If we're lucky, it's going to be even and we're done, and if we're unlucky, we're going to repartition the 54 coins and try again, until we are done.

The question then becomes whether we in six rounds can partition 54 coins into two halves, such that any two coins are in different partitions in at least one round (the sixth round comes from the fact that if we haven't found a balance in the first five rounds, we can still repartition it one more time before presenting it to Cosmo). When the two fake coins are in different partitions, we are done.

Here is one partitioning strategy that works: Give each coin a unique number from 0-27 and 36-63 (see explanation below why I choose this numbering). To partition the coins, we are going to use the coin number's binary representation:

$$binary(0) = 000000 \\ binary(1) = 000001 \\ binary(2) = 000010 \\ ... \\ binary(63) = 111111$$

In the first round, place all coins whose binary representation's least significant bit is 0 in the first pan, and all coins with 1 in the second pan.

In rounds $n$ = two to five, use the same procedure, but instead split into partitions by the $n$th least significant bit.

If any of the rounds produce an even balance, we are done and can stop. If after five rounds we still haven't found an even partitioning, we know that the two fake coins only differ in the most significant bit. We can then put coins 0 through 26 in one pile and 36 through 63 in the other and present the result to Cosmo.

Proof sketch: If the fake coins have numbers $x$ and $y$ (where $x \neq y$), the game will end in round $i$, where $i$ is the least significant bit where $x$ is different from $y$, because at this round $x$ and $y$ are in different partitions. This is guaranteed to happen in six rounds or less, since 0-63 can be represented in six bits.

The new numbering strategy is chosen to guarantee that each round splits the coins in two parts of exactly 27 coins each. This is because for each coin number $i$, there is a complement coin $j$ with all its bits reversed (for example, the complement of 0 is 63, the complement of 10 is 53). This was not the case when numbering the coins 0-53, as I had done originally.

Answer 3

Step 1:
Make 3 groups of 18 coins: A,B,C.
Compare A to B and B to C. If A≠B and B≠C then A=C.
Select the 'odd' group (assume C) and note if it is lighter or heavier than the others. (assume lighter)
2 weighings used

Step 2:
Split C into 3 groups of 6: D,E,F.
Compare D to E. If D=E, F is the odd group. Go to 3a
If D≠E the lighter one is the odd group (assume D). Go to 3b
3 weighings used

Step 3a:
Split F in 3 groups of 2: G,H,I.
Compare G and H.

• If G≠H compare the lighter portion (assume G) with I.
  • If G=I, then A+D+G+(either coin of H)=B+E+I+(the other coin of H)
  • If G≠I, then H=I and A+D+H+(either coin of G)=B+E+I+(the other coin of G)
• If G=H, then A+D+G+(either coin of I)=B+E+H+(the other coin of I)

Step 3b:
Split D in 3 groups of 2: G,H,I.
Compare G and H.

• If G=H, compare D and F.
  • If D=F, then A+D+(any three coins of E)=B+F+(the other 3 coins of E)
  • If D≠F, then A+F+G+(either coin of I)=B+E+H+(the other coin of I)
• If G≠H, (assume G is the lighter one) compare I+(any 4 known good coins) and F.
  • If F<I+4, A+D+(any three coins of E)=B+F+(the other 3 coins of E)
  • If F=I+4, A+E+G+(either coin of D)=B+F+I+(the other coin of D)

The key here is to use the knowledge of whether the odd set of coins were lighter or heavier to help locate the fakes, if they are within the odd set of coins.

Answer 4

Yes! I think I did it! The trick was

to 'bag' the coins :)

Note for the below I skip trying to follow 'symmetric' and 'easier' paths to the solution.

Step 1.
Divide coins in 2 equal groups of 27. A, B
Weigh A vs B
If A == B you are done
If A > B go to step 2
If A < B the solution is symmetric to step 2


Step 2
Take 13 coins away from A and put in CA.
Take 13 coins away from B and put in CB.
Weigh A+CB with B+CA
If A+CB == B+CA you are done
If A+CB > B+CA goto step 3
If A+CB < B+CA goto step 3 (knowing A==B)

Step 3
We know that A>B from measurement 1, and that CA==CB since they didn't change the sum weight.
A and B each have 14 coins left.
Take 7 coins away from A and put in DA.
Take 7 coins away from B and put in DB.
Weigh A+DB and B+DA
If B+DA == A+DB you are done
If A+DB > B+DA goto step 4
If A+DB < B+DA similar to step 4 (knowing A==B)

Step 4
We know that A>B from measurement 1, and that DA==DB since they didn't change the weight.
A and B each have 7 coins remaining
Take away 3 coins from A calling them EA, and 3 coins from B calling them EB.
Weigh A+EB and B+EA
If A+EB == B+EA you are done
If A+EB > B+EA goto step 5
If A+EB < B+EA similar to step 5 (knowing A==B)

Step 5
We know that A>B from measurement 1, and that EA==EB since they didn't change the weight.
A and B each have 4 coins remaining
Take away 2 coins from A calling them FA, and 2 coins from B calling them FB.
Weigh A+FB and B+FA
If A+FB == B+FA you are done
If A+FB > B+FA then either A or B has both the two fake coins (you found them!)
If A+FB < B+FA then either FA or FB has both the two fake coins (you found them!)

Since either A or B, or, FA or FB, has both fake coins, take 1 coin from each and distribute.