Coins and balances  a different twist
Moderators: jestingrabbit, Moderators General, Prelates
Coins and balances  a different twist
I read through many many threads to try and make sure this hasn't been done  I think this is a different take than has been done previously, but someone stop us if it has.
A group of pirates make off with 9 sacks of 1000 gold coins each, with plans to divide them up the next day. That night, one of the pirates sneaks out of bed and steals a coin  then wakes up an hour later with an attack of conscience. He goes out to return the coin, but forgot which bag it came from, so sticks it in a random bag. The pirates have access to a standard 2pan balance. What is the minimum number of weighings needed to either confirm that all the bags weigh the same, or to identify the light and heavy bags, without opening any of them?
A group of pirates make off with 9 sacks of 1000 gold coins each, with plans to divide them up the next day. That night, one of the pirates sneaks out of bed and steals a coin  then wakes up an hour later with an attack of conscience. He goes out to return the coin, but forgot which bag it came from, so sticks it in a random bag. The pirates have access to a standard 2pan balance. What is the minimum number of weighings needed to either confirm that all the bags weigh the same, or to identify the light and heavy bags, without opening any of them?

 Posts: 65
 Joined: Sat Apr 07, 2012 4:26 am UTC
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Coins and balances  a different twist
selfassembled wrote:Spoiler:
I don't think that's right. The idea of a balance is that it gives you only whether the two things are equal, or which is heavier. Also, even if it gives you some sort of ratio, 1001/1000  1000/999 is only a little more than a millionth. I doubt anything pirates had could deliver that sort of precision.
Assuming the balance only tells you which bag is heavier, or if they weigh the same,
Spoiler:
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Coins and balances  a different twist
I am fairly sure this works.
Spoiler:

 Posts: 65
 Joined: Sat Apr 07, 2012 4:26 am UTC
Re: Coins and balances  a different twist
Nitrodon wrote:I am fairly sure this works.Spoiler:
That's brilliant. And that's technically 6 jestingrabbit.
Re: Coins and balances  a different twist
Solid work  I went to bed last night with no replies, and woke up this morning with multiple replies and a right answer! Solving the lower bound is easy, actually finding a set of groupings that does it was (I think) much harder. And yes, jestingrabbit's solution would have been 6, in the worstcase scenario of finding the different pair last. An interesting note about Nitrodon's solution is that
Spoiler:
Re: Coins and balances  a different twist
Gwydion wrote:And yes, jestingrabbit's solution would have been 6, in the worstcase scenario of finding the different pair last.
I don't follow.
Spoiler:
Re: Coins and balances  a different twist
rmsgrey wrote:I don't follow.Spoiler:
I see now  I misread his solution, and this is correct. Still one more than necessary, but one less than I interpreted it to be.
Re: Coins and balances  a different twist
Not sure if I understood the conditions correctly. This is assuming that during weighing, they do know which bag belong to the theive but they do not know which bag he put the coin back in.
Considering worst case scenario:
1. (4 weighings) weigh 8/9 sacks in groups of 2, not weighing the theive's bag (if all are equal, then they put it back correctly, otherwise.)
2.1  if only one group had an inequality, then the heavier bag simply has 1 more coin than the lighter bag of the same group, problem solved (5 weighings)
2.2  if two groups had inequalities, weigh the leaders from both groups. The heavier bag represents a bag with 1 extra coin, and the lightest bag of the other group represents the bag having lost 1 coin. (5 weighings)
Considering worst case scenario:
1. (4 weighings) weigh 8/9 sacks in groups of 2, not weighing the theive's bag (if all are equal, then they put it back correctly, otherwise.)
2.1  if only one group had an inequality, then the heavier bag simply has 1 more coin than the lighter bag of the same group, problem solved (5 weighings)
2.2  if two groups had inequalities, weigh the leaders from both groups. The heavier bag represents a bag with 1 extra coin, and the lightest bag of the other group represents the bag having lost 1 coin. (5 weighings)
Re: Coins and balances  a different twist
Xiv wrote:Not sure if I understood the conditions correctly.
Conditions:
There are 9 sacks. Either: all 9 have equal weight of treasure; or 7 are equal, 1 is one coin heavier, and 1 is one coin lighter.
Each weighing compares one set of bags with another (nonoverlapping) set of bags and reveals which set (if either) is heavier.
I can't comment on your suggested solution because I don't understand it.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Coins and balances  a different twist
Gwydion wrote:Solving the lower bound is easy, actually finding a set of groupings that does it was (I think) much harder.
Agreed, and that feature of Nitrodon's solution that you pointed out is not shared by my own minimal solution, which is so wildly messy that I considered not writing it up.
Spoiler:
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Coins and balances  a different twist
A naive lower bound for number of weighings would be 3. Each weighing has one of three possible outcomes  left side heavier, right side heavier, or both the same. This particular puzzle has 10 possible situations. 3^2 is less than 10 but 3^3 is more than 10.
The reason that's not quite right is that when it comes to the first weighing, there's no meaningful distinction between "left side heavier" and "right side heavier"; all that matters is "same" or "different". After that it gets a little complex for me, though, so it still seems like three weighings might, in principle, be enough to distinguish among 18 possibilities. Hmm.
The reason that's not quite right is that when it comes to the first weighing, there's no meaningful distinction between "left side heavier" and "right side heavier"; all that matters is "same" or "different". After that it gets a little complex for me, though, so it still seems like three weighings might, in principle, be enough to distinguish among 18 possibilities. Hmm.
Re: Coins and balances  a different twist
Lenoxus wrote:A naive lower bound for number of weighings would be 3. Each weighing has one of three possible outcomes  left side heavier, right side heavier, or both the same. This particular puzzle has 10 possible situations. 3^2 is less than 10 but 3^3 is more than 10.
The reason that's not quite right is that when it comes to the first weighing, there's no meaningful distinction between "left side heavier" and "right side heavier"; all that matters is "same" or "different". After that it gets a little complex for me, though, so it still seems like three weighings might, in principle, be enough to distinguish among 18 possibilities. Hmm.
I'm not sure where you get "10 possible solutions" and "18 possibilities" from, but as JR correctly pointed out:
jestingrabbit wrote:Also, there are 73 different possibilities, and each balancing has 3 possible outcomes, so we need at least 4 balances. Dunno if its possible, but it will require a more cunning strategy than can be extemporised by me.[/spoiler]
Just to clarify:
If bag 1 has the extra coin (making it heavy), one of the other 8 bags is light  giving 8 possibilities for when bag 1 is heavy.
If bag 2 has the extra coin (making it heavy), one of the other 8 bags is light  giving 8 possibilities for when bag 2 is heavy.
.......
.......
If bag 9 has the extra coin (making it heavy), one of the other 8 bags is light  giving 8 possibilites for when bag 9 is heavy.
This gives 72 possibilities + 1 more possibility that the coin was put back into the original bag, making all the bags the same weight ..... giving a total of 73 different possibilities.
Re: Coins and balances  a different twist
Lenoxus wrote:The reason that's not quite right is that when it comes to the first weighing, there's no meaningful distinction between "left side heavier" and "right side heavier"; all that matters is "same" or "different". After that it gets a little complex for me, though, so it still seems like three weighings might, in principle, be enough to distinguish among 18 possibilities. Hmm.
In terms of strategy, there's no meaningful difference between leftsideheavier and rightsideheavier, but it does still distinguish cases  supposing there were only two bags, then there would be three cases (A heavy, B light; A light, B heavy; both same weight) which could be distinguished by one weighing.
Re: Coins and balances  a different twist
Oops, I missed jestingrabbit's spoiler. And I forgot about the need to identify the lighter bag. Carry on.
Who is online
Users browsing this forum: No registered users and 10 guests