strategy - Fifty-two genuine and two fake coins

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

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.