Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
You are a lab assistant and your prof asked you something very specific: There are $9$ coins made of three different materials with different densities in front of you, but they look the same, divide these $9$ coins into three different material group. It is also known that there are 3 coins for each material type.
What is the least amount of weighing required to guarantee you divide these coins into three different material group by using a two pan arm scale?
I found a range of possible weighings so far.
7-9 weighings
I got a lower bound with the following reasoning.
First find the total number of ways the 3 groups can be partitioned. There are $9!$ permutations of 9 coins but there are $3!$ ways each group can be ordered. This gives a total of $\frac{9!}{3!^3} = 1680$ combinations. Also thanks to @hexomino for catching my earlier mistake in the comments.
With $n$ weighings there are 3 outcomes per weighing for a total of $3^n$ outcomes. To get at least 1680 outcomes we need $\left \lceil{\log_3 1680}\right \rceil = \left \lceil{6.759936}\right \rceil = 7$ weighings.
This is a lower bound so 7 might not be possible due to some unforeseen issue.
Now here is a scheme that gives an upper bound.
Step 1) Pick the first coin and put it in group A.
Step 2) Pick another coin and weigh it against a coin in A. Put it in group A if the scales are balanced or group B otherwise.
Step 3) Repeat step 2 until there are two coins in group B.
Step 4) If the coins both weighed less or both weighed more then A, continue on otherwise goto end 1.
Step 5) Weigh the two group B coins against each other. If they are the different goto end 2.
Step 6) Repeat step 2 until we get a third coin. If all three coins tipped the scale the same direction, continue on otherwise goto end 3.
Step 7) Weigh the third coin against one of the other coins in group B. If it is different goto end 4 otherwise goto end 5.
End 1) We got lucky with A being a middle coin. Move one of the group B coins to C. Weigh the rest of the coins against A moving them to their matching group. We can stop when any two groups have 3 coins. This will result in a maximum of 7 weighings.
End 2) We now know a middle coin. Move this coin to group C. Weigh the rest of the coins against C moving them to their matching group. We can stop when any two groups have 3 coins. This will result in a maximum of 8 weighings.
End 3) We now know A is a middle coin. Move third coin to group C. Weigh the rest of the coins against A moving them to their matching group. We can stop when any two groups have 3 coins. This will result in a maximum of 8 weighings.
End 4) We now know a middle coin. Move this coin (and possible matching coin) to group C. Weigh the rest of the coins against C moving them to their matching group. We can stop when any two groups have 3 coins. This will result in a maximum of 9 weighings.
End 5) Group B is now complete. Keep weighing coins against A but now putting different weighing coins in group C. We can stop when any two groups have 3 coins. This will result in a maximum of 9 weighings.
Since all endings give a maximum of 9 weightings, 9 is an upper bound.
A method that meets Bennett's now improved-upon lower bound is as follows. First let the masses be L < M < H
Choose a coin A and weight it against each of seven other coins - placing each of the weighted coins in one of three piles l (for lighter), s (for same) and h for heavier than coin A.
If you are lucky and A was M, then the piles will be 223, or 313, or 322. Then you know the unweighed coin is L, M, or H, respectively (and know A is M) so have done the job in 7 weighings total.
If A was L then the piles lsh will have number of coins 016 or 025 (depending on whether the final coin was L or not). And you know the final unweighed coin is L, or either M or H, respectively (and know A is L). So now choose a coin B from the 6 in the heavier pile (consisting M and H coins). Weight it against each of four remaining coins in that pile.
If B is M, then you will get sh = 22, or sh = 13. So the unweighed coin of the six is H or M respectively (and know B is M). This would complete the sorting in a total of 11 weighings.
If B is H, you will get ls = 22, or 31, confirming the final coin is M or H respectively (and B is H). Also for 11 weighings total.
By symmetry, if A is H you can follow an effectively identical process to that above and still get the sorting done in 11 goes.
