There are 9 coins that look the same but only one of them is real.
They have different weights. There are only three possibilities
for their weights. Four coins are slightly heavier and four coins are slightly lighter
than the real coin.
The balance scale allows any number of coins
on each pan.
Find the real coin in not more than seven weighings.
How about six weighings?
We are given a mix consisting of four equal heavy coins, four equal light coins, and one real coin whose weight is somewhere inbetween. The goal is to find that coin.
First note that the only way an equal weighing can occur is if the real coin is not on the scale. Any coin in an equal weighing is known to be one of the heavy or light coins immediately.
Weigh four different 1v1 pairs for the first four weighings. Eight coins will have been on the scale once each and one odd coin will be unweighed. The results can have from 0 to 4 equal weighings.
Case 1: 4 equal weighings
All coins weighed are heavy/heavy or light/light pairs. The odd coin is the real coin.
4 weighings
Case 2: 3 equal weighings
The real coin is one of the two in the unequal weighing. The odd coin is the same weight as the coin that was compared to the real coin. Compare the odd coin to one of the two from the unequal pair to find out which is the real coin.
5 weighings
Case 3: 2 equal weighings
The two equal weighings must consist of one heavy/heavy pair and one light/light pair. Compare the two heavier coins from the unequal weighings. If unequal then the lighter coin is the real coin, else both are heavy coins. Then compare the two lighter coins from the unequal weighings. If unequal then the heavier coin is the real coin, else both are light coins. When both of those weighings are equal, the odd coin is the real coin.
6 weighings
Case 4: 1 equal weighings
The real coin must be in one of the unequal weighings. Also, all three unequal weighings have a coin which is the same weight as the odd coin. Call four coins from the unequal weighings A, B, C, and D such that A>B and C>D. Make the fifth weighing A+B vs C+D.
Subcase 4.1: A+B=C+D
A and C are heavy coins and B and D are light coins. The real coin is one of the two in the last unequal weighing. The other one of these two is the same weight as the odd coin, just like in Case 2. Compare the odd coin to one of the two from the unequal pair to find out which is the real coin.
6 weighings
Subcase 4.2: A+B>C+D
A is heavy, D is light, and the real coin is one of B or C. Weigh A+D vs B+C, which must be unequal. A+D>B+C means that C is real and B is light. B+C>A+D means B is real and C is heavy.
6 weighings
Subcase 4.3: C+D>A+B
C is heavy, B is light, and one of A and D is the real coin. Weigh A+D vs B+C, which must be unequal. A+D>B+C means that D is real and A is heavy. B+C>A+D means A is real and D is light.
6 weighings
Case 5: 0 equal weighings
Label the coins A-I such that A>B, C>D, E>F, G>H, and I is the odd coin. Four of A, C, E, G, and I are heavy and four of B, D, F, H, and I are light. The real coin can be any of the nine coins. Make the fifth weighing A+B+C vs E+F+G.
Subcase 5.1: A+B+C>E+F+G
The real coin is one of B, E, or G. If B is not real then it is light, also if E or G are not real then they are heavy. Weigh E vs G. If E=G then B is the real coin. If E>G then G is the real coin. If G>E then E is the real coin.
6 weighings
Subcase 5.2: E+F+G>A+B+C
The real coin is one of A, C, or F. If F is not real then it is light, also if A or C are not real then they are heavy. Weigh A vs C. If A=C then F is the real coin. If A>C then C is the real coin. If C>A then A is the real coin.
6 weighings
Subcase 5.3: A+B+C=E+F+G
Each side has 2 heavy and 1 light coin. The real coin is one of D, H, or I. The other two are both light. Weigh D vs H. If D=H then I is the real coin. If D>H then D is the real coin. If H>D then H is the real coin.
6 weighings