Three Pan Balance, 15 Coins.

[wubie]

Hello,

I have encountered a question in my discrete mathematics class and I was wondering if I have solved it correctly. I can't remember the question to the word but I will try my best to state it correctly


You have 15 coins. One is counterfeit. You also have a three pan balance (like a three leaf clover without the stem and balanced where the three leaves meet). If one of the three pans is heavier, then the balance will tip to the heavier pan.

Given that you must pay $100 per weighing , how much must you pay to determine the counterfiet coin? That is, determine the counterfiet coin in as few weighings as possible.

If you can, find a nonadaptive solution.

An adaptive solution is a solution in which the action at each step is adapted to the outcome from the previous action.

A nonadaptive solution is a solution in which all the actions are fully predetermined.


Now I think I have come up with a NONADAPTIVE solution. And I believe that the counterfeit coin can be identified in two weighings.

First, label each coin 1 to 15. Then construct a table with a row from 1 to 15 (the number of each coin):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Under each numbered coin put a one if it is in the heavier pan. If not, put a zero.

First weighing:

Divide the fifteen coins into four groups; three groups of four, and one group of three.

Group one: 1,2,3,4
Group two: 5,6,7,8
Group three: 9,10,11,12
Group four: 13,14,15.

Weigh groups one to three against each other. Leave group four alone.

Record a one underneath the coins which are part of the heavy pan.

Second weighing:

Group one: 1,5,9,13
Group two: 2,6,10,14
Group three: 3,7,11,15
Group four: 4,8,12.

Once again weigh groups one to three against each other and leave group four alone.

Record a one underneath the coins which are part of the heavy pan for the second weighing.

Now look at the table. The coin with two ones underneath should be the counterfeit coin.

EXAMPLE: Let's say that 11 is the heavy coin. But we don't know it yet. Now execute the above algorithm.

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | Numbered Coins

0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 | First weighing

0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 | Second weighing


As you can see, there are two ones underneath the coin numbered 11. Which is exactly what we want.

Does this seem like a solid, nonadaptive solution?

Any thoughts on the subject are appreciated. Thankyou.

 

[Hurkyl]

I suppose you also know the counterfeit coin is heavier than the real thing?

Anyways, your solution looks good to me. As a plus, you can even tell if all 15 coins happen to be good!

 

[wubie]

Yes. The counterfiet is supposed to be heavier.

Thanks for looking this over Hurkyl. This was a question on my midterm today. I thought I did it correctly, but I wasn't sure; I didn't have time to check.

Cheers.

 

[Integral]

The problem is nearly trivial if you know that the counterfeit coin is heavier (or lighter). It can be done in 3 adaptive trials for 12 coins, without that knowledge. 15 may take 4, you may not know without an extra measurement whether the counterfeit coin is light or heavy.

Your algorithm is not clear to me, looks like you are making at least 4 measurements, with knowledge of the weight it is easy to do in 3 Your algorithm does not seem to guarantee the bad coin in as few measurements as possible. What is the number of measurements required to isolate the coin?

 

[Njorl]

2 weighings, non adaptive. You don't need to know ahead of time whether it is light or heavy.

seperate coins into 3 groups of 5.

put 4 of 5 on each pan. record.

for each group
- move one coin clockwise
- one counter clockwise
- one off of the pan
- put the unweighed coin on the groups original pan.
record

Njorl

Edited to add - I believe my solution is really the same as yours. You don't need to know if the fake is heavy or light ahead of time. At some point, one balance will be in a different position than the others. If it is up, the fake is light. If it's down, the fake is heavy.

 

[Integral]

In my initial post I missed the 3 pan balance. I assumed a 2 pan balance, now your algorithm make more sense!

 

[wubie]

Yes. It is a three pan balance. That makes the question a little less trivial.

As far as whether the coin is lighter or heavier, it believe it doesn't make a difference. It one pan is lighter than the other three, I would think that the two pans that are heavier and the same weight would cause the lighter pan to rise.

In any case I would also think the above solution would work - just put one underneath the pan with the light coin.

I haven't thought about it too much, but I don't see a problem with that.

Cheers.