EvilAardvark
asked on
Counting Coins
It's the year 1400, and the king of Swahili comes to you. He has 24 coin-makers, all of whom make identical gold coins. Recently, some of hispeople have been complaining that the coins are counterfeit. (I'm sure you all recognize this riddle by now, but it's not the same one you're used to) The only way you can tell the difference between a counterfeit coin and a real coin is its weight (the gold-like metal does not weigh the same as gold). You don't know whether the fake coins are heavier or lighter, but you can rest assured that all the fakes are made with the same material, so they're all either heavier or lighter (you won't have one fake that's heavier and one that's lighter). The king hands you 24 bags, each filled with coins from each of the coin-makers (one bag per coin-maker). He allows you to use the royal scales, as well. These scales are really just a simple balance. They will tell you which side is heavier, when you place objects on either side. They are precise within .1% and you have been told that this is more than enough to determine the difference between the weights of the coins.
The king offers you all 24 bags of gold if you can complete this task. After thinking for a bit, he realizes that almost anyone could complete the task without a catch. He turns around and says "But each time you use that scale, you have to give me 4 bags back. And yes, that means you can't use them on the scale after I take them. If you can't complete the task, i'll have you beheaded!"
Two royal guards (One at the left of the scale, and one at the right) step forward and say "Please hand us each the bags you want weighed."
Is there a way you can be guaranteed to live through this trial? And if so, how many bags of coins do you get to walk away with?
Whoever comes out alive with the most coins will get the points.
The king offers you all 24 bags of gold if you can complete this task. After thinking for a bit, he realizes that almost anyone could complete the task without a catch. He turns around and says "But each time you use that scale, you have to give me 4 bags back. And yes, that means you can't use them on the scale after I take them. If you can't complete the task, i'll have you beheaded!"
Two royal guards (One at the left of the scale, and one at the right) step forward and say "Please hand us each the bags you want weighed."
Is there a way you can be guaranteed to live through this trial? And if so, how many bags of coins do you get to walk away with?
Whoever comes out alive with the most coins will get the points.
ASKER
Another thing. The scales will answer ONLY one question: "Which side is heavier?" They will do no more. They will not tell you how much heavier one side is than the other. The heavy side swings down, the light side swings up. There's no way to accurately gauge the difference in weight, only the fact that there is a difference.
ASKER
Oh, and i'm not completely certain that my answer is the best one. If you find an answer that i believe is better than my own, i'll double the points to 500.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Are there the same number of coins in each bag?
Is there only one devious coin-maker?
Paul
Is there only one devious coin-maker?
Paul
ASKER
yes, and yes.
Though i'd like to see a solution if you don't know how many counterfeiters there are, the only thing you're told is that less than half of them make fakes (otherwise since you don't know the weight difference you can't tell which are fake and which are real), and all their fakes are made with the same metal.
Though i'd like to see a solution if you don't know how many counterfeiters there are, the only thing you're told is that less than half of them make fakes (otherwise since you don't know the weight difference you can't tell which are fake and which are real), and all their fakes are made with the same metal.
Step 1. Bribe the guards with 8 bags of gold each.
Step 2. Take the last 8 bags of gold and run like hell.
Step 2. Take the last 8 bags of gold and run like hell.
ASKER
Step 3. Guards determine that you gave them counterfeits and chase you down. Game over.
why would fake gold coins weigh more ? They ought to weigh less ... or else I am willing to accept the counterfiets ;o)
ASKER
Perhaps they're made with lead. Lead is more dense than gold, if i'm not mistaken.
Am I allowed to choose which 4 bags to give to the king on each weigh?
Are there names on the bags? If not, can I put names on them?
Can I remove coins from the bags?
I'd suspect that the subleties here will involve ensuring that the bag that is found to be full of fake coins happens to be in the kings hands when the accusation is made.
Paul
Are there names on the bags? If not, can I put names on them?
Can I remove coins from the bags?
I'd suspect that the subleties here will involve ensuring that the bag that is found to be full of fake coins happens to be in the kings hands when the accusation is made.
Paul
all their fakes are made with the same metal.
Leave 1 bag back in case any guard gets a counterfeit bag. Run like hell with 7 bags.
ASKER
Yes paul, you get to choose the 4 bags the king takes.
The bags are each labelled with the insignia of the coin-maker, all are unique.
No you may not remove coins from the bags, they're sealed.
The bags are each labelled with the insignia of the coin-maker, all are unique.
No you may not remove coins from the bags, they're sealed.
ASKER
So far the best answer is 5 weighings, and you keep 4 bags of coins and your head, as commented by sunnycoder.
Can anyone beat it?
Can anyone beat it?
ASKER
The guards want 10 bags of real coins each, Arawn.
That means you leave 21 bags (in case any are fake), and run with 3.
You've got 3 bags and your head, but the king is after you. Still not as good as sunnycoder's.
That means you leave 21 bags (in case any are fake), and run with 3.
You've got 3 bags and your head, but the king is after you. Still not as good as sunnycoder's.
1. 8 vs 8 --> If this is equal, then you know the bad 8 are on the side, meaning that you know you have 16 good bags (subtract 4 to the king go to 2A) . If this is unequal, then you know you have 8 good ones on the side (subtract 4 to the king go to 2B).
2A. 4 good versus 4 bad. If this is equal, then you know the last 4 bags have the counterfeits. Otherwise the present 4 are counterfeits and you can tell if they are lighter or heavier. Go to 3.
2B. Continually weigh your 4 good bags against 4 suspect bags until you find a bad result. You will be able to know if the counterfeits are lighter or heavier. Go to 3.
3. You now have 4 suspect bags and you know if the counterfeits are lighter or heavier. Put three good vs 3 bad on scale and weigh. If this is equal, the remaing bad one is the counterfeit. If this is unequal, do one last weighing of 1-1 with 1 on the side to find counterfeit.
2A. 4 good versus 4 bad. If this is equal, then you know the last 4 bags have the counterfeits. Otherwise the present 4 are counterfeits and you can tell if they are lighter or heavier. Go to 3.
2B. Continually weigh your 4 good bags against 4 suspect bags until you find a bad result. You will be able to know if the counterfeits are lighter or heavier. Go to 3.
3. You now have 4 suspect bags and you know if the counterfeits are lighter or heavier. Put three good vs 3 bad on scale and weigh. If this is equal, the remaing bad one is the counterfeit. If this is unequal, do one last weighing of 1-1 with 1 on the side to find counterfeit.
ASKER
Arawn, unfortunately if your situation goes to 2B, in the worst case scenario, you're left with only 4 bags and need (again, worst case) 2 weighings to determine which bag is counterfeit. This equals 7 weighings, and you're not guaranteed to find the faulty bag.
In a good case though you are done in 3.
1. Hand 12 bags to each guard. Take a reading.
2. Hand 4 from the lighter 12 to the king and keep the remaining 8 in pile 1.
3. Remove 6 from the heavier set and give them to the other guard. Take a reading.
4. Hand 4 from the lighter 6 to the king and keep the remaining 2 in pile 2.
5. Split the remaining 6 into a four and a two and add the pile of 2 to the two, marking them in some way. Hand the two fours to the guards. Take a reading.
6. If the four with the two marked is heavier, one of the two unmarked ones is at fault! Use the 'a' route.
7a. Give each of the unmarked from the heavier 4 to the guards. Give four from pile 1 to the king.
8a. Accuse the owner of the heavier bag.
I end up with 6 in pile 1, 2 in pile 2, making 8.
7b. To maximise my possible earnings, take one from the heavier 4 and 3 from the lighter 4 and give them to the king.
8b. Split the remaining 4 into twos and weigh. If the weight is the same, the one I gave to the king is the bad one.
Gotta go! I'll be back with the rest of the solution soon.
Paul
2. Hand 4 from the lighter 12 to the king and keep the remaining 8 in pile 1.
3. Remove 6 from the heavier set and give them to the other guard. Take a reading.
4. Hand 4 from the lighter 6 to the king and keep the remaining 2 in pile 2.
5. Split the remaining 6 into a four and a two and add the pile of 2 to the two, marking them in some way. Hand the two fours to the guards. Take a reading.
6. If the four with the two marked is heavier, one of the two unmarked ones is at fault! Use the 'a' route.
7a. Give each of the unmarked from the heavier 4 to the guards. Give four from pile 1 to the king.
8a. Accuse the owner of the heavier bag.
I end up with 6 in pile 1, 2 in pile 2, making 8.
7b. To maximise my possible earnings, take one from the heavier 4 and 3 from the lighter 4 and give them to the king.
8b. Split the remaining 4 into twos and weigh. If the weight is the same, the one I gave to the king is the bad one.
Gotta go! I'll be back with the rest of the solution soon.
Paul
ASKER
Unfortunately paul, lets say that one of the 4 bags you gave the king after the first weighing was counterfiet. What happens then?
You don't know whether the counterfiet coins are heavier or lighter.
You don't know whether the counterfiet coins are heavier or lighter.
ASKER
Arawn, in a good case you're done without weighing at all. You pick a bag and give it to the king, and it's the right one.
We need a GUARANTEE, so we're assuming worst-case scenario every time.
We need a GUARANTEE, so we're assuming worst-case scenario every time.
Ok,
I'll try for a 'best' scenario:
Pick 2+2 for the guards to weigh. Best case will show them different. Pay the king from the main pile.
Number the four a,b,c,d. Weigh a against b. Best case is they are the same (both a and b are good). Pay the king from the main pile.
Weigh a against c. Best case if different, give c and 3 from pile to king and tell king that the maker of c is culprit.
Result: King has 11 good, 1 bad. I have 12.
Paul
I'll try for a 'best' scenario:
Pick 2+2 for the guards to weigh. Best case will show them different. Pay the king from the main pile.
Number the four a,b,c,d. Weigh a against b. Best case is they are the same (both a and b are good). Pay the king from the main pile.
Weigh a against c. Best case if different, give c and 3 from pile to king and tell king that the maker of c is culprit.
Result: King has 11 good, 1 bad. I have 12.
Paul
EA,
... Continue step 1 until below a 'certain' limit.
To guarantee survival, I'd have to change this algorithm once I have less than a certain number of bags. I'll get back to you on that level and the new algorithm.
Paul
... Continue step 1 until below a 'certain' limit.
To guarantee survival, I'd have to change this algorithm once I have less than a certain number of bags. I'll get back to you on that level and the new algorithm.
Paul
weigh any 8 vs any 8 - leaves 8 suspect
weigh 4 good vs 4 suspect - leaves 4 suspect
weigh 2 good vs. 2 suspect - leaves 2 suspect
weigh 1 good vs. 1 suspect - counterfeit found!!!
8 bags of Gold and my head for me !!!!!!!!!
weigh 4 good vs 4 suspect - leaves 4 suspect
weigh 2 good vs. 2 suspect - leaves 2 suspect
weigh 1 good vs. 1 suspect - counterfeit found!!!
8 bags of Gold and my head for me !!!!!!!!!
>weigh any 8 vs any 8 - leaves 8 suspect
If they do not weigh equal, you have 16 suspects
If they do not weigh equal, you have 16 suspects
oops.........
How did I overlook that :)
How did I overlook that :)
EA,
Do we have to 'pay' for the last weighing that determines the culprit? I would have thought not.
Paul
Do we have to 'pay' for the last weighing that determines the culprit? I would have thought not.
Paul
ASKER
You do. In other words, if you have 4 bags, and you can in one weighing determine the bad bag, you get to walk away, but he takes all the bags. You save your head, but make no money.
I just threw it in as a twist for fun...
Step 1. Weigh Bags
Step 2. ???
Step 3. Profit!
I just threw it in as a twist for fun...
Step 1. Weigh Bags
Step 2. ???
Step 3. Profit!
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
So what about my idea that 'could' net me 12 bags?
Paul
Paul
ASKER
It COULD net you 12, but it won't always.
I want a plan that will ALWAYS net you a certain amount, and will GUARANTEE that you live. That's why we're assuming worst-case scenario.
Your's doesn't do that.
I want a plan that will ALWAYS net you a certain amount, and will GUARANTEE that you live. That's why we're assuming worst-case scenario.
Your's doesn't do that.
ASKER
Arawn, that's the solution i had in mind. I'd still like to leave the question open a little longer to see if anyone can beat it. I'll give em 24 hours before i close and award points to you.
I still like my bribe and run option though. ;-)
ASKER
Swahilian guards are not known for their corruption. Bribing them is an expensive process.
Clearly, one of the guards always lies, and the other always tells the truth. Pick either one of the guards and ask him, "If the other guard knew how many of the guards' wives cheated on them, and had to cross a river using a boat that would only carry him and one flashlight, how many socks would he need to pull out of the drawer in order to figure out which lightswitch controls the color of his hat?"
>Arawn: I still like my bribe and run option though. ;-)<
Yes, but be sure that each guard has more bags than you -- say, 9 to each guard, and 6 for you. You'll be able to run faster! The guards shouldn't leave the gold behind, for fear that other palace personnel will nab it. Even if the guard who got the counterfeit bag throws it away, he's still more heavily burdened than you.
Wait a sec -- how come this poor schmuck has to go through all these life-or-death, over-priced scale shenanigans to determine which bag is the counterfiet, but the guards are apparently able to tell the fake stuff at a glance?
Yes, but be sure that each guard has more bags than you -- say, 9 to each guard, and 6 for you. You'll be able to run faster! The guards shouldn't leave the gold behind, for fear that other palace personnel will nab it. Even if the guard who got the counterfeit bag throws it away, he's still more heavily burdened than you.
Wait a sec -- how come this poor schmuck has to go through all these life-or-death, over-priced scale shenanigans to determine which bag is the counterfiet, but the guards are apparently able to tell the fake stuff at a glance?
ASKER
Well they'd have to use the scales, but the qualification process for becoming a swahilian guard requires one to be able to outrun 95% of other swahilians, even while heavily burdened.
You, being a computer science person, do NOT fall into the top 5% of running speed swahilians.
Besides, Arawn's come up with a method to guarantee himself 8 bags, and 12 if he gets lucky (1/12 chance).
You, being a computer science person, do NOT fall into the top 5% of running speed swahilians.
Besides, Arawn's come up with a method to guarantee himself 8 bags, and 12 if he gets lucky (1/12 chance).
... while the guards are arguing about whether it is better to switch doors, you take take 1/2 + 2 of the remaining diamonds (or bananas or coconuts), and give them to one half of your brothers, who are each one half as old as they will be when you finish firing arrows every 30 seconds. You then switch camels and head off to St. Ives, stopping only on Friday to check into a hotel that costs $30 (and by $30 I mean $25) before leaving 3 days later on Friday, at which point you make three left turns, see two masked men waiting for you, observe a shoe and a car parked in front of the hotel, decide you are bankrupt, and hang yourself in a room with no doors, no windows, and nothing to stand on but a puddle of water, in which are two bodies and a baseball.
But before you drop, you are saved by a man who hadn't seen the sawdust and therefore couldn't reach the top button in the elevator unless it was raining, so he was forced to subsist on albatross stew and announce whether he would be boiled in oil or beheaded, which is only plausible when you consider that anyone who has seen a mermaid has a hangover. You therefore move in with the Swede who lives in the blue house and owns a zebra and smokes Menthols at the rate of once per minute, twice per moment, but never in a thousand years. He spends his time counting the letter f and finding unusual paragraphs that do not contain the letter e. Having replaced his new door with one word, counted the number of grooves on each side of a 33 1/3 LP with 3 songs per side, and measured the amount of dirt in a hole, you apply for a job at Infosys.
Sounds like some sort of Fizzbin role-playing game! It would play out completely different after dark, though.
Step 1. Weigh Bags
Step 2. ???
Step 3. Profit!
___________________
We're talking about Gold Bags here, not Underpants!!! Must...have...more...caffe
Step 2. ???
Step 3. Profit!
___________________
We're talking about Gold Bags here, not Underpants!!! Must...have...more...caffe
Galisteo, today is a wednesday, we would have to play upside-down.
Only if you're in a boomerang vortex zone.
but not if you have the green hat with the feather.
Unless you have already sung the first three verses of the penalty song.
darn, i only sang 2. whats the third line again?
I don't know, but it's surely something in praise of tigers.
Here's a method i thought of.
1) Weigh 8 vs 8.
You will know which 8 bags have counterfeit coins.
Of these 8 coins,
2) Weigh 3 vs 3
Now you know of which group of coin(either 3 or 2) has counterfeit coins.
3) Weigh 1 vs 1
If you have 2 coins, you can get the result stright comparing 2 coins. Even if u got 3 coins in step 2, Just compare the 2 coins, and you can rule out which are the true coins and find your counterfeit coins!
1) Weigh 8 vs 8.
You will know which 8 bags have counterfeit coins.
Of these 8 coins,
2) Weigh 3 vs 3
Now you know of which group of coin(either 3 or 2) has counterfeit coins.
3) Weigh 1 vs 1
If you have 2 coins, you can get the result stright comparing 2 coins. Even if u got 3 coins in step 2, Just compare the 2 coins, and you can rule out which are the true coins and find your counterfeit coins!
problem, zz
you weigh 8 vs. 8, you know which one is heavier, you dont know if the fakes are heavier or lighter.
you weigh 8 vs. 8, you know which one is heavier, you dont know if the fakes are heavier or lighter.
ASKER