Author |
Topic: Counterfeit coin. (Read 11009 times) |
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
 |
Re: Counterfeit coin.
« Reply #25 on: Nov 2nd, 2013, 11:44pm » |
 Quote  Modify
|
on Nov 1st, 2013, 8:03am, 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.
|
| « Last Edit: Nov 3rd, 2013, 10:24am by jollytall » |
 IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #26 on: Nov 3rd, 2013, 12:54pm » |
Quote Modify
|
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.
|
| « Last Edit: Nov 3rd, 2013, 2:23pm by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #27 on: Nov 3rd, 2013, 2:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #28 on: Nov 4th, 2013, 10:42am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #29 on: Nov 6th, 2013, 7:58pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #30 on: Nov 6th, 2013, 8:19pm » |
Quote Modify
|
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().
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Counterfeit coin.
« Reply #31 on: Nov 7th, 2013, 6:35am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #32 on: Nov 7th, 2013, 9:12pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #33 on: Nov 8th, 2013, 7:44pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #34 on: Nov 14th, 2013, 3:58pm » |
Quote Modify
|
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.
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:
[edit]
Made the link to my site more inconspicuous.
Moved the technical drawing to this forum.
[/edit]
|
| « Last Edit: May 21st, 2014, 9:03am by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #35 on: Nov 14th, 2013, 4:06pm » |
Quote Modify
|
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.
|
| « Last Edit: Nov 14th, 2013, 4:38pm by rloginunix » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print