Author |
Topic: Counterfeit coin. (Read 11004 times) |
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Counterfeit coin.
« on: Oct 29th, 2013, 7:37pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Counterfeit coin.
« Reply #1 on: Oct 29th, 2013, 10:42pm » |
Quote Modify
|
3^3
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Counterfeit coin.
« Reply #2 on: Oct 30th, 2013, 4:29am » |
Quote Modify
|
000-222
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #3 on: Oct 30th, 2013, 10:48am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Counterfeit coin.
« Reply #4 on: Oct 30th, 2013, 10:50am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #5 on: Oct 30th, 2013, 11:28am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #6 on: Oct 30th, 2013, 10:36pm » |
Quote Modify
|
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.
|
« Last Edit: Nov 14th, 2013, 7:51pm by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #7 on: Oct 30th, 2013, 11:08pm » |
Quote Modify
|
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. } } }
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #8 on: Oct 30th, 2013, 11:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Counterfeit coin.
« Reply #9 on: Oct 30th, 2013, 11:27pm » |
Quote Modify
|
You can simplify the solution a lot by renumbering after each measurement (use pointers ).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Counterfeit coin.
« Reply #10 on: Oct 31st, 2013, 12:35am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Counterfeit coin.
« Reply #11 on: Oct 31st, 2013, 6:37am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #12 on: Oct 31st, 2013, 2:42pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #13 on: Oct 31st, 2013, 5:21pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Counterfeit coin.
« Reply #14 on: Nov 1st, 2013, 8:03am » |
Quote Modify
|
on Oct 31st, 2013, 2:42pm, 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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #15 on: Nov 1st, 2013, 12:17pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Counterfeit coin.
« Reply #16 on: Nov 1st, 2013, 11:50pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Counterfeit coin.
« Reply #17 on: Nov 2nd, 2013, 8:29am » |
Quote Modify
|
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.
|
« Last Edit: Nov 2nd, 2013, 8:30am by rmsgrey » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #18 on: Nov 2nd, 2013, 11:56am » |
Quote Modify
|
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.
|
« Last Edit: Nov 2nd, 2013, 11:59am by rloginunix » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #19 on: Nov 2nd, 2013, 12:25pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #20 on: Nov 2nd, 2013, 1:07pm » |
Quote Modify
|
I think I am on to something. Being stubborn with my elimination idea. Got to try it...
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #21 on: Nov 2nd, 2013, 2:14pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #22 on: Nov 2nd, 2013, 2:39pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #23 on: Nov 2nd, 2013, 3:17pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Counterfeit coin.
« Reply #24 on: Nov 2nd, 2013, 7:24pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
|