Weighing Marbles

[aaronspook]

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.

[Jesse]

Ah, I love this one. It's the first ever logic puzzle I was ever given (That I can remember as being a specific logic puzzle)

[sniffels]

I've got the solution. Good puzzle.

[aaronspook]

Really? It seemed so hard to me. Guess I was looking at it the wrong way. Well, anybody actually having trouble finding the answer?

[xkcd]

I could swear I've done this exact one before, but I'm just not seeing a simple answer this time. It's concievable I only did it with the "find a heavier marble" version, but . . .

[DaveFP]

Even though I saw this before somewhere (with the answer), I have no idea what the solution might be. I keep getting stuck because the 'odd' marble can be heavier or lighter, so when the scales tip you can't tell which side it's on.

[wisnij]

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.

[Charodei]

Like xkcd and DaveFP, I'm sure I've seen this before. Having trouble coming up with the solution again, though. My best approach so far has a 1/6 chance of knowing if the odd marble is lighter or heavier than the rest, but not which one of two it is. So close...

[Fleshpiston]

I got it. It's a good puzzle, especially because just when you think you have it you realize you are not quite there.

[sniffels]

especially because just when you think you have it you realize you are not quite there.

It's tricksy like that, it is...

Anyone want a hint? New thread for hints?

[wisnij]

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.

[Axolotl]

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

[xkcd]

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.

[Axolotl]

Heheh oops. I was halfway through writing out my solution, with a disclaimer at the start asking for gentle treatment in the likely event that I'd missed something and was making a fool of myself, when I realised that in fact I had and I was. I'll keep thinking

[MannyMax]

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 9-item 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.no-ip.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.

[aaronspook]

That's pretty much the answer I got (though written up far more rigorously than I bothered to). Interestingly, there were some minor differences in group composition, so I guess the answer isn't unique.

[area]

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 1-12 being lighter or heavier. I haven't quite found a series of weighings that works yet, though.

[RealGrouchy]

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 second-order cases in Case 1 (i.e. Case 1a, 1b, 1c) require us to look at the first-order descripton of Case 1 to determine whether the fake is ligher or heavier than the non-fakes (as required by the question). Once I figured that out, it made perfect sense to me!

- RG>

[Shellsh0ck]

Ah, this is easy. Took me maybe about 10 seconds.

Oh, by the way, hi. I'm new.

[theneutralnewt]

Ah, this is easy. Took me maybe about 10 seconds.

Oh, by the way, hi. I'm new.

That's one way of introducing yourself . I, on the other hand, didn't come up with the answer by the time I looked at the solution.

Oh, and I'm new too.

[xkcd]

Ah, this is easy. Took me maybe about 10 seconds.

Please post this answer.

[Shellsh0ck]

Ah, this is easy. Took me maybe about 10 seconds.

Please post this answer.

Um. Okay.

[kira]

Now, Randy. Just because the new kids are sometimes a little arrogant doesn't mean you have to spoil ALL of their fun.

[xkcd]

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.

:)

[kira]

I assumed you were deriding. Maybe that's just because I would have deridden. Derode. Derided.

[posiduck]

you need a fist shaking emoticon to use when you are actually complaining about us kids these days.

[SClay]

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

[Teaspoon]

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.

[siliconslave]

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!)

[DaveFP]

You've misread the question. Whilst that solution works if we know one marble is heavier, the problem presented is that one marble differs in mass. We don't know if it's heavier or lighter. That makes it a lot more complicated.

[siliconslave]

You've misread the question. Whilst that solution works if we know one marble is heavier, the problem presented is that one marble differs in mass. We don't know if it's heavier or lighter. That makes it a lot more complicated.

oops, that'll learn me then will have a re-think then!

[jwwells]

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

[Penguin]

We did a problem just like this in my 18.310 (principles of applied mathematics) class... using non-adaptive 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.

[peri_renna]

Huh, jwwells got a new solution - mine was mostly the same as the others. (Took me five starts with different initial loads to get it...)

[Teaspoon]

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 41-marble requirement.

[Teaspoon]

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 non-adaptive weighings.

It's very much doable. For thirteen coins, one of which is in one of two odd states there are only twenty-six states. For three weighings which could have three outputs (a>b,a=b,a<b) there are 27 possible result-sets. We can't use the "all three weighings resulted in equality" result-set because it doesn't tell us that one coin is heavier or lighter, so there are 26 useful result-sets. I believe I've found a sequence of weighings that creates a one-to-one mapping of coin-states to result-sets. 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 coin-states of 40 coins. But 41 coins? I'm not so sure.

[Teaspoon]

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 13-solution 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 non-adaptive weighings.

Something similar is going to happen in the four non-adaptive 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.

[jwwells]

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 12-marble 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 step-by-step reasoning process that gets to the solution to the 39-marble 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 vice-versa, which is solvable in one weighing. This is a variation on the same trick I used to solve the 12-case, but with 9 marbles instead of 8.

Call this the 5-and-4 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 5-and-4 case, or a 4-unknowns case, both of which can be solved in the remaining 2 moves.

Using the 5-and-4 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 5-and-4 scenarios.

If we can weigh 27 marbles, well we can solve the 40-marble set-up, right? Just weigh 14 against 13-and-a-control. This puts us in the 14-and-13 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 40-case if you smuggle a normal marble in, maybe from one of the earlier problems. On the bright side, the 39-case is easy now.

Make 3 groups of 13. Weigh two against each other. If they weigh the same, we have 13U NP, our 13U-and-a-control-in-three-weighings 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 5-and-4 with two weighings to go. Otherwise, we either have 4H 5L NP (5-and-4) or 4H 4L NP (4-and-4, 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?!

[jwwells]

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 heavy-or-light, you can do 41 coins.

Proof by induction given here:

http://home.att.net/~numericana/answer/ ... m#birthday

[Penguin]

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 non-adaptive weighings, if anyone's curious.