Weighing Marbles
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 20
 Joined: Thu Jul 20, 2006 9:55 pm UTC
Weighing Marbles
Here's a fun one I just heard. It took me about 6 hours to solve, and I eventually got the answer by proving that it was unsolvable, then figuring out why the proof was wrong and going from there. So if somebody solves this in half an hour, I'd appreciate it if you waited a couple hours to post the solution, if only to spare my ego.
There are 12 marbles. All of the marbles weigh the same except for one. Using only a balancing scale, figure out which marble has a different weight and whether it is heavier or lighter using only 3 weighings. You may weigh as many marbles at a time as you wish. The scale does not indicate specific weight difference, only heavier or lighter, so there is no point to placing different numbers of marbles on opposite sides of the scale.
There are 12 marbles. All of the marbles weigh the same except for one. Using only a balancing scale, figure out which marble has a different weight and whether it is heavier or lighter using only 3 weighings. You may weigh as many marbles at a time as you wish. The scale does not indicate specific weight difference, only heavier or lighter, so there is no point to placing different numbers of marbles on opposite sides of the scale.

 Posts: 20
 Joined: Thu Jul 20, 2006 9:55 pm UTC
I'm pretty sure I have a solution. I'm writing a Perl script to test it against all possible initial states.
EDIT: Yep, it works. That was easier than I'd expected, I got the basic idea within a few seconds.
EDIT again: Wait, crap, that doesn't work. Tracing showed I was using the balance one extra time in some instances. Hm.
EDIT: Yep, it works. That was easier than I'd expected, I got the basic idea within a few seconds.
EDIT again: Wait, crap, that doesn't work. Tracing showed I was using the balance one extra time in some instances. Hm.
I burn the cheese. It does not burn me.

 Posts: 37
 Joined: Thu Jul 13, 2006 9:38 am UTC
 Location: Florida
It doesn't look like there is a single clean algorithm... you just have to work out all the possible cases and figure out how to proceed from each decision point. Maybe a table of the results would reveal some useful pattern, but I'm not going to bother right now.
I have figured out that I wasn't splitting the original set of 12 into the right groups, though.
I have figured out that I wasn't splitting the original set of 12 into the right groups, though.
I burn the cheese. It does not burn me.
I may be overlooking something, or have seen this before though I can't remember having done so but I have a solution which only took me a couple of minutes, which is surprising as I don't have any particular aptitude for logic puzzles. If I'm right, my advice to anyone struggling is to first work out which obvious methods will NOT work and why, then look for a different method with the knowledge that it's really not very complicated. Your super mathematical brains may be assuming additional complexity, thereby making the whole thing harder thanit needs to be
axolotl wrote:I may be overlooking something, or have seen this before though I can't remember having done so but I have a solution which only took me a couple of minutes, which is surprising as I don't have any particular aptitude for logic puzzles.
Hmm. By all means share, because I ended up looking up some literature on this problem which seems to agree there's no simple answer. I'd love a shortcut.
I believe I've solved the puzzle. It took me a couple hours and several tries, but through the magical power of cheap whiteboards I think I've got it. Good puzzle, though; certainly much harder than the 9item variant!
Both in working through the puzzle and in writing it out, I used the notion of coins, one of which is fake; this helps if only because you can say "the fake coin" rather than "the marble that's heavier or lighter than the other marbles." My solution also assumes that all objects are distinguishable (which you can always achieve either by labelling them, or being Very Very Careful). If I've made a mistake (which is rather likely, knowing me), I welcome any criticism.
My writeup is posted online at http://mannymax.noip.com/misc/12_coins_3_weighings.txt.
The key idea for me in solving Case 1 was the group renaming; this allows the easy carrying of a bit of additional information that makes the solution that much neater. Case 2 I found a mistake in just as I was posting it here; with 1/12 probability (1/4 once Case 2 is known to occur), my solution would identify the bad coin, but not its weight. I think I have fixed this, but this remains the part of the solution which is most likely to contain a mistake (especially as I've just written it out, and it's rather clumsily written; oh well....). The fix was to use the idea from Case 1 of 'interchanging' coins from previous weighings, which seems to me not unlike the way in which systems of linear equations are solved.
Both in working through the puzzle and in writing it out, I used the notion of coins, one of which is fake; this helps if only because you can say "the fake coin" rather than "the marble that's heavier or lighter than the other marbles." My solution also assumes that all objects are distinguishable (which you can always achieve either by labelling them, or being Very Very Careful). If I've made a mistake (which is rather likely, knowing me), I welcome any criticism.
My writeup is posted online at http://mannymax.noip.com/misc/12_coins_3_weighings.txt.
The key idea for me in solving Case 1 was the group renaming; this allows the easy carrying of a bit of additional information that makes the solution that much neater. Case 2 I found a mistake in just as I was posting it here; with 1/12 probability (1/4 once Case 2 is known to occur), my solution would identify the bad coin, but not its weight. I think I have fixed this, but this remains the part of the solution which is most likely to contain a mistake (especially as I've just written it out, and it's rather clumsily written; oh well....). The fix was to use the idea from Case 1 of 'interchanging' coins from previous weighings, which seems to me not unlike the way in which systems of linear equations are solved.

 Posts: 20
 Joined: Thu Jul 20, 2006 9:55 pm UTC
I'm almost positive that there is a set  probably many sets  of three weighings that you can do, then sit down afterwards with the result and figure out which marble is odd, and whether it is heavier or lighter.
My logic is that for three sets of weighings, there are 27 out comes  each weighing can give left lighter, balanced, or right lighter. We only have 24 possibilities, however  marbles 112 being lighter or heavier. I haven't quite found a series of weighings that works yet, though.
My logic is that for three sets of weighings, there are 27 out comes  each weighing can give left lighter, balanced, or right lighter. We only have 24 possibilities, however  marbles 112 being lighter or heavier. I haven't quite found a series of weighings that works yet, though.
 RealGrouchy
 Nobody Misses Me As Much As Meaux.
 Posts: 6703
 Joined: Thu May 18, 2006 7:17 am UTC
 Location: Ottawa, Ontario, Canada
 Contact:
area  there's a fair amount of data retention between weighings (as I discovered reading MannyMax's writeup).
MannyMax  great writeup, I think it just needs to be extended slightly: The secondorder cases in Case 1 (i.e. Case 1a, 1b, 1c) require us to look at the firstorder descripton of Case 1 to determine whether the fake is ligher or heavier than the nonfakes (as required by the question). Once I figured that out, it made perfect sense to me!
 RG>
MannyMax  great writeup, I think it just needs to be extended slightly: The secondorder cases in Case 1 (i.e. Case 1a, 1b, 1c) require us to look at the firstorder descripton of Case 1 to determine whether the fake is ligher or heavier than the nonfakes (as required by the question). Once I figured that out, it made perfect sense to me!
 RG>
Jack Saladin wrote:etc., lock'd
Mighty Jalapeno wrote:At least he has the decency to REMOVE THE GAP BETWEEN HIS QUOTES....
Sungura wrote:I don't really miss him. At all. He was pretty grouchy.

 Posts: 9
 Joined: Sat Aug 05, 2006 4:09 am UTC
 theneutralnewt
 Posts: 15
 Joined: Mon Aug 07, 2006 8:49 am UTC

 Posts: 9
 Joined: Sat Aug 05, 2006 4:09 am UTC
kira wrote:ShellSh0ck wrote:xkcd wrote:ShellSh0ck wrote:Ah, this is easy. Took me maybe about 10 seconds.
Please post this answer.
Um. Okay.
Now, Randy. Just because the new kids are sometimes a little arrogant doesn't mean you have to spoil ALL of their fun.
Aww, I hate when my attempts at concision are mistaken for attempted derision!
But also, those damn kids! They should get off my lawn, etc.
:)
you need a fist shaking emoticon to use when you are actually complaining about us kids these days.
blistering guitar solo
My try
my first try ended with some paths requiring 4 weighings My next attempt had 3, but I found a flaw in the logic.. my final one was quite similar to Manny's. I wrote it out in psuedo code, thinking that would be short and concise, but it ended up being kind of big... you can check it out here : my solution
Oh, first time here.. Hi guys..
Oh, first time here.. Hi guys..
I fiddled around with the 12 and had a few ideas that would find the different coin but not necessarily tell me if it was lighter or heavier, so I decided to find easier pickings first.
I worked out how to answer it for three coins first (can be done in two weighs), then four and so on until I'd worked my way up to twelve. I stalled for a bit at ten until I worked out how to find which one was different if you have (a+b+c+d)>(e+f+g+h), with an extra coin "i" that is known to be normal, in two weighings.
The results look suspiciously like C functions, because... well... there are times when my brain just outputs C code instead of thoughts.
My results can be found here. The really interesting functions are the ones with a maxdepth of one or two. They let you do some awfully clever things if your previous tests have come up with useful information about a few of the coins.
I need to go grocery shopping now, but when i get back I intend to have a read through the solution already offered on the page. I may also supplement my collection of solutions with pretty little tree diagrams, if I feel so inclined.
I'm off to buy some groceries and then I'm finally going to have a look at the other solution posted earlier.
<later...>
My "Case 1" solution is different. MannyMax introduces two "control" coins and performs a 4v4 weigh with two leftovers. I introduce one control coin for a 3v3 weigh with three leftovers. Both are, as I understand them, correct.
Tomorrow my job consists of driving for 2.5 hours to deliver and install two 17" LCD monitors. I believe the rest of the day will give me plenty of time to either find another puzzle to obsess over or to draw trees of the various weighings required for different numbers of coins. My job's awesome.
I worked out how to answer it for three coins first (can be done in two weighs), then four and so on until I'd worked my way up to twelve. I stalled for a bit at ten until I worked out how to find which one was different if you have (a+b+c+d)>(e+f+g+h), with an extra coin "i" that is known to be normal, in two weighings.
The results look suspiciously like C functions, because... well... there are times when my brain just outputs C code instead of thoughts.
My results can be found here. The really interesting functions are the ones with a maxdepth of one or two. They let you do some awfully clever things if your previous tests have come up with useful information about a few of the coins.
I need to go grocery shopping now, but when i get back I intend to have a read through the solution already offered on the page. I may also supplement my collection of solutions with pretty little tree diagrams, if I feel so inclined.
I'm off to buy some groceries and then I'm finally going to have a look at the other solution posted earlier.
<later...>
My "Case 1" solution is different. MannyMax introduces two "control" coins and performs a 4v4 weigh with two leftovers. I introduce one control coin for a 3v3 weigh with three leftovers. Both are, as I understand them, correct.
Tomorrow my job consists of driving for 2.5 hours to deliver and install two 17" LCD monitors. I believe the rest of the day will give me plenty of time to either find another puzzle to obsess over or to draw trees of the various weighings required for different numbers of coins. My job's awesome.

 Posts: 4
 Joined: Wed Sep 20, 2006 12:05 pm UTC
the way i'd do this (came up with it in a couple of min so feel free to rip it to shreads if you fancy)
12 marbles  split them 50:50 and weigh (1)
take heavyest 6 and split 50:50, weigh(2) and take heavyest, giving you the 3 with the heavyest in,
now take one at random out and weigh(3) the remaining two if one is heavyer then its the odd one out, if both balance then its the one you removed
hope that makes sence
(oh and hi, love the comic, and the brain work outs great too!)
12 marbles  split them 50:50 and weigh (1)
take heavyest 6 and split 50:50, weigh(2) and take heavyest, giving you the 3 with the heavyest in,
now take one at random out and weigh(3) the remaining two if one is heavyer then its the odd one out, if both balance then its the one you removed
hope that makes sence
(oh and hi, love the comic, and the brain work outs great too!)

 Posts: 4
 Joined: Wed Sep 20, 2006 12:05 pm UTC
(I'm using white text to hide an answer, so if you're reading on another background color, please don't read on unless you want it.)
The solutions given above work, but when I solved it, I stumbled on another, though there could be a flaw in it. It involves dividing the marbles into three sets of four, as in the other solutions; in the case where two weigh the same, the answer is the same as the ones given before. Otherwise, it goes as follows:
Call the marbles on the heavier side A, B, C, and D, and those on the lighter side E, F, G, and H. Weigh ABE vs. CDF. If ABE is heavier, that means that either A or B is heavy, or F is light. Weighing A against B resolves that one. If CDF is heavier, than either C or D is heavy, or E is light  the same situation. If the two have the same weight, G or H is light. Then weighing either G or H against a known normal marble, like A, will tell you which.
The solutions given above work, but when I solved it, I stumbled on another, though there could be a flaw in it. It involves dividing the marbles into three sets of four, as in the other solutions; in the case where two weigh the same, the answer is the same as the ones given before. Otherwise, it goes as follows:
Call the marbles on the heavier side A, B, C, and D, and those on the lighter side E, F, G, and H. Weigh ABE vs. CDF. If ABE is heavier, that means that either A or B is heavy, or F is light. Weighing A against B resolves that one. If CDF is heavier, than either C or D is heavy, or E is light  the same situation. If the two have the same weight, G or H is light. Then weighing either G or H against a known normal marble, like A, will tell you which.
We did a problem just like this in my 18.310 (principles of applied mathematics) class... using nonadaptive weighing (ie, putting set groups of coins on the scale and then later working out which is the bad one) we had to design a spreadsheet that would let you find the bad coin out of 41 coins in only 4 weighings AND find out whether it's heavier or lighter. The 3 weighings for 12 coins case is easy by extension.
<3!
 peri_renna
 Posts: 85
 Joined: Wed Sep 20, 2006 2:52 pm UTC
 Contact:
I like jwwells' solution better than mine. It seems more elegant to avoid using a "control" coin/marble. I may rewrite my collection to employ this sort of method.
The "4 set weighings for up to 41 marbles" one sounds like a cool way to burn up my afternoon at work.
Once again, I'll start at just a few marbles and then try to come up with clever tweaks to add extras until I manage to hit that crazy 41marble requirement.
The "4 set weighings for up to 41 marbles" one sounds like a cool way to burn up my afternoon at work.
Once again, I'll start at just a few marbles and then try to come up with clever tweaks to add extras until I manage to hit that crazy 41marble requirement.
For anybody interested, I believe I've come up with a way to identify which of THIRTEEN coins is odd and in what way  and it only takes three nonadaptive weighings.
It's very much doable. For thirteen coins, one of which is in one of two odd states there are only twentysix states. For three weighings which could have three outputs (a>b,a=b,a<b) there are 27 possible resultsets. We can't use the "all three weighings resulted in equality" resultset because it doesn't tell us that one coin is heavier or lighter, so there are 26 useful resultsets. I believe I've found a sequence of weighings that creates a onetoone mapping of coinstates to resultsets. Results will be posted in an hour or two when I get home and can get at my webserver.
I'm sure my solution could be expanded to cover the 80 useful results of four set weighings so that it allows for the 80 coinstates of 40 coins. But 41 coins? I'm not so sure.
It's very much doable. For thirteen coins, one of which is in one of two odd states there are only twentysix states. For three weighings which could have three outputs (a>b,a=b,a<b) there are 27 possible resultsets. We can't use the "all three weighings resulted in equality" resultset because it doesn't tell us that one coin is heavier or lighter, so there are 26 useful resultsets. I believe I've found a sequence of weighings that creates a onetoone mapping of coinstates to resultsets. Results will be posted in an hour or two when I get home and can get at my webserver.
I'm sure my solution could be expanded to cover the 80 useful results of four set weighings so that it allows for the 80 coinstates of 40 coins. But 41 coins? I'm not so sure.
I didn't have my USB memory stick with me at work, so I didn't bring my file home. Attempts to recreate it here have succeeded only in making me wonder how I buggered things up when I was doing it at work.
My 13solution must've had a duplicate entry somewhere. There are definitely 26 meaningful sets of results for 13 weighs, but the first weigh would require 5 coins to be weighed against 4 and makes one of the results unachievable. If we had a 14th "control" coin, 13 coins could be analysed in three nonadaptive weighings.
Something similar is going to happen in the four nonadaptive weighings scenario. I believe the maximum number of meaningful, achievable results is only going to be somewhere around the 38 mark. I could be mistaken. We shall see.
My 13solution must've had a duplicate entry somewhere. There are definitely 26 meaningful sets of results for 13 weighs, but the first weigh would require 5 coins to be weighed against 4 and makes one of the results unachievable. If we had a 14th "control" coin, 13 coins could be analysed in three nonadaptive weighings.
Something similar is going to happen in the four nonadaptive weighings scenario. I believe the maximum number of meaningful, achievable results is only going to be somewhere around the 38 mark. I could be mistaken. We shall see.
Note: The nomenclature that works best for me is to call marbles that are either heavy or normal H, call marbles that are either light or normal L, call unknown marbles U, and call definitely normal marbles N. This simplifies things, though we get long rows of H's and L's.
For example, one possible state of the 12marble solution looks like this:
HHHHLLLLNNNN. (I know that four are either heavy or normal, four are either light or normal, and four are definitely normal.)
The other possible state after the first weighing is:
NNNNNNNNUUUU. (Which we can simplify to UUUU + N pool.)
Or, if you prefer, 4U NP. This helps me a lot.
Below is a stepbystep reasoning process that gets to the solution to the 39marble case. It's a lot of recursion, really.
(More white text ahead:)
You can do exactly nine marbles in two weighings in the current setup, provided that the situation is either HHHHHLLLL or HHHHLLLLL.
It's easy. Weigh HHL vs. HHL, leaving HLL aside, in the first case. (In the second case, it's just LLH vs. LLH, leaving HHL aside.) No matter what the outcome, you're left with 2H 1L or viceversa, which is solvable in one weighing. This is a variation on the same trick I used to solve the 12case, but with 9 marbles instead of 8.
Call this the 5and4 trick  we can solve 5H 4L or 5L 4H in two weighings. It's going to REALLY come in handy.
For example, if we have 13 marbles and a control N, we can solve it in 3 moves by first weighing 5U vs 4U 1N, setting aside 4U. This either gives us a 5and4 case, or a 4unknowns case, both of which can be solved in the remaining 2 moves.
Using the 5and4 trick repeatedly lets us deal with 27 marbles in three weighings, provided that the situation is either 14H 13L or 13H 14L. For example, in the 14H 13L case, divide them into these groups:
5H 4L, 5H 4L, 4H 5L
(Notice the analogy to HHL, HHL, LLH!)
And weigh the first two against each other. That takes one weighing. Then you've got two weighings left, and all of those are 5and4 scenarios.
If we can weigh 27 marbles, well we can solve the 40marble setup, right? Just weigh 14 against 13andacontrol. This puts us in the 14and13 setup above and leaves us with 13 unknowns. We can deal with 13 unknowns, easy! We've got the procedure above.
Oh, wait. No control. Oh, well. You can solve the 40case if you smuggle a normal marble in, maybe from one of the earlier problems. On the bright side, the 39case is easy now.
Make 3 groups of 13. Weigh two against each other. If they weigh the same, we have 13U NP, our 13Uandacontrolinthreeweighings case, solved above. Otherwise, we have 13H 13L NP. That uses one weighing.
Weighing 2: Set aside 5H 4L, and weigh 4H 4L 1N vs. 4H 5L. If the two weigh the same, we've got 5and4 with two weighings to go. Otherwise, we either have 4H 5L NP (5and4) or 4H 4L NP (4and4, which we split into HHL vs HHL with leftover LL  easy.) Either way, we solve it in the remaining 2 weighings.
BUT HOW DO WE DO IT WITH 41?!
For example, one possible state of the 12marble solution looks like this:
HHHHLLLLNNNN. (I know that four are either heavy or normal, four are either light or normal, and four are definitely normal.)
The other possible state after the first weighing is:
NNNNNNNNUUUU. (Which we can simplify to UUUU + N pool.)
Or, if you prefer, 4U NP. This helps me a lot.
Below is a stepbystep reasoning process that gets to the solution to the 39marble case. It's a lot of recursion, really.
(More white text ahead:)
You can do exactly nine marbles in two weighings in the current setup, provided that the situation is either HHHHHLLLL or HHHHLLLLL.
It's easy. Weigh HHL vs. HHL, leaving HLL aside, in the first case. (In the second case, it's just LLH vs. LLH, leaving HHL aside.) No matter what the outcome, you're left with 2H 1L or viceversa, which is solvable in one weighing. This is a variation on the same trick I used to solve the 12case, but with 9 marbles instead of 8.
Call this the 5and4 trick  we can solve 5H 4L or 5L 4H in two weighings. It's going to REALLY come in handy.
For example, if we have 13 marbles and a control N, we can solve it in 3 moves by first weighing 5U vs 4U 1N, setting aside 4U. This either gives us a 5and4 case, or a 4unknowns case, both of which can be solved in the remaining 2 moves.
Using the 5and4 trick repeatedly lets us deal with 27 marbles in three weighings, provided that the situation is either 14H 13L or 13H 14L. For example, in the 14H 13L case, divide them into these groups:
5H 4L, 5H 4L, 4H 5L
(Notice the analogy to HHL, HHL, LLH!)
And weigh the first two against each other. That takes one weighing. Then you've got two weighings left, and all of those are 5and4 scenarios.
If we can weigh 27 marbles, well we can solve the 40marble setup, right? Just weigh 14 against 13andacontrol. This puts us in the 14and13 setup above and leaves us with 13 unknowns. We can deal with 13 unknowns, easy! We've got the procedure above.
Oh, wait. No control. Oh, well. You can solve the 40case if you smuggle a normal marble in, maybe from one of the earlier problems. On the bright side, the 39case is easy now.
Make 3 groups of 13. Weigh two against each other. If they weigh the same, we have 13U NP, our 13Uandacontrolinthreeweighings case, solved above. Otherwise, we have 13H 13L NP. That uses one weighing.
Weighing 2: Set aside 5H 4L, and weigh 4H 4L 1N vs. 4H 5L. If the two weigh the same, we've got 5and4 with two weighings to go. Otherwise, we either have 4H 5L NP (5and4) or 4H 4L NP (4and4, which we split into HHL vs HHL with leftover LL  easy.) Either way, we solve it in the remaining 2 weighings.
BUT HOW DO WE DO IT WITH 41?!
Last edited by jwwells on Sat Sep 23, 2006 9:06 am UTC, edited 1 time in total.
And, following a hunch, I found a proof (which, to be fair, I didn't verify) that says that you can't do more than 39 coins in four weighings unless you have a control coin  assuming you need to find out heavy or light. If you have an extra coin, AND you don't need to find out heavyorlight, you can do 41 coins.
Proof by induction given here:
http://home.att.net/~numericana/answer/ ... m#birthday
Proof by induction given here:
http://home.att.net/~numericana/answer/ ... m#birthday
You're right about the good coin  I forgot that was part of the problem in class and not here as well. However, with the good coin, you can definitively tell if the bad coin is heavy or light for 40 of the 41 possibly bad coins (the exception being, of course, if the bad coin is the one coin never placed on the balance).
Here are course notes on the topic of nonadaptive weighings, if anyone's curious.
Here are course notes on the topic of nonadaptive weighings, if anyone's curious.
<3!
Who is online
Users browsing this forum: Google Feedfetcher and 4 guests