Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Counting Coins Revisited: The king strikes back

Posted on 2004-08-11
Medium Priority
374 Views
After reading the magical electronic manuscript presented in

http://www.experts-exchange.com/Miscellaneous/Puzzles_Riddles/Q_21080384.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.
0
Question by:Ideefiks
• 30
• 23
• 2
• +2

LVL 4

Expert Comment

ID: 11776532
>>'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?'

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.
0

LVL 2

Expert Comment

ID: 11783151
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.
0

LVL 2

Expert Comment

ID: 11783158
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
0

LVL 5

Author Comment

ID: 11783197
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 ...
0

LVL 5

Author Comment

ID: 11783303
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.
0

LVL 2

Expert Comment

ID: 11783551
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.
0

LVL 2

Expert Comment

ID: 11783649
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.

0

LVL 2

Expert Comment

ID: 11783827
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.
0

LVL 2

Expert Comment

ID: 11784033
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.
0

LVL 5

Author Comment

ID: 11784215
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
0

LVL 5

Author Comment

ID: 11784220
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
0

LVL 5

Author Comment

ID: 11784275
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 ...
0

LVL 2

Expert Comment

ID: 11784371
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
0

LVL 2

Expert Comment

ID: 11784399
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.

0

LVL 2

Expert Comment

ID: 11784467
Oh, ignore the "we can lower the number of bags..." at the end of my post (two above), it wasnt supposed to be there.
0

LVL 2

Expert Comment

ID: 11784605
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)
0

LVL 5

Author Comment

ID: 11785195
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
0

LVL 2

Expert Comment

ID: 11785268
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.
0

LVL 2

Expert Comment

ID: 11785415
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.

0

LVL 5

Author Comment

ID: 11785515
'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.
0

LVL 2

Expert Comment

ID: 11785666
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.
0

LVL 5

Author Comment

ID: 11785795
'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.
0

LVL 5

Author Comment

ID: 11785869
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 :-)

0

LVL 2

Expert Comment

ID: 11786097
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.

0

LVL 2

Expert Comment

ID: 11786123
That's supposed to be X[1] = 1.

You need 3^(N-1) control bags for these.
0

LVL 2

Expert Comment

ID: 11786159
My math is horrible. I apologize.

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.
0

LVL 5

Author Comment

ID: 11786186
You are getting VERY close now, unfortunately you don't have any control bags at the beginning ...
0

LVL 5

Author Comment

ID: 11786247
That is even better.

So now we have got: the answer is 40 if you have 27 control bags to start with.
0

LVL 2

Expert Comment

ID: 11786280
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.
0

LVL 5

Author Comment

ID: 11786501
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.
0

LVL 5

Author Comment

ID: 11786568
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) ...
0

LVL 2

Expert Comment

ID: 11786725
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.
0

LVL 2

Expert Comment

ID: 11787261
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.
0

LVL 5

Author Comment

ID: 11787482
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- !!!
0

LVL 5

Author Comment

ID: 11787508
To be continued ... tomorrow.
0

LVL 5

Author Comment

ID: 11791623
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.
0

LVL 2

Expert Comment

ID: 11792570
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.
0

LVL 5

Author Comment

ID: 11792670
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.
0

LVL 2

Expert Comment

ID: 11792851
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.
0

LVL 2

Expert Comment

ID: 11793260
That leaves

Y(N) = (((7 * 3^(N-1)) - 3) / 6)

where Y is number of bags, N is number of weighings.

0

LVL 5

Author Comment

ID: 11793337
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!
0

LVL 9

Expert Comment

ID: 11794292
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!
0

LVL 5

Author Comment

ID: 11794447
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.
0

LVL 9

Expert Comment

ID: 11794614
respectfully idee, do you think that lead is dense than gold?
0

LVL 2

Expert Comment

ID: 11794771
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.
0

LVL 2

Expert Comment

ID: 11794816
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.

0

LVL 5

Author Comment

ID: 11795110
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.
0

LVL 5

Author Comment

ID: 11795149
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.
0

LVL 2

Expert Comment

ID: 11795467
Dear lord.

I can do 39 now.
0

LVL 2

Expert Comment

ID: 11795486
wait, maybe not.  Hmm
0

LVL 2

Expert Comment

ID: 11795560
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
0

LVL 2

Accepted Solution

EvilAardvark earned 1000 total points
ID: 11796032

Its not as easy to explain in my words as it is to explain written out:

39 Bags, split into 3 piles of 13, A, B, and C.
Split each of these piles of 13, into a pile of 9, 3, and 1.
We now  have 9 piles:  9A 3A 1A, 9B 3B 1B, and 9C 3C 1C.

Weighing One:
All of A vs All of B:  Note the position of the scale.

Weighing Two:
Move 9B off the scale, 9A to replace 9B, and 9C to replace 9A.
If the scale was originally equal, and tips now, We know the fake is in group 9C and whether it's heavier or lighter based on how the scale moves. (9B+)
If the scale was originally tipped, and equals now, we know the fake was in group 9B, and it's weight  (9B+)
If the scale was tipped one way, and tips the other way now, we know the fake was in 9A, and its weight (9B+)

If the scale doesn't move, we go to ThreeA.

Weighing ThreeA:
Move 3B off the scale, 3A to replace 3B, and 3C to replace 3A.
Follow the same rules as above.

Weighing ThreeB (For use if you have 9B+):
3B vs 3B, 3B aside leaves 3B+

Weighing FourA:
Move 1B off the scale, 1A to replace 1B, and 1C to replace 1A.
The scale WILL move this time.  Follow same rules as above.

Weighing FourB (For use if you have 3B+):
1B vs 1B, 1B aside leaves 1B+

Thirty-nine in 4 weighings.  If you can do 40, I'm giving up.  I know for a FACT that no more than 40 are possible.

Based on my method for 39, the formula is:  ((( 3 ^ n ) - 3 ) / 2 )
0

LVL 8

Expert Comment

ID: 11801617
"3 original star wars movies" -- There were more than 3??
0

LVL 2

Expert Comment

ID: 11810907
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.
0

LVL 2

Expert Comment

ID: 11811131
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.
0

LVL 5

Author Comment

ID: 11811360
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).
0

LVL 5

Author Comment

ID: 11813213
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.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Ready to kick start your career in 2018? Add app developer skills to your resume. Januaryâ€™s Course of the Month features Android App Development training with hands-on learning.  Read on to learn why these skills are important.
A quick solution showing how to control and open a POS Cash Register Drawer using VBA with MS Access.