Coins and balances - a different twist

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Coins and balances - a different twist

Postby Gwydion » Wed Nov 28, 2012 11:50 pm UTC

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 2-pan 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?

selfassembled
Posts: 65
Joined: Sat Apr 07, 2012 4:26 am UTC

Re: Coins and balances - a different twist

Postby selfassembled » Fri Nov 30, 2012 5:08 am UTC

Spoiler:
4. Make 4 pairs; the fractional difference between 999v1000 and 1000v1001 gives us the power to determine by looking at the scale whether the heavier bag has 1001 coins or is merely being weighed against the 999 bag. Checking 8 of them in pairs of two will show at least one of the irregularities, the ninth would be clear if necessary.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Coins and balances - a different twist

Postby jestingrabbit » Fri Nov 30, 2012 5:48 am UTC

selfassembled wrote:
Spoiler:
4. Make 4 pairs; the fractional difference between 999v1000 and 1000v1001 gives us the power to determine by looking at the scale whether the heavier bag has 1001 coins or is merely being weighed against the 999 bag. Checking 8 of them in pairs of two will show at least one of the irregularities, the ninth would be clear if necessary.


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:
its easy to get to get it done in 5. Again, break it up into 4 pairs and a spare. Weigh the 4 pairs: if they're all the same, the bags are all equal; If one pair is different, weigh the last bag against a correct weight bag; and if two are unbalanced, weigh one of the unbalanced against a balanced bag.

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Coins and balances - a different twist

Postby Nitrodon » Fri Nov 30, 2012 7:55 am UTC

I am fairly sure this works.
Spoiler:
1,2,3 vs 7,8,9
1,4,7 vs 3,6,9
1,9 vs 3,7
2,8 vs 4,6

selfassembled
Posts: 65
Joined: Sat Apr 07, 2012 4:26 am UTC

Re: Coins and balances - a different twist

Postby selfassembled » Fri Nov 30, 2012 8:49 am UTC

Nitrodon wrote:I am fairly sure this works.
Spoiler:
1,2,3 vs 7,8,9
1,4,7 vs 3,6,9
1,9 vs 3,7
2,8 vs 4,6


That's brilliant. And that's technically 6 jestingrabbit.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Coins and balances - a different twist

Postby Gwydion » Fri Nov 30, 2012 1:36 pm UTC

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 worst-case scenario of finding the different pair last. An interesting note about Nitrodon's solution is that
Spoiler:
after the first 2 weighings, if they are both equal you can stop because you know all the bags must be equal. The third and fourth are simply to identify the different-weight bags when present.

rmsgrey
Posts: 3148
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Coins and balances - a different twist

Postby rmsgrey » Fri Nov 30, 2012 1:46 pm UTC

Gwydion wrote:And yes, jestingrabbit's solution would have been 6, in the worst-case scenario of finding the different pair last.


I don't follow.

Spoiler:
After 4 weighings, you have 5, 6 or 9 bags known to be the proper weight. With 6, weighing the unweighed bag against one of the proper weight tells you whether it's heavy or light, and hence whether the heavier or lighter of the unbalanced pair is the other bag of improper weight.

If you have 5 known good bags and two unbalanced pairs, say A<B and C<D then either A is light and D is heavy, or C is light and B is heavy - weighing A against E tells you whether A is light or proper weight, so which bag is light and which is heavy.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Coins and balances - a different twist

Postby Gwydion » Fri Nov 30, 2012 4:03 pm UTC

rmsgrey wrote:I don't follow.

Spoiler:
After 4 weighings, you have 5, 6 or 9 bags known to be the proper weight. With 6, weighing the unweighed bag against one of the proper weight tells you whether it's heavy or light, and hence whether the heavier or lighter of the unbalanced pair is the other bag of improper weight.

If you have 5 known good bags and two unbalanced pairs, say A<B and C<D then either A is light and D is heavy, or C is light and B is heavy - weighing A against E tells you whether A is light or proper weight, so which bag is light and which is heavy.

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.

Xiv
Posts: 2
Joined: Thu Nov 08, 2012 9:12 pm UTC

Re: Coins and balances - a different twist

Postby Xiv » Mon Dec 03, 2012 9:32 am UTC

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)

rmsgrey
Posts: 3148
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Coins and balances - a different twist

Postby rmsgrey » Mon Dec 03, 2012 12:17 pm UTC

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 (non-overlapping) 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.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Coins and balances - a different twist

Postby jestingrabbit » Mon Dec 03, 2012 1:59 pm UTC

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:
You start by comparing AB v CD and EF v GH.

If everything balances, then either one of the pairs AB, CD, EF or GH contained the high and low weight bags, or all the bags balance. weigh AC v EI. If that balances, weigh H v I. Otherwise, weigh AD v BC.

If one of the first two comparisons balance, wlog assume that EF = GH and AB > CD. There are 8 possibilities, 3 with a heavy A, 3 with a heavy, and 2 with a heavy I. Weigh A v B, then C v D.

If the first two comparisons are unbalanced, then wlog, assume AB > CD, and EF > GH. Weight AC v EG. If you get balance, weight B v D. Otherwise, AG v CE decides the issue.
I specifically tried to find two initial weighings that gave me 8 or 9 cases to separate out with the final two weighings. This choice really has maximised the messiness though.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Lenoxus
Posts: 120
Joined: Thu Jan 06, 2011 11:14 pm UTC

Re: Coins and balances - a different twist

Postby Lenoxus » Tue Dec 04, 2012 6:08 pm UTC

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.

User avatar
Moonbeam
Posts: 278
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Re: Coins and balances - a different twist

Postby Moonbeam » Tue Dec 04, 2012 6:39 pm UTC

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.

rmsgrey
Posts: 3148
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Coins and balances - a different twist

Postby rmsgrey » Wed Dec 05, 2012 11:12 am UTC

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 left-side-heavier and right-side-heavier, 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.

User avatar
Lenoxus
Posts: 120
Joined: Thu Jan 06, 2011 11:14 pm UTC

Re: Coins and balances - a different twist

Postby Lenoxus » Wed Dec 05, 2012 7:05 pm UTC

Oops, I missed jestingrabbit's spoiler. :oops: And I forgot about the need to identify the lighter bag. :oops: Carry on. :)


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests