wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Counterfeit coin.
        
(Message started by: rloginunix on Oct 29^th, 2013, 7:37pm)

Title: Counterfeit coin.
Post by rloginunix on Oct 29^th, 2013, 7:37pm

Counterfeit coin.

Using only three measurements on the pan-scales find the only counterfeit coin out of 27 knowing that it's slightly heavier than the real ones.

Title: Re: Counterfeit coin.
Post by jollytall on Oct 29^th, 2013, 10:42pm

3^3

Title: Re: Counterfeit coin.
Post by rmsgrey on Oct 30^th, 2013, 4:29am

000-222

Title: Re: Counterfeit coin.
Post by rloginunix on Oct 30^th, 2013, 10:48am

jollytall is correct.

I apologize if my puzzle is perceived as a duplicate. Couldn't get the hang of the search functionality initially but promise to do better next time.

Solution.

I used the Division and Elimination approaches to solve it. Divide 27 coins into 3 9-coin piles. Pick two piles at random and place them on the scales. Leave the third pile on the table.

Measurement one. If scales register no weight difference then the fake coin is in the table pile - eliminate 18 good coins off the pans. If weight difference is registered then the pile on the heavier pan has the fake coin - eliminate 18 good coins anyway - one from the table and one from the lighter pan.

Repeat. Divide remaining 9 coins into 3 3-coin piles. Place two random 3-coin piles on the scales, leave one pile on the table. That's measurement two. Apply the above logic and eliminate 6 more coins, 18+6=24 coins total after two measurements.

Repeat. Divide remaining 3 coins into 3 one-coin piles...

Title: Re: Counterfeit coin.
Post by jollytall on Oct 30^th, 2013, 10:50am

Yes, but if you like these kind of questions then here is another (surely on the site already):
12 coins, one counterfeit. We do not know which one and whether the weight is more or less than the others. 3 measurements please with the same scale.

Title: Re: Counterfeit coin.
Post by rloginunix on Oct 30^th, 2013, 11:28am

Yes. While trying to master the search functionality on this site I've seen someone asking the unknown relative weight question.

I'll start with a primitive case - 3 coins, 1 fake with relative weight unknown.

My solution path.

Divide 3 coins into 3 one-coin piles. Place two random ones on the scale. Leave the third on the table. Name T = coin on the table, L = coin on the left pan, R = coin on the right pan.

If L = R then the fake coin is T. To deduce it's relative weight we need one more measurement - swap T with L or R, keep the state - remember which one is which and after the second measurement we will know which coin is fake and if it's lighter or heavier than the good ones.

If L != R then the T coin is good and can be used as a standard. Need one more measurement. Keep the state, swap T with L or R. Let's say L is the good coin now.

If L = R then the T coin is fake and if we kept the state we can tell if it was heavier or lighter from the first measurement.

Otherwise R is heavier or lighter and by observing the scale we can tell its relative weight.

So need two measurements to answer two questions - which one is fake and what's its relative weight.

Be back with 12.

Title: Re: Counterfeit coin.
Post by rloginunix on Oct 30^th, 2013, 10:36pm

Boy, I thought it would be easy but did this puzzle send a silly old goose like me for a loop.

First I though I'd show some of my real time thinking process but then after 5 sheets of paper covered with a mad man's scribbles, four hours and a missed lunch I lost track of my own thought. I'll just mention some snippets here and there, show my deductions as I came across them and tell where I had the biggest problems.

First I tried to divide 12 into piles of 2x6, 3x4, 6x2. Tried the straight Division and Elimination. Failed miserably. Then I though how about 3+3+6 and 5+5+2? Failed miserably. Now the gloves were off. After some more tinkering I realized - need to keep more state. That's the key. Similar to what I've used in the primitive 3-coin case above - the result of the previous measurement is used in the current one.

After much trial and error I've settled on 4+4+4 grouping for the first test as the hunch was that this configuration eliminates the most coins in one go. When I came to testing a 4+4 pair I tried 2+2+6, 3+3+2 and 4+4 configurations. Only the middle one - 3+3+2 worked out. Keeping track of all the permutations tried and failed was a real pain in the neck. I've got the first part when the pans are at equilibrium relatively quickly. But, man, did I get stuck when they were not. Tried all kinds of crazy combinations until it dawned on me - there is only one bad coin, that's all you have to rearrange. That's another approach I had to use by the way - Rearrangement. I lost track of time but a total of 10 hours sounds right.

Being an old C/UNIX programmer my final solution will look like a good old C program but don't sweat it - it's easy. I will only use the if statement for clarity. If English words say this "if X equals to Y then Z is a fifth derivative of the triangulation tensor" then in a C-like fashion I will use this:

if A = B
{
Z = foo
}

You are a smart bunch, you'll get the hang of it.

My L and R notations are the same as above. For example, the following C-like snippet:

if L(1, 2, 3) = R(4, 5, 6)
{
blah blah
}
else if L(1, 2, 3) > R(4, 5, 6)
{
blah blah
}
else if L(1, 2, 3) < R(4, 5, 6)
{
blah blah
}

In English becomes long, tedious and hard to read and grasp (for me at least) - put the coins marked 1, 2 and 3 on the Left pan and put the coins marked 4, 5 and 6 on the Right pan and perform exactly one measurement. If the coins on the left pan weigh as much as the coins on the right pan then blah blah and if the coins on the left pan weigh more than the coins on the right pan then blah blah otherwise - the only choice left - if the coins on the left pan weigh less than the coins on the right pan then blah blah.

Code is easy on my eyes, that's what I do for living. When you will read it pay attention to the coin numbers. That's where I've used the Rearrangement approach. When you see the Ls and Rs with one argument then the arguments are either the suspects or good coins - read the deductions directly above the test.

The site is telling me my post is too long. So here we go. Cutting it. See solution in the next one.

Title: Re: Counterfeit coin.
Post by rloginunix on Oct 30^th, 2013, 11:08pm

Solution.

Mark all the coins with the base 10 decimals in the ascending order: 1, 2, 3, 4, ..., 11, 12.

Place the first four on the left pan, the next four on the right pan, keep the next four on the table.

execute the first measurement
if L(1, 2, 3, 4) = R(5, 6, 7, 8 )
{
coins 1-8 are all good.
bad coin is one of 9-12.
execute the second measurement.
if L(6, 7, 8 ) = R(10, 11, 12)
{
coin 9 is bad.
execute the third and final measurement.
if L(9) > R(12)
{
return answer = coin 9 is bad and heavier.
}
else
{
return answer = coin 9 is bad and lighter.
}
}
else if L(6, 7, 8 ) < R(10, 11, 12)
{
bad coin is heavier.
bad coin is one of 10-12.
execute the third and final measurement.
if L(11) = R(12)
{
return answer = coin 10 is bad and heavier.
}
else
{
return answer = coin in the lower pan is bad and heavier.
}
}
else if L(6, 7, 8 ) > R(10, 11, 12)
{
bad coin is lighter.
bad coin is one of 10-12.
execute the third and final measurement.
if L(11) = R(12)
{
return answer = coin 10 is bad and lighter.
}
else
{
return answer = coin in the higher pan is bad and lighter.
}
}
}
else if L(1, 2, 3, 4) < R(5, 6, 7, 8 )
{
coins 9-12 are all good.
bad coin is one of 1-8.
execute the second measurement.
if L(2, 3, 4, 5) = R(1, 9, 10, 11)
{
coins 1-5 are all good.
one of coins 6-8 is bad.
bad coin is heavier.
execute the third and final measurement.
if L(7) = R(8 )
{
return answer = bad coin is 6 and heavier.
}
else
{
return answer = coin in the lower pan is bad and heavier.
}
}
else if L(2, 3, 4, 5) < R(1, 9, 10, 11)
{
coin 1 must be good - it didn't change the balance.
coin 5 must be good - it didn't change the balance.
bad coin is one of 2-4.
bad coin is lighter.
execute the third and final measurement.
if L(3) = R(4)
{
return answer = bad coin is 2 and lighter.
}
else
{
return answer = coin in the higher pan is bad and lighter.
}
}
else if L(2, 3, 4, 5) > R(1, 9, 10, 11)
{
coins 1 and 5 flipped the balance.
bad coin = either 5 and heavier OR 1 and lighter.
execute the third and final measurement.
if L(5) = R(12)
{
return answer = bad coin is 1 and lighter.
}
else
{
return answer = bad coin is 5 and heavier.
}
}
else if L(1, 2, 3, 4) > R(5, 6, 7, 8 )
{
if L(2, 3, 4, 5) = R(1, 9, 10, 11)
{
coins 1-5 are all good.
bad coin is one of 6-8.
bad coin is lighter.
execute the third and final measurement.
if L(7) = R(8 )
{
return answer = bad coin is 6 and lighter.
}
else
{
return answer = coin in the higher pan is bad and lighter.
}
}
else if L(2, 3, 4, 5) > R(1, 9, 10, 11)
{
coins 1 and 5 must be good - they didn't change the balance.
bad coin is one of 2-4.
bad coin is heavier.
execute the third and final measurement.
if L(3) = R(4)
{
return answer = bad coin is 2 and heavier.
}
else
{
return answer = coin in the lower pan is bad and heavier.
}
}
else if L(2, 3, 4, 5) < R(1, 9, 10, 11)
{
coins 1 and 5 flipped the balance.
bad coin = either 1 and heavier OR 5 and lighter.
execute the third and final measurement.
if L(5) = R(12)
{
return answer = bad coin is 1 and heavier.
}
else
{
return answer = bad coin is 5 and lighter.
}
}
}

Title: Re: Counterfeit coin.
Post by rloginunix on Oct 30^th, 2013, 11:16pm

Another thought occurred to me. But it would have to wait many many weekends.

I think a solution with Rearrangement approach applied to the number's base may also exist. The standard technique here is to start with a base 10 number, convert it to base 2 (or 3 in this case), manipulate it in some way in a different base, then convert the number back to base 10.

I just need to find a way to connect a bit-pattern to the suspect coin number. But that would have to wait.

Title: Re: Counterfeit coin.
Post by towr on Oct 30^th, 2013, 11:27pm

You can simplify the solution a lot by renumbering after each measurement (use pointers ;) ).

Title: Re: Counterfeit coin.
Post by jollytall on Oct 31^st, 2013, 12:35am

You do not need to work out left>right and left<right in the first measurement to explain. These are symmetrical, assuming the counterfeit being false in the other direction. This simplifies a lot. A solution:

if abcd=efgh
if ij>ka
if ik>ab then i heavy
if ik=ab then j heavy
if ik<ab then k light
if ij=ka then
l<>a gives the solution (l=a IMPOSSIBLE, one of the 27-24=3 lost cases)
if ij<ka is symmetrical to ij>ka

if abcd>efgh
if abef>gcij then
if ag>ij then a heavy
if ag=ij then b heavy
if ag<ij then g light
if abef=gcij then
if d>a then d heavy
if d=a then h light
if d<a IMPOSSIBLE (one, or with symmetry two, of the 27-24=3 lost cases)
if abef<gcij then
if ce>ij then c heavy
if ce=ij then f light
if ce<ij then e light

Title: Re: Counterfeit coin.
Post by rmsgrey on Oct 31^st, 2013, 6:37am

The next trick is to specify three weighings in advance so that you can just request those three measurements be done and come back, look at the results and determine the correct answer - for 27 coins with one heavier, number them from 0 to 26 in ternary (000 to 222), associate each weighing with a position - so the first weighing is the first trit; the second, the second; third, third. In each weighing, put the coins with a 1 in that position on the left pan; with a 2 on the right; and 0s leave out. For the results, put down a 0 if the pans balance, a 1 if the left was heavier, and a 2 if the right, and you will create the ternary number of the heavy coin.

Title: Re: Counterfeit coin.
Post by rloginunix on Oct 31^st, 2013, 2:42pm

All the points are taken, guys. Well done, well done. I see you've spent quite a bit of time on this problem. I just was able to find a solution in principle. Which proves one more time that the first take is not the most optimal. If at first you succeed try and try again.

rmsgrey, at a time I honestly didn't know what you meant in your first post. Only after solving the 12-coin problem did I get it. Came up with a hypothesis and now you took away my fun of searching for a bit-patterned solution. Oh, well. At least now I know my hunch was right. Please give me a warning next time.

Thanks everyone.

Title: Re: Counterfeit coin.
Post by rloginunix on Oct 31^st, 2013, 5:21pm

Now. I was thinking. Since the cat is out of the bag and I planned to use it as a template anyway where would the parallel with the poisoned wine versus lab mice problem take me?

So what you, guys, are saying is this:

bottle = coin
poison = fake
mice = scales
dead/alive -> base 2 = </=/> -> base 3
multiple feeds to one mouse = multiple coins on one pan
wine to mouse iff the bit in that position of bottle's # is 1 = coin on L/R pan if it's # has 1/2 in bit position == weighing #
which means that: bottle # = weighing #
waiting for mice to kick the bucket = null
bit pattern of dead mice = bit pattern of fake coin

Interesting how on the surface quite different problems reveal quite a bit of similarity upon deeper investigation.

Math wizards out there can use this as a template to create more like problems or problems where more than 3 outcomes are possible.

Title: Re: Counterfeit coin.
Post by rmsgrey on Nov 1^st, 2013, 8:03am

on 10/31/13 at 14:42:12, rloginunix wrote:

rmsgrey, at a time I honestly didn't know what you meant in your first post. Only after solving the 12-coin problem did I get it. Came up with a hypothesis and now you took away my fun of searching for a bit-patterned solution. Oh, well. At least now I know my hunch was right. Please give me a warning next time.

The 12-coins-with-fixed-weighings is still open to you.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 1^st, 2013, 12:17pm

Got it.

Actually, I've missed a key observation yesterday - number of weighings/lab mice (in base 10) is equal to the number of bits used to count the coins/bottles in base 3/2.

From that a question popped into my head. What is the maximum number of coins that can be tested for one fake coin in exactly N tests? (previous conditions standing - relative weight is unknown).

Solving this problem I will also solve the 12-coin bit-pattern problem.

Don't have much free time right now but N tests mean N bits. Each bit can carry three unique values 0, 1, 2. Order matters, 01 != 10. Repetitions are allowed, 111 is ok. So it's permutations with repetitions. Which is n to the power of r. In our case n = 3, r = N. So the maximum number of items we can enumerate with N tests is 3 to the power of N.

It feels that something must be subtracted from 3^N and then divided or the other way around only because with the 12-coin problem the number of tests is 3 and 3^3 is 27. However, only 12 coins can be tested. How do we get 12 from 27?

That's what will keep me busy. Be back with my findings in a while.

Title: Re: Counterfeit coin.
Post by jollytall on Nov 1^st, 2013, 11:50pm

Before you spend too much time: it is 24 out of 27, so only 3 are "lost". You find those 3 lost in my posting above.

Title: Re: Counterfeit coin.
Post by rmsgrey on Nov 2^nd, 2013, 8:29am

You have 12 coins, one of which weighs differently than the others, and can be heavier or lighter, which gives you 24 possibilities.

This level of analysis rules out picking out the odd coin and determining whether it's heavy or light from among 14 coins in just 3 weighings (28 possibilities can't be shared among 27 outcomes without at least one doubling up).

Deciding the 13-coin case takes a bit more work - as I recall, if you look at possible first weighings, there's no weighing that divides the outcomes 9:9:8, so no way to guarantee being able to decide among the remaining outcomes in the latter two weighings.

You can also conclude that the case where the scales balance each time can't tell you whether the odd coin is heavier or lighter, so can't be a valid sequence.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 2^nd, 2013, 11:56am

Before I chew on your comments, guys, if you don't mind, let me dump my findings so far before I forget them or get affected by your observations.

Driving home last night couldn't write but talked to my brain. The maximum number of items I can enumerate is 27 but the most I can test is 12. Where do 15 numbers go? And why? Why, why, why.

OK, they must be eliminated. That's the only choice I see. How? Dealing with bits here. When the current bit runs through all the allowed numbers 0, 1, 2 we jump left and repeat. This is forced repetition. And where is repetition there are patterns.

So I either find a useFul pattern to keep or a useLess pattern to throw out. I will start with the primitive case of 3 coins, 1 fake with unknown relative weight. Answering your previous questions I've deduced that in that case I need two tests. And to start things off I will apply rmsgrey's testing system of ones left twos right zeros on the table.

The only thing I can see in my mind's eye right away is this. Numbers with zero in the first bit will never make it on to the pans for the first weighing. Numbers with zero in the second bit will never make it on to the pans for the second test. Numbers with zero in the third bit will never make it on to the pans for the third test. And so on. In general numbers with zero in the n-th bit will never make it on to the pans for the n-th test. May be there's something here - when the relative weight of the bad coin is not known ALL the coins must make their way on to the pans at least once. Right or wrong?

For example, a coin numbered 00 has absolutely no hope of getting onto a pan because it does not have either 1 or 2 in the second bit. Wait a second. I have a hole in my reasoning. For consequent tests numbers with zero in the n-th bit will not make it on to the pans for n-th test but some of them may have been tested before.

Yes. Need pen and paper and start writing some numbers down.

-----------------------------
End of my last night thoughts.

Now let me think about what you just said.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 2^nd, 2013, 12:25pm

I see.
3^3 = 27. 27 - 3 = 24. 24 / 2 = 12.
3^2 = 9. 9 - 3 = 6. 6 / 2 = 3.

So to answer my own question for N tests it's

coins = (3^N - 3) / 2

Is that right?

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 2^nd, 2013, 1:07pm

I think I am on to something. Being stubborn with my elimination idea. Got to try it...

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 2^nd, 2013, 2:14pm

I may be off on reasoning but I think I've found what works for 9 coins first. 00 01 02 10 11 12 20 21 22.

Tried 3-coin problem numbering them 00 01 02 and ran into a wall. I could only do one test. No coins satisfied the placement criteria for second test. However, observing my previous elimination idea and your "3 lost" idea I wrote down all nine two-test numbers and the following clicked:

1. Can't number items 00 01 02 - must pick conveniently patterned ones from the nine above.

2. These must satisfy the following criteria:
- can't run out of coins to test;
- must have good variance in bit patterns;
- each coin must be weighed at least once;
- can't have conflicts - multiple coins per pan are allowed but each pan (and table) must have equal number of coins, third, third, and third.

From that - kill coins with no variance at all - 00 11 22 must go. That's -3. What happens next I think depends on the testing scheme, see below. I will eventually figure out what the pattern is but here's what worked - coins 10 02 21.

Testing scheme. Ones go left, zeros right, twos on the table. If ones pan goes down - record 1 in heavy variable AND record 0 in light variable. If zeros pan goes down - record 0 in heavy variable AND 1 in light. Balance - record two in both. Next test rearranges coins as per this rule.

At the end of the test we don't know if bad coin is heavy or light. Solution - search test coins for a heavy number. If found - that's your man. If not - the light number is guilty.

Example, let's say 21 is heavy:

ones zeros twos suspects
21 10 02 1 and 0
10 02 21 21 and 20

Number 20 was not in the mix. Hence the bad coin is heavy and it's 21.

Hunch (as I'm typing this). Coins that are left out 01 12 20 may also work but bit positioning must be changed for testing.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 2^nd, 2013, 2:39pm

Yes, it works. And no - bit assignments don't matter. Testing 01 12 20 works equally well with my original rule.

It's not how coins are tested but which ones are selected for the test.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 2^nd, 2013, 3:17pm

OK, what's so special about these patterns:

02
10
21

and

01
12
20

What I can see is this. If you look vertically then for each column or bit position one third has zeros, one third has ones and one third has twos. My guess would also be that for more coins if there would be duplicates in the same bit position then it would have to be equal amount of them.

Also, since I've found that pan bit assignment doesn't matter then the following is also true. Weight difference produces two mutually exclusive events. One pan goes down, the other necessarily up. Only one coin is bad. If it's heavy it can't be light. And if it's light it can't be heavy. Hence. If you swap the pan assigned bits around in the bad coin's number you should NOT get the number from the mix.

For example, in the rule I used ones go left and zeros right. So. We pick ones and zeros. If we swap them around - all ones to zeros and all zeros to ones in 21 it becomes 20 and it's not in the original mix. I think.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 2^nd, 2013, 7:24pm

12-coin bit-patterned solution.

1. Write 27 numbers in base 3:

000 001 002 010 011 012 020 021 022
100 101 102 110 111 112 120 121 122
200 201 202 210 211 212 220 221 222

2. Chuck:

000 111 222.

3. Select:

010 101 201
012 102 202
020 120 210
021 121 212

4. Weigh (pick you favorite configuration, here's 0 left,1 right, 2 table):

010 101 012
020 021 102
120 121 202
210 201 212

5. Record (improvement?) heavy/light suspect in one variable.

6. If suspect is found in selected numbers it's heavy/light. If not - swap all zeros into ones and all ones into zeros in suspect and declare the bad coin light/heavy (reverse quality).

Title: Re: Counterfeit coin.
Post by jollytall on Nov 2^nd, 2013, 11:44pm

on 11/01/13 at 08:03:23, rmsgrey wrote:

The 12-coins-with-fixed-weighings is still open to you.

Without any bits, a simple logic:
All measured coins must be measured differently, otherwise we cannot differentiate them.
Theoretically there could be one that we never measure. In this case we have no information on this, so it has to be excluded. It also means that we never get three times balanced pans (one lost case).
There are three (a,b,c) that appear only in one measurement.
There are three (d,e,f) that appear twice on the same side.
There are three (g,h,i) that appear twice but on different sides.
There are three (j,k,l) that appear three times, twice on one side, once on the other.
Theoretically there could be one more (m) that appears three times, on the same see. I come back to that later.

Now place them in reverse sequence (easier to place the complicated first and at the end the easy ones):
jl-k jk-l kl-j
jlg-ki jkh-lg kli-jh
jlg-kidf jkh-lgde kli-jhef

And the last step:
jlga-kidf jkhb-lgde klic-jhef

This by design gives the solution.
And now about the 13th piece. In the above solution, there is no coin that is always on the same side, so it never happens that the three measurements give the same result (always the left is lighter or heavier than the right one). These are the two more lost cases.
But it also means that if we have a 13th potentially fake coin we could use it to put it always on the same side. Unfortunately then we have 5 vs. 4 on the two sides, so it won’t work. But if we have a “neutral”, surely good 14th coin then even 13 coins are doable. Then we have only one lost case, the three times equal.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 3^rd, 2013, 12:54pm

From door to door I flow
As numbers I arrange.
When to the next I go
I would prefer the change.
These changes are not random.
They all have common beat.
If you would like to find them
O-one-two may be it.

What am I?

A bit pattern that solves the 3 and 12-coin puzzles.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 3^rd, 2013, 2:16pm

The purity of the experiment is now spoiled as I've solved the problem and seen your solutions but I would keep coins numbered. Where there are simple numbers there are simple formulas.

I've played with the 3-coin problem a bit. So coins are numbered 1, 2, 3. And we test 1 2 and 1 3. If the first coin is K (=1) then going from one test to another we replace coin 3K-1 (2) with 3K (3).

I also noticed that:

3*1 - 2 = 1
3*2 - 5 = 1
3*3 - 8 = 1

If 2, 5, 8 don't look bewildering to you they were certainly to me. But I said OK let's move onto 12 coins.

Keep testing in groups of three and say 1 is heavy then:

123 > 456

Replace 456 with 789:

123 > 789

I said now what? That's where 2, 5, 8 come in:

147 > 258.

If say 4 is light same thing works again. And if the bad coin is 7-9 it works again too. I tried it. So in two tests we can test the groups of three.

Next let's say we test just three coins. And do two tests 1 2 and 1 3. It is impossible for results to be say 1 down in one and 1 up in the other. Can't be. There's only one bad coin. It means that if we add two extra coins say 10 and 11 to two tests and swap them around between tests - they must behave consistently and we are sure to derive some useful information:

12310 45611
12311 78910

Finally need to figure out what to do with 12. Our triplet tests were so far:

123 456
123 789
147 258

So for quads I said OK what if two first tests balance:

12310 == 45611
12311 == 78910
14711 ? 25812

In that case all the coins are good and 12 is bad. I'll be honest I didn't write all the scenarios completely, I want a little bit of a weekend or whatever is left of it, but here's what I analyzed and I think there's potential here:

if 12310 == 45611
if 12311 == 78910
if 14711 == 25812
no bad coin at all
if 14711 < 25812
12 heavy
else
12 light
if 12311 > 78910
if 14711 == 25812
9 light
if 14711 < 25812
7 light
if 14711 > 25812
8 light

and so on.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 4^th, 2013, 10:42am

An AVL tree node stores among other things a balance factor that tells if the tree below is left heavy, right heavy or balanced. I now wonder if the coin puzzle solution exists that revolves around an AVL or similar (may be tertiary) tree? Just a hypothesis.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 6^th, 2013, 7:58pm

While working on the all-quad testing scheme I've uncovered an interesting connection between it and the bit-patterned solution. Both work according to this pattern: original + transformation + manipulation + reverse transformation. In the bit-patterned solution the original are the decimal (coin) numbers. The transformation is the rearrangement of these numbers from base ten to base three. The manipulation is the selection of the specific numbers based on their bit properties and the assignment of test results to the bit positions in the suspect's coin number. The reverse transformation is base three to base ten rearrangement.

In the all-quad or three plus one testing scheme the original are the coin numbers 1, 2, 3. The transformation is the rearrangement of these numbers into three groups G1, G2, G3, renaming the testing scheme into G1G2, G1G3, switching from 3-coin to 12-coin puzzle, copying all the numbers of the 3-coin puzzle into G1 and using the last coin K=3 as the anchor adding sizeof(G1) items K+1, K+2 and K+3 to G2 (456) and 3K-2, 3K-1, 3K to G3 (789). The reverse transformation is renaming the 12-coin G1, G2, G3 back into the numbers they carry:

123 456
123 789

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 6^th, 2013, 8:19pm

I've finished analyzing all the remaining scenarios for the all-quad or three plus one testing scheme. It works.

I realized that I can compress my test results a lot by using the 5-column table. First three columns record the test result as R for right, L for left and B for balance. The next column is the bad coin number and the last column is the weight quality: LLL 01 H means all three tests were left heavy, the bad coin is 1 and it's heavy.

In this form I've got BBB as all coins are good. If it's given that one bad coin must be there then this is the first possibility to discard. The other two were LRL and RLL. I said why no symmetry in these two? Turns out it was my sloppy placement of coin number 11 in the last test. If you make it 10 then the impossible results are RLL and LRR. So the following testing scheme works:

12310 45611
12311 78910
14710 25812

My original results were in different order but I sorted these by the coin number:

LLL	01	H
RRR	01	L
LLR	02	H
RRL	02	L
LLB	03	H
RRB	03	L
RBL	04	H
LBR	04	L
RBR	05	H
LBL	05	L
RBB	06	H
LBB	06	L
BRL	07	H
BLR	07	L
BRR	08	H
BLL	08	L
BRB	09	H
BLB	09	L
LRL	10	H
RLR	10	L
RLB	11	H
LRB	11	L
BBR	12	H
BBL	12	L

BBB, LRR, RLL are not possible.

As I was working through the table I was wondering that since BBB looks a lot like it's bit-patterned counterpart 000 if the other two impossibilities would be RRR and LLL. No such luck.

The table is pretty static. For the same number L and R are symmetrical. For a game or some such the sorted version of this table can be created at compile time and the answer can be obtained with a single call to bsearch().

Title: Re: Counterfeit coin.
Post by rmsgrey on Nov 7^th, 2013, 6:35am

You can change RLL and LRR into LLL and RRR by swapping the first weighing - so you can make any of the 8 triples of Ls and Rs (no Bs) an illegal outcome - and then the other illegal outcome will have additional constraints.

By switching sides for any individual weighing and changing the order of the weighings, you can convert one of the two pairs {RLL,LRR} and {LRL,RLL} into any pair of [L|R]{3} where at least two positions differ. It's not clear whether you can arrange things so that the illegal results are {BBB, LLL, LLR} and it's obvious that you can't have all three places match.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 7^th, 2013, 9:12pm

You are absolutely correct, rmsgrey. Thank you very much for your help. So

45611 12310
12311 78910
14710 25812

does the trick. The day I stumbled on to this LRB notation at first I thought it's just a convenient testing device. But then as the table came to life more and more I started wondering if there's a deeper connection with the bit-patterned solution. Hence the question if LLL and RRR could be made illegal mimicking 111 and 222.

Today I made an interesting discovery. Binary trees don't work. Tertiary do. I was able to construct 7 tertiary trees one for 3, two for 4, two for 5, one for 6 and one for 7-coin puzzles. 8-coin tree is a toughie. Before I've stopped though I looked at the 3-coin tree and said how can I make paths LL or RR illegal. The answer was staring me in the face - swap the last test - instead of 1 vs 3 do it as 3 vs 1. But I couldn't carry the connection to the all-quad testing scheme.

Thanks again, rmsgrey, much appreciate it.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 8^th, 2013, 7:44pm

Figured out the 8-coin tree. What made it for me was the 2-coin tree with a known good reference coin. So now I've got it and finished the remaining 9, 10, 11 and 12-coin trees.

The key behind the tree-based solution is to design the coin groupings in such a way that they generate the fullest tree possible.

Need a few days to digest and to draw up the sketches.

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 14^th, 2013, 3:58pm

I didn't have much luck with the binary trees but the ternary trees did work out. I've constructed the total of 18 trees and at some point Niels Bohr got involved. I've managed to keep my scribbles in order this time, the paper trail was good and the article is rather lengthy.

Anyone interested in the entire story please read it here. (http://romanyandronov.elementfx.com/pse/ryapse12coins.html)

As I've mentioned before the key to solving this coin puzzle using the ternary trees is to design the coin groupings in such a way that they generate the fullest tree possible.

My notation. Each intermediate node represents one test. Each terminal node represents one bad coin and its relative weight, H is heavy, L is light. A terminal node NP means Not Possible. Test "123 456" means coins 123 are on the left pan and coins 456 are on the right pan. T1, T2, T3 are the test numbers. G is a good coin. I followed towr's advice of renumbering the coins after each test but changed it a bit to rename each good coin as G:

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_12coins16.png

[edit]
Made the link to my site more inconspicuous.
Moved the technical drawing to this forum.
[/edit]

Title: Re: Counterfeit coin.
Post by rloginunix on Nov 14^th, 2013, 4:06pm

Observations:

1). With certainty we can determine two characteristics - bad coin number and its relative weight.

2). Number only, no weight. The maximum number of coins T that can be tested for one bad coin in H tests is the sum total of all the nodes of a ternary tree of height H - 1.

That observation comes from the fact that when you look at a 3-coin or a 12-coin tree there's "pans always balance" scenario leading to an NP node in dead center which can always be replaced with the 4th or 13th coin:

T(H) = Sum 3^k, k in [0, H - 1]

Forgetting the essence of the problem for a moment we can calculate that sum purely algebraically by applying a rearrangement approach to its terms. Say H = 4:

T(4) = 1 + 3 + 9 + 27

Factor out 3 for all the terms starting from the second one:

T(4) = 1 + 3*1 + 3*3 + 3*9
T(4) = 1 + 3(1 + 3 + 9)

Notice that the sum in parenthesis is one term short of the original:

T(4) = (1 + 3 + 9) + 27
(1 + 3 + 9) = T(4) - 3^3

Put that back:

T(4) = 1 + 3(T(4) - 3^3)

And solve for T(4):

T(4) = 1 + 3T(4) - 3*3^3
2T(4) = 3^4 - 1
T(4) = (3^4 - 1) / 2

So for any H:

T(H) = (3^H - 1) / 2

3). Number and weight. The maximum number of coins W whose weight quality can also be determined with certainty in H tests is one short of T:

W(H) = T(H) - 1
W(H) = (3^H - 1) / 2 - 1
W(H) = (3^H - 3) / 2

which confirms the previous finding.

4). If you also designate the straight lines in the ternary tree as LRB then by following such a path you will come to a bad coin. My interpretation - the LRB path is a story of how the bad coin traveled through the pans during the tests. L - it was on the left pan, R - it was on the right pan, B - it was off the pans. For example, say 10 is bad and heavy. Its path through the tests is BLR.

5). For all the trees the very last test is always the one on one test - there's only one coin on each pan. Not entirely obvious if you look at just one tree presented here but I've checked all 10 trees and it works.