6
$\begingroup$

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?

|improve this question
$\endgroup$
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Shouldn't it be 9!/(3!^3) because the order in each of the three groups is arbitrary? $\endgroup$ – hexomino Sep 9 '18 at 22:39
  • $\begingroup$ Yep, thanks for the catch. I thought I might have done something wrong. I think I might also have found a strategy that uses less than 11. Further proving that my lower bound is wrong. $\endgroup$ – Bennett Bernardoni Sep 9 '18 at 22:42
  • $\begingroup$ Does it include weighings with several coins on one pan? Or is it banned? $\endgroup$ – rus9384 Sep 10 '18 at 18:17
  • $\begingroup$ @rus9384 The method given above only weighs one coin on each side at a time. I'm guessing a better method might not follow this to achieve better result. However, we don't know the densities so a dense coin might be heavier than two less dense coins. $\endgroup$ – Bennett Bernardoni Sep 10 '18 at 19:01
  • $\begingroup$ I guess there is an algorithm that does this in 8 weighings, but not sure the one doing it in 7 exists. $\endgroup$ – rus9384 Sep 10 '18 at 20:43
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ I think you forgot a coin. There are nine in total and you only weigh 1 against 7 for a total of 8. Furthermore, I made a mistake in my math and got the lower bound wrong. See my edit for a correct (I hope) lower bound and upper bound (that is lower than my previous lower bound). $\endgroup$ – Bennett Bernardoni Sep 9 '18 at 23:19
  • $\begingroup$ Nevermind about the forgotten coin, I just misunderstood your method. The rest of my comment applies though. $\endgroup$ – Bennett Bernardoni Sep 9 '18 at 23:57
  • $\begingroup$ Bennett's lower bound is about worst case scenario. In yours it is 11 weighings. $\endgroup$ – rus9384 Sep 10 '18 at 18:27
  • $\begingroup$ @rus9384 my original lower bound was 11. That's what I'm talking about in my comment above $\endgroup$ – Bennett Bernardoni Sep 10 '18 at 19:03

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.