Ideefiks
asked on
Counting Coins Revisited: The king strikes back
After reading the magical electronic manuscript presented in
https://www.experts-exchange.com/questions/21080384/Counting-Coins.html
The king of Swahili realises his riddle was too easy. Very few get beheaded and his treasure of gold is getting smaller by the day. So he increases the difficulty and presents every contestant with 25 bags of coins. Not before long however people come up with a solution ... Could You?
The king then decides not to accept any contestants for a week, during which he will decide how he can make the riddle more difficult. For several days he ponders on this and decides to limit the number of times they can use the royal scales to 4. Next he starts wondering, 'How many bags of coins shall I present them with?'
Although he rather beheads somebody then to give them gold, the king is an honest man and wants to be sure the riddle can be solved. Unfortunately he was told the original riddle and was never able to solve it himself so how could he solve it if were more difficult? For days and nights he thinks about nothing else till suddenly the solution comes to him.
The next morning the royal gards hang out the new riddle which now reads:
'Given you can only use the royal scales 4 times and you have to hand 4 bags of coins back to the king every time you use them, what would be the maximum number of bags from which the counterfeits could be isolated?'
Whoever comes out with the most coins will get the points.
https://www.experts-exchange.com/questions/21080384/Counting-Coins.html
The king of Swahili realises his riddle was too easy. Very few get beheaded and his treasure of gold is getting smaller by the day. So he increases the difficulty and presents every contestant with 25 bags of coins. Not before long however people come up with a solution ... Could You?
The king then decides not to accept any contestants for a week, during which he will decide how he can make the riddle more difficult. For several days he ponders on this and decides to limit the number of times they can use the royal scales to 4. Next he starts wondering, 'How many bags of coins shall I present them with?'
Although he rather beheads somebody then to give them gold, the king is an honest man and wants to be sure the riddle can be solved. Unfortunately he was told the original riddle and was never able to solve it himself so how could he solve it if were more difficult? For days and nights he thinks about nothing else till suddenly the solution comes to him.
The next morning the royal gards hang out the new riddle which now reads:
'Given you can only use the royal scales 4 times and you have to hand 4 bags of coins back to the king every time you use them, what would be the maximum number of bags from which the counterfeits could be isolated?'
Whoever comes out with the most coins will get the points.
The question he's asking is "Whats the most number of bags to start, that you can always find a solution in 4 weighings or less, based upon the original rules (hand 4 back each time)?"
In other words, if there exists a solution in 4 weighings for 27 bags, and not for 28, the answer is 27 bags.
At least, that's how i read it.
I like this, partially because it's based off my translation of an old CS fav, but partially because it means i get to think some more.
Now, do you want a PROOF of our answer, or just a guess, with reasoning how we got the number? I don't think i could write such a proof, but i'll try regardless.
In other words, if there exists a solution in 4 weighings for 27 bags, and not for 28, the answer is 27 bags.
At least, that's how i read it.
I like this, partially because it's based off my translation of an old CS fav, but partially because it means i get to think some more.
Now, do you want a PROOF of our answer, or just a guess, with reasoning how we got the number? I don't think i could write such a proof, but i'll try regardless.
Oh, and you should've named it "The emperor strikes back", to make it more of a play on "The empire strikes back", the best of the 3 original star wars movies. :-D
ASKER
Arawn,
What I meant is: the king thinks that by presenting 25 bags and only allowing 4 weighings the riddle wil still be too easy and he suspects that solutions exist for more then 25 bags. In other words could you find the counterfeits if I showed you 26 bags? Or more? What is the maximum number of bags I could present you with and still find a solution in only 4 weighings?
Oh, and your solution for 25 bags is not correct, in step 4A you could be left with 2 bags and no more weighings ... Chop Chop ...
What I meant is: the king thinks that by presenting 25 bags and only allowing 4 weighings the riddle wil still be too easy and he suspects that solutions exist for more then 25 bags. In other words could you find the counterfeits if I showed you 26 bags? Or more? What is the maximum number of bags I could present you with and still find a solution in only 4 weighings?
Oh, and your solution for 25 bags is not correct, in step 4A you could be left with 2 bags and no more weighings ... Chop Chop ...
ASKER
That is what I am asking EvilAardvark and that was what I was hinting at but you started with a king and in the end I couldn't decide between 'the empire strikes back' and 'return of the king' ...
I read the original thread after it was closed but I was pretty sure solutions were possible for more then 24 bags and started looking for them before I posted this question, just in case you suspect I am the king and couldn't find the solution either :-)
I will require proof ofcourse, and will reward the points to whoever comes up with the most bags and a proof.
Additional points for he who comes up with the actual maximum for he has found the relationship between the number of bags and the number of weighings (As proof for this the number of bags for 6 weighings is more then adequate since we our way out of trial and error territory by then).
Greetz and happy thinking.
I read the original thread after it was closed but I was pretty sure solutions were possible for more then 24 bags and started looking for them before I posted this question, just in case you suspect I am the king and couldn't find the solution either :-)
I will require proof ofcourse, and will reward the points to whoever comes up with the most bags and a proof.
Additional points for he who comes up with the actual maximum for he has found the relationship between the number of bags and the number of weighings (As proof for this the number of bags for 6 weighings is more then adequate since we our way out of trial and error territory by then).
Greetz and happy thinking.
I can do it in 4 for 28. I can do it in 4 for 29.
I think the answer is 29.
I'll have reasoning in a minute or two.
I think the answer is 29.
I'll have reasoning in a minute or two.
Scratch that, 29 isn't possible either. My solution only works 28/29 (97% of the time).
My solution for 28:
(Key: B = Bad, or questionable bag; G = Good bag, real coins)
1. We have: 28B.
7 vs 7 with 14 aside. We're left with 14 and no knowledge of weight no matter what.
2. We have: 14B, 10G.
9B vs 9G with 5B aside. We're left with either 9B plus we know weight (3[1]), or 5B with no knowledge of weight (3[2]).
3[1]. We have: 9B, 11G, Knowledge of weight
3B vs 3B with 3B aside. We're left with 3B and knowledge of weight. Go to 4[1]
3[2]. We have: 5B, 15G
3B vs 3G with 2B aside. We're left with either 3B and knowledge of weight (4[1]) or 2B and no knowledge of weight (4[2]).
4[1]. We have 3B, 13G, knowledge of weight.
1B vs 1B with 1B aside. We're left with 1B, the bad bag. We also know whether it weighs more or less.
4[2]. We have 2B, 14G.
1B vs 1G with 1B aside. We're left with 1B, the bad bag. If the scales tip, we also know whether it weighs more or less. If not, we still know the bad bag, but not whether it weighs more or less.
I don't think 29 is possible.
My solution for 28:
(Key: B = Bad, or questionable bag; G = Good bag, real coins)
1. We have: 28B.
7 vs 7 with 14 aside. We're left with 14 and no knowledge of weight no matter what.
2. We have: 14B, 10G.
9B vs 9G with 5B aside. We're left with either 9B plus we know weight (3[1]), or 5B with no knowledge of weight (3[2]).
3[1]. We have: 9B, 11G, Knowledge of weight
3B vs 3B with 3B aside. We're left with 3B and knowledge of weight. Go to 4[1]
3[2]. We have: 5B, 15G
3B vs 3G with 2B aside. We're left with either 3B and knowledge of weight (4[1]) or 2B and no knowledge of weight (4[2]).
4[1]. We have 3B, 13G, knowledge of weight.
1B vs 1B with 1B aside. We're left with 1B, the bad bag. We also know whether it weighs more or less.
4[2]. We have 2B, 14G.
1B vs 1G with 1B aside. We're left with 1B, the bad bag. If the scales tip, we also know whether it weighs more or less. If not, we still know the bad bag, but not whether it weighs more or less.
I don't think 29 is possible.
Here's my reasoning why nothing more is possible.
(More key: + means With knowledge of weight, - means without)
Lets start at the point with 3 weighings done. At this point, we've got 1 weighings left.
In 1 weighing, if we know the weight, we can find the single bad bag out of 3 possible. (1B vs 1B, 1B aside leaves us with the solution)
In 1 weighing, without knowledge of weight, we can only find the single bad bag out of 2. (1B vs 1G, 1B aside leaves 1B)
Now, to work from there, we need to get to either 2- or 3+ on our 3rd weighing.
With 9+, we can get to 3+ as i showed above (step 3[1]).
With 5-, we can get to either 3+ or 2-, as shown in step 3[2].
I don't think you can get to 3+ or 2- with better than 9+ or 5-.
10+ leaves us 3B vs 3B, 4B aside, and can leave 4+
6- leaves us 3B vs 3G, 3B aside, and can leave 3-, or 4B vs 4G, 2B aside, and can leave 4+.
To get to 9+ or 5-, you need 14-, and weigh 9B vs 9G. If you have 15, you need to either weigh 9B vs 9G and have 6-, or 10B vs 10G with 10+.
The first step (weighing 1/4 vs 1/4, with 1/2 aside) is required to get the pile of good bags started (you end up with 1/2B, 1/2G. I don't believe there is a better first step than 1/4 vs 1/4, 1/2 aside). Well, 1/2 of 28 is 14, and from 14 you can get to 9+/5-. I don't believe you can get to 9+/5- from anything less than 14.
(More key: + means With knowledge of weight, - means without)
Lets start at the point with 3 weighings done. At this point, we've got 1 weighings left.
In 1 weighing, if we know the weight, we can find the single bad bag out of 3 possible. (1B vs 1B, 1B aside leaves us with the solution)
In 1 weighing, without knowledge of weight, we can only find the single bad bag out of 2. (1B vs 1G, 1B aside leaves 1B)
Now, to work from there, we need to get to either 2- or 3+ on our 3rd weighing.
With 9+, we can get to 3+ as i showed above (step 3[1]).
With 5-, we can get to either 3+ or 2-, as shown in step 3[2].
I don't think you can get to 3+ or 2- with better than 9+ or 5-.
10+ leaves us 3B vs 3B, 4B aside, and can leave 4+
6- leaves us 3B vs 3G, 3B aside, and can leave 3-, or 4B vs 4G, 2B aside, and can leave 4+.
To get to 9+ or 5-, you need 14-, and weigh 9B vs 9G. If you have 15, you need to either weigh 9B vs 9G and have 6-, or 10B vs 10G with 10+.
The first step (weighing 1/4 vs 1/4, with 1/2 aside) is required to get the pile of good bags started (you end up with 1/2B, 1/2G. I don't believe there is a better first step than 1/4 vs 1/4, 1/2 aside). Well, 1/2 of 28 is 14, and from 14 you can get to 9+/5-. I don't believe you can get to 9+/5- from anything less than 14.
Also, for the relationship between max # of bags for N weighings.
(3 ^ N-1) + 1
It's a lot simpler than i thought it would be.
(3 ^ N-1) + 1
It's a lot simpler than i thought it would be.
ASKER
EvilAardVark,
Your solution for 28 is flawed since in case 4[2] you only know which is bad but not whether it is lighter or heavier. Your last post is far most interesting I think, as this kind of reasoning is what lead me to the solution.
Some remarks, you are correct with 3+ and 9+ but not on 2- and 5-, that should actually be 1- and 4- (which is why your solution for 28 was not correct).
Good luck
Your solution for 28 is flawed since in case 4[2] you only know which is bad but not whether it is lighter or heavier. Your last post is far most interesting I think, as this kind of reasoning is what lead me to the solution.
Some remarks, you are correct with 3+ and 9+ but not on 2- and 5-, that should actually be 1- and 4- (which is why your solution for 28 was not correct).
Good luck
ASKER
EvilAardVark,
Your solution for 28 is flawed since in case 4[2] you only know which is bad but not whether it is lighter or heavier. Your last post is far most interesting I think, as this kind of reasoning is what lead me to the solution.
Some remarks, you are correct with 3+ and 9+ but not on 2- and 5-, that should actually be 1- and 4- (which is why your solution for 28 was not correct).
Good luck
Your solution for 28 is flawed since in case 4[2] you only know which is bad but not whether it is lighter or heavier. Your last post is far most interesting I think, as this kind of reasoning is what lead me to the solution.
Some remarks, you are correct with 3+ and 9+ but not on 2- and 5-, that should actually be 1- and 4- (which is why your solution for 28 was not correct).
Good luck
ASKER
As for the relationship, I guess you found an easy way to get to 28 but i am afraid it is not correct.
I too however found the relationship to be simpler then expected an not that much different from yours ...
The protagonists from 'Charmed' would have no difficulty finding it ...
I too however found the relationship to be simpler then expected an not that much different from yours ...
The protagonists from 'Charmed' would have no difficulty finding it ...
Here's my explanation for that relationship.
With any number of bags with knowledge of weight, we can find the solution with Y remaining weighings from N bags, where N = 3^Y.
With any number of bags without knowledge of weight, we can find P, the number of Bags with Y remaining weighings, as the solution to P =(((3^Y) + 1) /2). (e.g. P = 3^2 + 1 / 2 = (9+1) /2 = 10/2 = 5 with 2 weighings left).
So, with Y+1 remaining weighings, we can use the method outlined in step 2 of my solution for 28, plugging in Y into each of the two above equations, to determine exactly how many we need to set on the scale.
If there are 4 remaining weighings, we plug 3 (Y+1 = 4, Y = 3) into each of those two equations (N = 3^3 = 27, and O = 3^3 + 1 /2 = 14), so
The step 2, translated into variables is as follows:
2. We have: X bad, Y good.
NB vs NG with OB aside. We're left with either NB plus we know weight (3[1]), or OB with no knowledge of weight (3[2]).
To maximize this, we use 27 for N, and 14 for O, so 41 remaining bags at this step. To get to this step, we need to weigh 1/4 vs 1/4, 1/2 aside, splitting in half. From 82 bags, we get to 41.
In other words, 82 bags is the maximum for 4 weighings.
By repeating this process for different # of weighings, i've determined that (3 ^ (N-1)) + 1 is the # of bags for N weighings.
we can lower the number of bags to N+ or X-, where N is a power of 3 (e.g. 3, 9, 27, 81) and
With any number of bags with knowledge of weight, we can find the solution with Y remaining weighings from N bags, where N = 3^Y.
With any number of bags without knowledge of weight, we can find P, the number of Bags with Y remaining weighings, as the solution to P =(((3^Y) + 1) /2). (e.g. P = 3^2 + 1 / 2 = (9+1) /2 = 10/2 = 5 with 2 weighings left).
So, with Y+1 remaining weighings, we can use the method outlined in step 2 of my solution for 28, plugging in Y into each of the two above equations, to determine exactly how many we need to set on the scale.
If there are 4 remaining weighings, we plug 3 (Y+1 = 4, Y = 3) into each of those two equations (N = 3^3 = 27, and O = 3^3 + 1 /2 = 14), so
The step 2, translated into variables is as follows:
2. We have: X bad, Y good.
NB vs NG with OB aside. We're left with either NB plus we know weight (3[1]), or OB with no knowledge of weight (3[2]).
To maximize this, we use 27 for N, and 14 for O, so 41 remaining bags at this step. To get to this step, we need to weigh 1/4 vs 1/4, 1/2 aside, splitting in half. From 82 bags, we get to 41.
In other words, 82 bags is the maximum for 4 weighings.
By repeating this process for different # of weighings, i've determined that (3 ^ (N-1)) + 1 is the # of bags for N weighings.
we can lower the number of bags to N+ or X-, where N is a power of 3 (e.g. 3, 9, 27, 81) and
Yes, i don't know whether the bag is heavier or lighter than the good ones, but i know that it, and only it, is the bad bag.
Your question states that all i need to determine is WHICH bag is the bad one. My solution does that.
My question previously asks the same thing, just WHICH bag is the proper one, its weight is unimportant.
Your question states that all i need to determine is WHICH bag is the bad one. My solution does that.
My question previously asks the same thing, just WHICH bag is the proper one, its weight is unimportant.
Oh, ignore the "we can lower the number of bags..." at the end of my post (two above), it wasnt supposed to be there.
I suppose your solution, rather than +1 at the end, is -3.
X = (3 ^ (N-1)) - 3
If you make it -3, you're able to determine whether the bag that contains the counterfeits is heavier or lighter in addition to determining that it's the bad bag. By adding 4 more, as in the case of mine, you can determine which bag is the counterfeit 100% of the time, and whether it is heavier or lighter all but 2/X times. (in my case, 2/28)
X = (3 ^ (N-1)) - 3
If you make it -3, you're able to determine whether the bag that contains the counterfeits is heavier or lighter in addition to determining that it's the bad bag. By adding 4 more, as in the case of mine, you can determine which bag is the counterfeit 100% of the time, and whether it is heavier or lighter all but 2/X times. (in my case, 2/28)
ASKER
1. Sorry, I didn't realise your original question didn't state this, I am however looking for a solution that ALWAYS gives you the bad bag AND tells you whether they are lighter or heavier.
That also explains why you use 5- and I use 4-
2. X = (3 ^ (N-1)) - 3
is not my solution as this gives X=24 for N=4 and I guess it was already clear from my original formulation of the riddle that I found a solution bigger then 24 ...
3. A couple of posts up you wrote 'In other words, 82 bags is the maximum for 4 weighings.'
That can not be true, how you got there however is very close to the final solution
That also explains why you use 5- and I use 4-
2. X = (3 ^ (N-1)) - 3
is not my solution as this gives X=24 for N=4 and I guess it was already clear from my original formulation of the riddle that I found a solution bigger then 24 ...
3. A couple of posts up you wrote 'In other words, 82 bags is the maximum for 4 weighings.'
That can not be true, how you got there however is very close to the final solution
Based on your requirements, and my solution, which i feel very strongly is the best, 25-27 bags will not be able to tell you the solution with knowledge of whether the bag is heavier or lighter 100% of the time.
- and -
I meant 82 bags is the maximum for 5 weighings.
- and -
I meant 82 bags is the maximum for 5 weighings.
I unfortunately realized that 80 bags is the solution for 5 weighings, and that my solution X = (3 ^ (N-1)) - 3 doesn't hold for all values of N.
The final answer MUST be a multiple of 4. Otherwise, one cannot split it evenly into 4 piles (1/4 vs 1/4, 1/2 spare) for the first weighing.
Neither (3 ^ N-1) - 3, nor (3 ^ (N-1)) +1 always return values that are divisible by 4. As much a pain as it is, we must make it (for your proper solution):
((3^ (N-1)) - 4) + (-1 ^ N)
For mine, there's just no -4.
I still don't believe you can do 4 weighings with knowledge with more than 24 bags.
The final answer MUST be a multiple of 4. Otherwise, one cannot split it evenly into 4 piles (1/4 vs 1/4, 1/2 spare) for the first weighing.
Neither (3 ^ N-1) - 3, nor (3 ^ (N-1)) +1 always return values that are divisible by 4. As much a pain as it is, we must make it (for your proper solution):
((3^ (N-1)) - 4) + (-1 ^ N)
For mine, there's just no -4.
I still don't believe you can do 4 weighings with knowledge with more than 24 bags.
ASKER
'I meant 82 bags is the maximum for 5 weighings.'
and 41 bags in 4 weighings.
You also say: 'With any number of bags without knowledge of weight, we can find P, the number of Bags with Y remaining weighings, as the solution to P =(((3^Y) + 1) /2). (e.g. P = 3^2 + 1 / 2 = (9+1) /2 = 10/2 = 5 with 2 weighings left)'
But any number of bags without knowledge of weight is the start situation, so this formula should be applicable to that, meaning for 4 weighings P=41, again ...
Does this mean then that the solution following your requirements is 41? Or is it 28?
Translate my requirements into your key, meaning 2- has to become 1-, and go from there.
and 41 bags in 4 weighings.
You also say: 'With any number of bags without knowledge of weight, we can find P, the number of Bags with Y remaining weighings, as the solution to P =(((3^Y) + 1) /2). (e.g. P = 3^2 + 1 / 2 = (9+1) /2 = 10/2 = 5 with 2 weighings left)'
But any number of bags without knowledge of weight is the start situation, so this formula should be applicable to that, meaning for 4 weighings P=41, again ...
Does this mean then that the solution following your requirements is 41? Or is it 28?
Translate my requirements into your key, meaning 2- has to become 1-, and go from there.
I did translate. The solution becomes 24 for 4 bags.
80 bags in 5 weighings.. I weigh 20vs20 with 40 spare.
From the remaining 40 bad bags, i can find the solution in 4 weighings, yes. But ONLY because i have 40 bags left over that i KNOW are good, as well.If i started with 40 bags, i'd need 5 weighings, because i'm given no "control" bags that i know are good.
I don't believe you're able to do 26 (which i've decided is the answer you have in mind, as it'd be foolish to use an odd number) in 4 weighings without assuming something that you haven't told me.
80 bags in 5 weighings.. I weigh 20vs20 with 40 spare.
From the remaining 40 bad bags, i can find the solution in 4 weighings, yes. But ONLY because i have 40 bags left over that i KNOW are good, as well.If i started with 40 bags, i'd need 5 weighings, because i'm given no "control" bags that i know are good.
I don't believe you're able to do 26 (which i've decided is the answer you have in mind, as it'd be foolish to use an odd number) in 4 weighings without assuming something that you haven't told me.
ASKER
'my solution X = (3 ^ (N-1)) - 3 doesn't hold for all values of N.'
That is usually a sign that something is wrong with the solution.
I guarantee you there is a simple formula that holds for all values of N, and its result for N=4 is more then 24.
I wrote the whole thing out for N=4, exploring every outcome of every step and it holds, I can find it with knowledge.
Concenterate on what is correct so far:
3+ coming from 9+
1- coming from 4-
So far we have no solution for more then 24 bags that meets my requirements. I will try to give you one that does not give away the whole solution.
That is usually a sign that something is wrong with the solution.
I guarantee you there is a simple formula that holds for all values of N, and its result for N=4 is more then 24.
I wrote the whole thing out for N=4, exploring every outcome of every step and it holds, I can find it with knowledge.
Concenterate on what is correct so far:
3+ coming from 9+
1- coming from 4-
So far we have no solution for more then 24 bags that meets my requirements. I will try to give you one that does not give away the whole solution.
ASKER
A good point EvilAardVark, the situation is different and considerably easier when you have control bags. I was hinting at this earlier when I said 'But any number of bags without knowledge of weight is the start situation'.
But how many control bags do you need?
I am hesitant to tell you what the answer that I have in mind actually is because I said I would give the points to he who comes up with the highest number of bags (unless ofcourse somebody finds my answer in which case I will gladly confirm this and give the promised bonus points), not that this is very important now as you are the only player for the moment :-)
But how many control bags do you need?
I am hesitant to tell you what the answer that I have in mind actually is because I said I would give the points to he who comes up with the highest number of bags (unless ofcourse somebody finds my answer in which case I will gladly confirm this and give the promised bonus points), not that this is very important now as you are the only player for the moment :-)
With 27 control bags, i can determine which one out of 40 bags is the proper one and whether the fake is heavier or lighter in 4 weighings.
Key: C = Control
27C vs 27B, 13B aside = 27B+, or 13B-
From 27B+, 3 weighings brings us to 1.
From 13B-, weigh 9B vs 9C, 4B aside, = 9B+ or 4B-
From 9B+, 2 weighings brings us to 1.
From 4B-, 3B vs 3C, 1B aside, = 3B+ or 1B-
From 3B+, 1 weighing brings us to 1.
From 1B-, weigh the one bag vs any good bag to determine weight.
In this case, The answer is the sum of powers of 3.
X[N] (where N is # of weighings) = 3 ^ N + X[N-1]
X[0] = 1.
1, 4, 13, 40, 121, 364 are the first 6 values of X.
It's also (X[N-1] * 3 + 1), whichever is easiest for you.
Key: C = Control
27C vs 27B, 13B aside = 27B+, or 13B-
From 27B+, 3 weighings brings us to 1.
From 13B-, weigh 9B vs 9C, 4B aside, = 9B+ or 4B-
From 9B+, 2 weighings brings us to 1.
From 4B-, 3B vs 3C, 1B aside, = 3B+ or 1B-
From 3B+, 1 weighing brings us to 1.
From 1B-, weigh the one bag vs any good bag to determine weight.
In this case, The answer is the sum of powers of 3.
X[N] (where N is # of weighings) = 3 ^ N + X[N-1]
X[0] = 1.
1, 4, 13, 40, 121, 364 are the first 6 values of X.
It's also (X[N-1] * 3 + 1), whichever is easiest for you.
That's supposed to be X[1] = 1.
You need 3^(N-1) control bags for these.
You need 3^(N-1) control bags for these.
My math is horrible. I apologize.
The formula should read:
X[N] (where N is # of weighings) = (3 ^ (N-1)) + X[N-1]
X[1] = 1.
X[N] = (((3 ^ N) - 1) / 2)
is the solution with no iteration.
The formula should read:
X[N] (where N is # of weighings) = (3 ^ (N-1)) + X[N-1]
X[1] = 1.
X[N] = (((3 ^ N) - 1) / 2)
is the solution with no iteration.
ASKER
You are getting VERY close now, unfortunately you don't have any control bags at the beginning ...
ASKER
That is even better.
So now we have got: the answer is 40 if you have 27 control bags to start with.
So now we have got: the answer is 40 if you have 27 control bags to start with.
The EXPECTED Solution for 25:
Have 25B-. 6B vs 6B, 13B spare, leaves 12B or 13B.
Have 13B-. 9B vs 9G, 4B spare, leaves 9B+, or 4B-.
Have 12B-. 9B vs 9G, 3B spare, leaves 9B+, or 3B-.
Have 9B+. 3B vs 3B, 3B spare leaves 3B+.
Have 4B-. 3B vs 3G, 1B spare leaves 3B+ or 1B-.
Have 3B-. 3B vs 3G, leaves 3B+
Have 3B+. 1B vs 1B, 1B spare leaves 1B+.
Have 1B-. 1B vs 1G leaves 1B+.
Tell me, is this the solution you use?
It's wrong.
Have 25B-. 6B vs 6B, 13B spare, leaves 12B or 13B.
Have 13B-. 9B vs 9G, 4B spare, leaves 9B+, or 4B-.
Have 12B-. 9B vs 9G, 3B spare, leaves 9B+, or 3B-.
Have 9B+. 3B vs 3B, 3B spare leaves 3B+.
Have 4B-. 3B vs 3G, 1B spare leaves 3B+ or 1B-.
Have 3B-. 3B vs 3G, leaves 3B+
Have 3B+. 1B vs 1B, 1B spare leaves 1B+.
Have 1B-. 1B vs 1G leaves 1B+.
Tell me, is this the solution you use?
It's wrong.
ASKER
It is wrong because when you have 13B-, 9b vs 9G is a no go as you have only 8G left ...
I looked into this carefully as another version of the riddle I got years ago didn't require to hand over any bags.
So no, this is not the solution I use.
Your expected solution is VERY VERY VERY close to the solution though, in fact it contains only 1 mistake, a mistake that has been there from the very beginning (I am now referring to Arawn's and your solution for your question), the mistake that lead me to believe more then 24 bags were possible in the first place.
I looked into this carefully as another version of the riddle I got years ago didn't require to hand over any bags.
So no, this is not the solution I use.
Your expected solution is VERY VERY VERY close to the solution though, in fact it contains only 1 mistake, a mistake that has been there from the very beginning (I am now referring to Arawn's and your solution for your question), the mistake that lead me to believe more then 24 bags were possible in the first place.
ASKER
You still don't believe it is possible to go for more then 24 bags.
Then you would really be amazed at how many bags the best solution gives (my original question already suggests that it is more then 25) ...
Then you would really be amazed at how many bags the best solution gives (my original question already suggests that it is more then 25) ...
If you'd care to email your crazy solution to me, webmaster at-mark ktcomx period com, i'd love to see it. I'll back out of the runnings for the points.
I STILL don't believe its possible to go past 24.
I STILL don't believe its possible to go past 24.
I tried to reply to your email, but it didnt work. Got an "undeliverable mail, username does not exist" return from your server :(
Message Text:
Ah, but you're wrong.
When you weigh 6 bad bags vs 6 other bad bags, it will tell you which side
is heavier, but you still don't know if the bad bags are heavier or lighter
than the good ones. If the left side goes up, then you know that the left
side is heavier, and that the bad bag is one of the 12 on the scale.
Please explain how you get 12B+. I don't see it possible.
Message Text:
Ah, but you're wrong.
When you weigh 6 bad bags vs 6 other bad bags, it will tell you which side
is heavier, but you still don't know if the bad bags are heavier or lighter
than the good ones. If the left side goes up, then you know that the left
side is heavier, and that the bad bag is one of the 12 on the scale.
Please explain how you get 12B+. I don't see it possible.
ASKER
Hmm, don't know what happened with the mail ... :-(
you wrote: 'If the left side goes up, then you know that the left side is heavier'
I am assuming that is a typo, because surely the left side would be lighter, or you are using some sort of antimatter balance :-)
Anyway, new key: split + into H(eavy) and L(ight), - still means the same.
6B- vs 6B- and the scales tilt gives 6BH and 6BL which is equal to 12B+ and is NOT the same as 12B- !!!
you wrote: 'If the left side goes up, then you know that the left side is heavier'
I am assuming that is a typo, because surely the left side would be lighter, or you are using some sort of antimatter balance :-)
Anyway, new key: split + into H(eavy) and L(ight), - still means the same.
6B- vs 6B- and the scales tilt gives 6BH and 6BL which is equal to 12B+ and is NOT the same as 12B- !!!
ASKER
To be continued ... tomorrow.
ASKER
I could post a solution for 25, just to prove more then 24 is possible, again my original question already hinted at the fact that the final solution is higher then 25 so this would not be the end of this thread.
I'd like to see it. Something tells me i can find a problem with it, because based on your rules, i don't think more than 24 is possible.
ASKER
Solution for 25:
Have 25B-. 7B vs 7B, 11B spare, leaves 7BH and 7BL or 11B-.
Have 7BH and 7BL. 7BH vs 7G, 7BL spare, leaves 7B+
Have 11B-. 7B vs 7G, 4B spare, leaves 7B+, or 4B-.
Have 7B+. 3B vs 3B, 1B spare leaves 3B+ or 1B+.
Have 4B-. 3B vs 3G, 1B spare leaves 3B+ or 1B-.
Have 3B+. 1B vs 1B, 1B spare leaves 1B+.
Have 1B-. 1B vs 1G leaves 1B+.
This solution even gives you a chance at finding the solution in 3 weighings.
Have 25B-. 7B vs 7B, 11B spare, leaves 7BH and 7BL or 11B-.
Have 7BH and 7BL. 7BH vs 7G, 7BL spare, leaves 7B+
Have 11B-. 7B vs 7G, 4B spare, leaves 7B+, or 4B-.
Have 7B+. 3B vs 3B, 1B spare leaves 3B+ or 1B+.
Have 4B-. 3B vs 3G, 1B spare leaves 3B+ or 1B-.
Have 3B+. 1B vs 1B, 1B spare leaves 1B+.
Have 1B-. 1B vs 1G leaves 1B+.
This solution even gives you a chance at finding the solution in 3 weighings.
Ah. I don't know why i couldn't see that.
I'm guessing then that your highest you can do in 4 is... 31?
Have 31B-. 9B vs 9B, 13B spare, leaves 9BH, 9BL, or 13B-
Have 9BH, 9BL. 9BH vs 9G, 9BL spare leaves 9B+
Have 13B-. 9B vs 9G, 4B spare, leaves 9B+ or 4B-.
Have 9B+. 3B vs 3B, 3B spare leaves 3B+.
Have 4B-. 3B vs 3G, 1B spare leaves 3B+ or 1B-
Have 3B+. 1B vs 1B, 1B spare leaves 1B+.
Have 1B-. 1B vs 1G leaves 1B+.
I don't see more.
I'm guessing then that your highest you can do in 4 is... 31?
Have 31B-. 9B vs 9B, 13B spare, leaves 9BH, 9BL, or 13B-
Have 9BH, 9BL. 9BH vs 9G, 9BL spare leaves 9B+
Have 13B-. 9B vs 9G, 4B spare, leaves 9B+ or 4B-.
Have 9B+. 3B vs 3B, 3B spare leaves 3B+.
Have 4B-. 3B vs 3G, 1B spare leaves 3B+ or 1B-
Have 3B+. 1B vs 1B, 1B spare leaves 1B+.
Have 1B-. 1B vs 1G leaves 1B+.
I don't see more.
That leaves
Y(N) = (((7 * 3^(N-1)) - 3) / 6)
where Y is number of bags, N is number of weighings.
Y(N) = (((7 * 3^(N-1)) - 3) / 6)
where Y is number of bags, N is number of weighings.
ASKER
Interesting isn't it, half an hour ago you were convinced that more then 24 was impossible, now you tweaked my 25 solution to 31, a full 7 more then 24!
So, currently we have a proven solution with 31 bags, 4 weighings, return 4 bags after each weighing and always be able to tell wether it is lighter or heavier.
I don't see more either with this approach, 31 is max, however I only posted the 25 solution because it shows but 1 improvement over your 24 solution, this is however not my final solution!
To further increase the number of bags another - less obvious - improvement needs to be added to the solution ...
And after that you can start looking for the mathematical relationship ...
More thinking is required! Good luck!
So, currently we have a proven solution with 31 bags, 4 weighings, return 4 bags after each weighing and always be able to tell wether it is lighter or heavier.
I don't see more either with this approach, 31 is max, however I only posted the 25 solution because it shows but 1 improvement over your 24 solution, this is however not my final solution!
To further increase the number of bags another - less obvious - improvement needs to be added to the solution ...
And after that you can start looking for the mathematical relationship ...
More thinking is required! Good luck!
fyi in 1400 the heaviest substance known was gold. it weights far more than lead. Even now if you don't have access to depleted uranium you'll have a hard time finding something heaver (and cheaper) than gold. Good puzzles though!
ASKER
Actually lead is 3 places further down the periodic table, it was known to the greeks and romans and in those days - as today - it was a lot cheaper then gold.
Don't feel like giving the puzzle a shot Gilbar? EvilAardvark has set the, only, mark at 31 bags.
Don't feel like giving the puzzle a shot Gilbar? EvilAardvark has set the, only, mark at 31 bags.
respectfully idee, do you think that lead is dense than gold?
Ah, but you're wrong gilbar.
In the land of swahili, EVERYONE knows that lead is more dense than gold. Considering how this is a HYPOTHETICAL situation, the rules can be played out any way the creator wishes.
In swahili, lead is significantly more dense than gold. And, just so you know, Depleted uranium can be found in every household, and it's almost as light as air.
Please think twice before posting your smartass comments in threads that didn't ask for them. This is the "Puzzles and Riddles" TA, not the "Chemistry" TA. We don't care how dense your elements are, we're trying to solve a Puzzle.
In the land of swahili, EVERYONE knows that lead is more dense than gold. Considering how this is a HYPOTHETICAL situation, the rules can be played out any way the creator wishes.
In swahili, lead is significantly more dense than gold. And, just so you know, Depleted uranium can be found in every household, and it's almost as light as air.
Please think twice before posting your smartass comments in threads that didn't ask for them. This is the "Puzzles and Riddles" TA, not the "Chemistry" TA. We don't care how dense your elements are, we're trying to solve a Puzzle.
I've looked at this puzzle too long. I don't see any better ideas. Shame we don't have more people watching, more brains = more ideas.
Maybe you'd care to give a hint?
I do now believe you that you can beat 31, if you say you can.
Maybe you'd care to give a hint?
I do now believe you that you can beat 31, if you say you can.
ASKER
Weighings 3 and 4 can not be improved, they are identical to my solution.
Weighings 1 and 2 however offer room for improvement, what drives these 2 weighings in the 31 solution and why exactly is 31 the limit with this approach?
Then ask yourself whether this 'driver' can not be replaced by something more efficient.
Very vague indeed but I don't really see how to give a hint without actually telling you the answer.
Gilbar: I said that lead was further down the periodic table hence a single atom of lead is heavier then a single atom of gold. Which is not the same as its density which is a macroscopic property.
Weighings 1 and 2 however offer room for improvement, what drives these 2 weighings in the 31 solution and why exactly is 31 the limit with this approach?
Then ask yourself whether this 'driver' can not be replaced by something more efficient.
Very vague indeed but I don't really see how to give a hint without actually telling you the answer.
Gilbar: I said that lead was further down the periodic table hence a single atom of lead is heavier then a single atom of gold. Which is not the same as its density which is a macroscopic property.
ASKER
EvilAardVark,
Have to go now ...
Don't loose your sleep over this riddle, if nobody else wants to give it a go and you abandon I will give you my solution on monday.
Greetz.
Have to go now ...
Don't loose your sleep over this riddle, if nobody else wants to give it a go and you abandon I will give you my solution on monday.
Greetz.
Dear lord.
I can do 39 now.
I can do 39 now.
wait, maybe not. Hmm
According to a fairly simple 1 to 1 diagram.... With 3 possible outcomes to each weighing, and 4 total weighings, there are 81 possible outcomes.
To map 81 outcomes to solutions, each bag could possibly be lighter or heavier, so for each bag there are 2 solutions.
This leads me to believe the total # of bags MATHEMATICALLY possible is 40.
I'll work to see if i can't devise a solution on 39, to start. I think it's possible, but i don't see it, yet
To map 81 outcomes to solutions, each bag could possibly be lighter or heavier, so for each bag there are 2 solutions.
This leads me to believe the total # of bags MATHEMATICALLY possible is 40.
I'll work to see if i can't devise a solution on 39, to start. I think it's possible, but i don't see it, yet
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
"3 original star wars movies" -- There were more than 3??
There were only 3 ORIGINAL star wars movies (#'s 4, 5 and 6). Then lucas produced the 3 prequels (#'s 1, 2 and 3, 3 is currently in production) 20 years later.
For bags to give up after each weighing with my strategy, read below:
One: Give away 4 from 9B if the scale doesn't tip, or 3C + 1C if it does.
Two: Give away any of the good bags if the scale moves from its last position.
If it doesn't, give 4 away from 9B, and use 4 of 9B's bags to replace 3C and 1C if you used them in One.
ThreeA: Give away any of the good bags if the scale moves from its last position.
If it doesn't, give the last 9B bag and all of 3B.
ThreeB: Give away any of the good bags.
FourA: Give away any of the good bags, as you know the solution.
FourB: Give away any of the good bags, as you know the solution.
One: Give away 4 from 9B if the scale doesn't tip, or 3C + 1C if it does.
Two: Give away any of the good bags if the scale moves from its last position.
If it doesn't, give 4 away from 9B, and use 4 of 9B's bags to replace 3C and 1C if you used them in One.
ThreeA: Give away any of the good bags if the scale moves from its last position.
If it doesn't, give the last 9B bag and all of 3B.
ThreeB: Give away any of the good bags.
FourA: Give away any of the good bags, as you know the solution.
FourB: Give away any of the good bags, as you know the solution.
ASKER
Congratulations!
That is my solution, 39 bags, the formula is correct as well, no I can not do 40 :-)
An astonishing 15 bags more then the original riddle !
I had a different approach for weighing 2, not using any of the good balls if the scale tips, but the result is the same.
You only really need control balls if the scale does not tip, in which case you have 26 to choose from (or 22 after you have given 4 back).
That is my solution, 39 bags, the formula is correct as well, no I can not do 40 :-)
An astonishing 15 bags more then the original riddle !
I had a different approach for weighing 2, not using any of the good balls if the scale tips, but the result is the same.
You only really need control balls if the scale does not tip, in which case you have 26 to choose from (or 22 after you have given 4 back).
ASKER
At one point you thought that 39 was possible but hadn't found the solution yet, did you also decide that if 3B+ can come from 9B+, 9B+ could come from 27B+ ?
You already had the formula a while back, solution with 27 control balls:
X[N] (where N is # of weighings) = (3 ^ (N-1)) + X[N-1]
X[1] = 1.
Except the second line should have read X[1] = 0 since you don't have a control ball, and you really don't need the control balls at the beginning.
You already had the formula a while back, solution with 27 control balls:
X[N] (where N is # of weighings) = (3 ^ (N-1)) + X[N-1]
X[1] = 1.
Except the second line should have read X[1] = 0 since you don't have a control ball, and you really don't need the control balls at the beginning.
Do you mean the MINIMUM amout of bags from which the counterfeits could be isolated? Because the maximum number of bags is 25. I could just walk in there, tell the king that the counterfeits are somewhere in the 25 bags over in the corner, and then leave.
If you want the minimum, I have it down to 2 bags in some cases, and no bags in other cases. I used a variation on my answer from the previous riddle.
1. 6 vs 6 with 13 to the side. This will give you either an equal result, in which case the ones to the side are the bad ones (go to 2A) or it will give you an unequal result in which case on of the two lots on the scale is bad and the one to the side is good (go to 2B).
2A. Take the 8 of the bad ones and measure against 8 of the remaining good ones. If this is equal that means the last 5 bags are counterfeit. - go to 3A. If this is inequal, you now know whether the counterfeits are lighter or heavier and you know they are in the 8 bad bags on the scale. (Go to 3B).
3A. Take 4 good bags and 4 bad bags. If they are equal, the last bag is counterfeit. If they are not equal, you now know if the counterfeit bag is lighter or heavier than the rest. (Go to 4A).
3B. Put 3 bad bags on each side of the scale and 2 bad bags aside. If the bags on the scale are equal, you know the last two are counterfeit. Go to 4B. If they are unequal, go to 4C.
4A. From the last 4 bags, put one on each side of the scale and two to the side. You know if the counterfeit is lighter or heavier, so if the scale is inequal, you know your counterfeit bag. If the scale is equal, the counterfeit is is one of the two remaining bags.
4B. From your two remaining bad bags, put one bad bag on the scale and measure against a good bag. From this weighing you will know which of the two bags is counterfeit.
4C. Take the three bad bags and put one on each side of the scale and one to the side. You know if the counterfeit is lighter or heavier, so you know which bag on the scale is counterfeit if the scale is inequal, otherwise the one to the side is the counterfeit.