1. Counterfeit Coin

Apparently a bit of a classic, but I hadn't seen this puzzle before:

"Given 11 coins of equal weight and one that appears identical but is either heavier or lighter than the others, use a balance pan scale to determine which coin is counterfeit and whether it is heavy or light. And do it with three weighings."

Alan

2. Re: Counterfeit Coin

OK, a bit of a tough one, so here's an example of how to do it with 3 coins in 2 weighings. Call the coins 1, 2 & 3 and let "L" represent the Left balance pan falling, "R" represent the Right pan falling and "B" represent the pans Balancing. The first weighing is done with 1 on the left pan and 2 on the right; the second with 1 on the left pan and 3 on the right. The possible outcomes and conclusions are as follows:

<table border=1><td> First </td><td> Second </td><td> Fake </td><td></td><td></td><td></td><td>L</td><td>L</td><td>1 (heavy)</td><td>L</td><td>B</td><td>2 (light)</td><td>L</td><td>R</td><td>not possible</td><td>B</td><td>L</td><td>3 (light)</td><td>B</td><td>B</td><td>no fake</td><td>B</td><td>R</td><td>3 (heavy)</td><td>R</td><td>L</td><td>not possible</td><td>R</td><td>B</td><td>2 (heavy)</td><td>R</td><td>R</td><td>1 (light)</td></table>

The extension to 12 coins incorporates the above, but there's also more to it.

Alan

3. Re: Counterfeit Coin

Several Solutions since with 3 weighings and 3 results of each, you have 27 outcomes and you only need 22 results 1-11 each either Hi or low:
<span style="background-color: #FFFF00; color: #000000; font-weight: bold"><font color=yellow>
1) 1234 vs 5678
Case a Left heavier: 1234 are Heavy, 5678 are Light , [9,10,11 are normal]
2) 125 vs 346
case a) Left heavier: 12 are heavy, or 6 is Light
3) 1 vs 2
Case a) Left heavy: 1 is heavy
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 2 is heavy
Case 3) Balance: 6 is Light

1) 1234 vs 5678
Case a Left heavier: 1234 are Heavy, 5678 are Light , [9,10,11 are normal]
2) 125 vs 346
case [img]/forums/images/smilies/cool.gif[/img] Right heavier: 34 are heavy, or 5 is Light
3) 3 vs 4
Case a) Left heavy: 3 is heavy
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 4 is heavy
Case 3) Balance: 5 is Light

1) 1234 vs 5678
Case a Left heavier: 1234 are Heavy, 5678 are Light , [9,10,11 are normal]
2) 125 vs 346
case c) Balanced: 78 Light
3) 7 vs 8
Case a) Left heavy: 8 light
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 7 light
Case 3) Balance: Not possible

1) 1234 vs 5678
Case b Right heavier: 1234 are Light, 5678 are Heavy , [9,10,11 are normal]
2) 125 vs 346
case a) Left heavier: 34 are light, or 5 is Heavy
3) 3 vs 4
Case a) Left heavy: 4 is light
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 3 is light
Case c) Balance: 5 is Heavy

1) 1234 vs 5678
Case a Right heavier: 1234 are Light, 5678 are Heavy , [9,10,11 are normal]
2) 125 vs 346
case [img]/forums/images/smilies/cool.gif[/img] Right heavier: 12 are Light, or 6 is Heavy
3) 1 vs 2
Case a) Left heavy: 2 is light
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 1 is light
Case 3) Balance: 6 is heavy
1) 1234 vs 5678
Case a right heavier: 1234 are Light, 5678 are Heavy , [9,10,11 are normal]
2) 125 vs 346
case c) Balanced: 78 Heavy
3) 7 vs 8
Case a) Left heavy: 7 Heavy
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 8 Heavy
Case c) Balance: Not possible

1) 1234 vs 5678
Case c Balanced 9,10,or 11 Counterfeit
2) 12 vs 9,10
case a) Left heavier: 9, 10 Light
3) 9 vs 10
Case a) Left heavy: 10 is light
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 9 is light
Case c) Balance: Not Possible

1) 1234 vs 5678
Case c Balanced 9,10,or 11 Counterfeit
2) 12 vs 9,10
case [img]/forums/images/smilies/cool.gif[/img] Right heavier: 9, 10 Heavy
3) 9 vs 10
Case a) Left heavy: 9 Heavy
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 10 heavy
Case c) Balance: Not Possible

1) 1234 vs 5678
Case c Balanced 9,10,or 11 Counterfeit
2) 12 vs 9,10
case c) 11 Counterfeit
3) 1 vs 11
Case a) Left heavy: 11 Light
Case [img]/forums/images/smilies/cool.gif[/img] Right heavy: 11 heavy
Case c) Balance: Not Possible</font color=yellow></span hi>

Steve

4. Re: Counterfeit Coin

Sorry to reply late to this Steve. I noticed the wording of this problem (not my own BTW) is a source of possible confusion. I think the "11 coins of equal weight and one that appears identical" would be better expressed as "11 coins of equal weight plus one that appears identical". That is, 12 coins in total. I've yet to read your solution in detail, so don't know if this will affect your method.

Alan

5. Re: Counterfeit Coin

Yes, I assumed only 11 coins total. The method is still valid though the solving of the last 4 (instead of 3 will be different).

No time now, but will work up a solution after I get home (I have a 10 hr trip tomorrow). I will flowchart it, it will be easier to see. I had none of my "tools" at my brother's house.

Steve

6. Re: Counterfeit Coin

Here is a solution in a table, (unforunately it seems tables do not "hide")

Steve
<span style="background-color: #FFFF00; color: #000000; font-weight: bold"><font color=yellow>
<table border=1><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>1</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>1 Heavy</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=right valign=bottom>----</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>6 Light</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>2</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>2 Heavy</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>1,2,5</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>7</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>8 Light</td><td align=right valign=bottom>-----</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>N/A</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>3,4,6</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>8</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>7 Light</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>3</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>3 Heavy</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=right valign=bottom>----</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>5 Light</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>4</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>4 Heavy</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>9</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>10 Heavy</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=right valign=bottom>----</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>11 Light</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>10</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>9 Heavy</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>1,2,3,4</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>9,10</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>1</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>12 Light</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>N/A</td><td align=center valign=bottom>5,6,7,8</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>11,1</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>12</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>12 Heavy</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>9</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>9 Light</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=right valign=bottom>----</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>11 Heavy</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>10</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>10 Light</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>3</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>4 Light</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=right valign=bottom>----</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>5 Heavy</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>4</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>3 Light</td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>1,2,5</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>7</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>8 Heavy</td><td align=right valign=bottom>------</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>N/A</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>3,4,6</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>8</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>7 Heavy</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>|</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>1</td><td align=center valign=bottom>---</td><td align=center valign=bottom>L</td><td align=center valign=bottom>2 Light</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=right valign=bottom>----</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>---</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>---</td><td align=center valign=bottom>B</td><td align=center valign=bottom>6 Heavy</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>2</td><td align=center valign=bottom>---</td><td align=center valign=bottom>R</td><td align=center valign=bottom>1 Light</td></table>
</font color=yellow></span hi>

7. Re: Counterfeit Coin

Very elegant presentation
You can "hide" a table by hiding each cell individually

StuartR

8. Re: Counterfeit Coin

<P ID="edit" class=small>(Edited by cbaldrey on 31-Dec-03 03:58. WAY TOO EARLY in the morning typo... I'm surprised I saw it!)</P>
<hr>You can "hide" a table by hiding each cell individually<hr>
Ouch... I'd love to see that coded in, but I'd also hate to be the one to type it out!

9. Re: Counterfeit Coin

Hi Steve

What with Xmas, the new board and my brain, it's a while since I got back to you on this. I like your solution, but the way I interpretted the problem suggested to me that what was being asked was a "universal" method, where the next weighing did not depend on the result(s) of the previous one(s)... like the method for the 3 coins I gave. After much headaching I came up with a method equivalent to this one (which I discovered elsewhere, and is easier to "document" than my homespun version).

<span style="background-color: #FFFF00; color: #000000; font-weight: bold"><font color=yellow>1 2 3 10 vs 4 5 6 11
1 2 3 11 vs 7 8 9 10
1 4 7 10 vs 2 5 8 12

Fake Heavy Light

10. Re: Counterfeit Coin

Alan,

It solves it using a "Design of Experiments" type of matrix. I saw a "similar" type of thought process when I learned to do DoE when the question was asked how do you determine the mass of 3 objects with a pan balance to get the best precision with the min of measurements
Typically you would just "balance" them each once (put one in the left balance and add the mass to the right until balanced)
Meas 1: 1 vs "MassA"
Meas 2: 2 vs "MassB"
Meas 3: 3 vs "MassC"

So Mass 1 = "MassA", Mass of 2 = "MassB", Mass of 3 = "MassC"
But you can improve the precision immensely by adding a 4th measurement! The secret is to always use all 4 objects in the measurement!
Meas 1: 123 vs "MassD"
Meas 2: 1 vs 23 + "MassE"
Meas 3: 2 vs 13 + "MassF"
Meas 3: 3 vs 23 + "MassG"

From these 4 determinations, you can get the individual masses and the precision is better since you have literally measured each item 4 times instead of only 1 time. Each mass is thus an "average of 4 measurements" and Each measurement error is spread among all the mass determinations.

I had solved it as a "logic" puzzle. I will have to keep your approach in mind for other types of puzzles of this sort!
Steve

11. Re: Counterfeit Coin

Alan,
I looked at your technique in a little more detail.

This method is pretty "general" and it will actually allow finding a counterfeit coin with only 4 weighings if there is a counterfeit coin in 39 coins (38 identical + 1 either heavy or light). [I have done this and leave this as a puzzle to those interested]

I am "almost"certain, that the simple "logic" approach I used originally could not be used in this case!

By extension 120 coins (119 identical + 1 either heavy or light) could be identified with only 5 weighings, though I haven't tried this.

Steve

12. Re: Counterfeit Coin

<hr>It solves it using a "Design of Experiments" type of matrix. <hr>
So that's how I did it? <img src=/S/grin.gif border=0 alt=grin width=15 height=15> Your background obviously included some emphasis on experimental design & planning. Mine unfortunately omitted any such emphasis, which I think is regrettable. Perhaps it was considered an optional luxury for the engineering side of science, but it was something I had to pick up on myself when I entered the R&D area and always wished I'd had the formal discipline. I even had to learn by experience that a sample size of 4 was the go for statistical analysis (pre-computer calculation days).

I must look up these terms you used and start my formal training. <img src=/S/grin.gif border=0 alt=grin width=15 height=15>

Alan

13. Re: Counterfeit Coin

I received none of it (unfortunately) in my "formal education" (undergrad and graduate work). It was all learned in courses I took after starting my job.

If you need more info on "your method" I could give you "my interpretation" of it regarding this puzzle and how to use it to find other solutions (there is not 1 unique solution) to your original post and to extend it to larger sets.

<img src=/S/rant.gif border=0 alt=rant width=66 height=37>
I think it is a "major" problem in the education of scientists (which I think also includes engineers, though you usually hear the term "scientists and engineers" <img src=/S/grin.gif border=0 alt=grin width=15 height=15>). Formal education teaches "one factor at a time"-type of thinking which is inefficient and more prone to "errorneous conclusions" from the more "imprecise" data.

Steve

14. Re: Counterfeit Coin

Steve

I'm afraid I wouldn't know how to "formalize" my method if you paid me. The closest I could come is to compare it to Sherlock Holmes approach - if you eliminate all but one from the frame, then you must be left with the guilty party. In my case, I started trying to generate a set of outcomes analagous to the 3 coin problem, and as each successive approach failed <img src=/S/disappointed.gif border=0 alt=disappointed width=15 height=15> the next attempt was born. Given that there are a finite number of weighing possibilities, I guess I had to hit on a working one eventually. <img src=/S/grin.gif border=0 alt=grin width=15 height=15>

I'd certainly be interested in a better explanation of what I did (or perhaps what I'd have done if I knew what I was doing <img src=/S/grin.gif border=0 alt=grin width=15 height=15> ) than the one above.

Alan

15. Re: Counterfeit Coin

I am going to try to discuss this without "too much" of the Design of Experiments nomenclature and concentrate more on how to solve this puzzle with "your methodology".

It is important to realize several things (some more obvious than others):
1) Each "weighing" (I will probably move in and out with my "precision": a balance does not "weigh" but compares mass, but weighing is a verb and shorter than saying comparing masses all the time<g>) gives you 3 pieces of info (Left, Right, Balance)
2) Each piece of info can only tell you only 1 thing
3) Just because you have enough pieces of info to theoretically determine all the items, the proper choice of "experiments" is required to make sure the design has independent determinations and the effects of each can be determined.
4) Even though you compare the masses together (adding multiple items onto each "pan of the balance" the masses remain independent of one another - there are no interactions between the different masses.

In the problem as stated we have 12 coins and 3 weighings. With 3 weighings we have 27 "possible" outcomes (3*3*3 = 27). We need only 24 [=12 coins * 2 potentials (Heavy or light)] of these possibilites to answer the question. If you note from my "flowchart" the other 3 are "not possible" due to "constraints" of problem.

[Note that one of these is possibilities (balancing all 3 times) could be used to answer the Problem:
Given 12 coins. 11 of which are identical, the 12th is either heavier, lighter, or identical to the others. With only 3 uses of a pan balance, determine if all the coins identical or if not determine which coin is different and if it is heavier or lighter.]

Given a number of weighings, you might wonder how to determine the max coins that are "testable" for the 1 "bad one". For 3 weighings: Start with the total possibilites (3^3 = 27). Remove 1 for completely balancing (26). Divide by 2 for heavy/light (13). "Theoretically" we could do 13 coins, but we are limited since to to this puzzle each weighing must be in thirds: 1/3 in left pan, 1/3 in right, and 1/3 not weighed. Thus the largest number <=13 that is divisible by 3 is 12. Each pan will contain 4 coins in each weighing.

For 2 weighings, you can determine that: (3^2 - 1)/2 = 4, so only 3 coins maybe determined.
For 4 weighings (3^4 - 1)/2 = 40, so 39 coins are possible.

[Note: if you define in the puzzle that the coin is HEAVY, then the number of coins that can be tested is double! With weighings you can test 24 coins IF you say the "counterfeit coin" is Heavier (or is lighter)]

The question comes which coins do you place in the pans for each weighing

Let's start with the simple case of only 2 weighings. With 2 weighings we will get 9 pieces of info as there are 9 (=3 * 3) possibilities:

<table border=1><td align=center valign=bottom></td><td align=center valign=bottom>1</td><td align=center valign=bottom>2</td><td align=center valign=bottom>1</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>2</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>3</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>4</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>5</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>6</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>7</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>8</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>9</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td></table>

There are 2 things to note:
A)The values in the list have "symmetry":
1 is opposite to 9
2 is opposite of 8
3 opposite 7
4 opposite of 6

[img]/forums/images/smilies/cool.gif[/img] One value (all balancing= 5) "stands alone"

[The "one" value is why you subtract 1, and the "pairs" are the reason for the divided by 2, you must be divisible by three since you have 3 results: L, B, R]

For 2 weighings (as I stated) you can determine 3 coins: each weighing should have 1 in left, 1 in right, and 1 not weighed. The "key" is that the setup must be "balanced" (pun intended). You will assign the "results" of each weighing to one of the coins. The results come in PAIRS however. For example if you assign coin 1 "heavy" to result 1 (LL) then you automatically assign the "light" to its "reverse" (9 = "RR"). None are assigned to the "balanced" result (5). The 3 result "pairs" you choose must equal numbers of Ls, Bs, and Rs ("balanced") so the 3 I choose to assign must have 1L, 1B, and 1R for each weighing.

So if coin 1 Heavy is 1 (LL), then coin 2 cannot be result 2(LB) since you must have either a B or R in the first slot and a B or R in 2nd. So you can choose for Coin 2 (heavy) to be 6 (BR) and that leaves 8 (RB) for coin 3 (heavy) It also means that 1 light is RR (opp of LL), 2 light is BL (opp of BR) and 3 light is LB (opp of RB).

For the first weighing look at the first item in the series (123 = LBR) so that you will have:
1 in left vs 3 in right (2 not weighed)
and for the second (123 = LRB):
1 in left vs r in right (3 not weighed).

You work similarly with 3 weighings 27 results:
<table border=1><td align=center valign=bottom>Coin</td><td align=center valign=bottom>Result</td><td align=center valign=bottom>1</td><td align=center valign=bottom>2</td><td align=center valign=bottom>3</td><td align=center valign=bottom>1</td><td align=center valign=bottom>1</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>2</td><td align=center valign=bottom>2</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>3</td><td align=center valign=bottom>3</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>4</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>5</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>6</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>10</td><td align=center valign=bottom>7</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>8</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>9</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>10</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>11</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>12</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>13</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>14</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>11</td><td align=center valign=bottom>15</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>4</td><td align=center valign=bottom>16</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>5</td><td align=center valign=bottom>17</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>6</td><td align=center valign=bottom>18</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>19</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>12</td><td align=center valign=bottom>20</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>21</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>7</td><td align=center valign=bottom>22</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>8</td><td align=center valign=bottom>23</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>9</td><td align=center valign=bottom>24</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>25</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>26</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>27</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td></table>

I assigned them in "triplets" so that the 3rd weighing would always be balanced (one of each), then the first 2 are identical to the "2 weighing case". This yields a "balanced 9" and for the last 3 it is just a matter of find 3 that balanced on their own

this results in the "weighings"
<table border=1><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>Left</td><td align=center valign=bottom>pan</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>right</td><td align=center valign=bottom>pan</td><td align=center valign=bottom></td><td align=center valign=bottom>1</td><td align=center valign=bottom>1</td><td align=center valign=bottom>2</td><td align=center valign=bottom>3</td><td align=center valign=bottom>10</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>7</td><td align=center valign=bottom>8</td><td align=center valign=bottom>9</td><td align=center valign=bottom>12</td><td align=center valign=bottom>2</td><td align=center valign=bottom>1</td><td align=center valign=bottom>2</td><td align=center valign=bottom>3</td><td align=center valign=bottom>12</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>4</td><td align=center valign=bottom>5</td><td align=center valign=bottom>6</td><td align=center valign=bottom>10</td><td align=center valign=bottom>3</td><td align=center valign=bottom>1</td><td align=center valign=bottom>4</td><td align=center valign=bottom>7</td><td align=center valign=bottom>10</td><td align=center valign=bottom>vs</td><td align=center valign=bottom>3</td><td align=center valign=bottom>6</td><td align=center valign=bottom>9</td><td align=center valign=bottom>11</td></table>

With the results interpretation:
<table border=1><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>Heavy</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>Light</td><td align=center valign=bottom></td><td align=center valign=bottom></td><td align=center valign=bottom>1</td><td align=center valign=bottom>2</td><td align=center valign=bottom>3</td><td align=center valign=bottom></td><td align=center valign=bottom>1</td><td align=center valign=bottom>2</td><td align=center valign=bottom>3</td><td align=center valign=bottom>1</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom>2</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>3</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>4</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>5</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>6</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>L</td><td align=center valign=bottom>7</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom>8</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>9</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>10</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom></td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>11</td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>R</td><td align=center valign=bottom></td><td align=center valign=bottom>B</td><td align=center valign=bottom>B</td><td align=center valign=bottom>L</td><td align=center valign=bottom>12</td><td align=center valign=bottom>R</td><td align=center valign=bottom>L</td><td align=center valign=bottom>B</td><td align=center valign=bottom></td><td align=center valign=bottom>L</td><td align=center valign=bottom>R</td><td align=center valign=bottom>B</td></table>

I hope this explains the "logic" of my "interpretation". If you need more clarification, let me know.

Steve

Page 1 of 2 12 Last

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•