## Weighing Marbles

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Jesse
Vocal Terrorist
Posts: 8635
Joined: Mon Jul 03, 2006 6:33 pm UTC
Location: Basingstoke, England.
Contact:
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
Has a big nose
Posts: 11
Joined: Fri Jul 07, 2006 7:08 pm UTC
I've got the solution. Good puzzle.

aaronspook
Posts: 20
Joined: Thu Jul 20, 2006 9:55 pm UTC
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
Site Ninja
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC
Contact:
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
Posts: 76
Joined: Thu Jul 20, 2006 11:43 pm UTC
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
Posts: 426
Joined: Mon Jun 26, 2006 5:03 pm UTC
Location: a planet called Erp
Contact:
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.
I burn the cheese. It does not burn me.

Charodei
Posts: 86
Joined: Fri Jul 21, 2006 8:29 pm UTC
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
Posts: 37
Joined: Thu Jul 13, 2006 9:38 am UTC
Location: Florida
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
Has a big nose
Posts: 11
Joined: Fri Jul 07, 2006 7:08 pm UTC
Fleshpiston wrote: 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?
I've got a signature! Wheeeee!

wisnij
Posts: 426
Joined: Mon Jun 26, 2006 5:03 pm UTC
Location: a planet called Erp
Contact:
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 burn the cheese. It does not burn me.

Axolotl
Posts: 107
Joined: Fri Jul 21, 2006 5:15 am UTC
Location: Melbourne
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
Site Ninja
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC
Contact:
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.

Axolotl
Posts: 107
Joined: Fri Jul 21, 2006 5:15 am UTC
Location: Melbourne
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
Posts: 1
Joined: Wed Aug 02, 2006 4:52 am UTC
Location: MN
Contact:
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
Posts: 20
Joined: Thu Jul 20, 2006 9:55 pm UTC
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
Posts: 10
Joined: Tue Jul 04, 2006 10:49 am 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 1-12 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: 6704
Joined: Thu May 18, 2006 7:17 am UTC
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 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>
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.

Shellsh0ck
Posts: 9
Joined: Sat Aug 05, 2006 4:09 am UTC
Ah, this is easy. Took me maybe about 10 seconds.

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

theneutralnewt
Posts: 15
Joined: Mon Aug 07, 2006 8:49 am UTC
Shellsh0ck wrote: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
Site Ninja
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC
Contact:
Ah, this is easy. Took me maybe about 10 seconds.

Shellsh0ck
Posts: 9
Joined: Sat Aug 05, 2006 4:09 am UTC
xkcd wrote:
Ah, this is easy. Took me maybe about 10 seconds.

Um. Okay.

kira
I hate bananas.
Posts: 904
Joined: Fri Apr 14, 2006 4:21 am UTC
Location: school
Contact:
Now, Randy. Just because the new kids are sometimes a little arrogant doesn't mean you have to spoil ALL of their fun.

xkcd
Site Ninja
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC
Contact:
kira wrote:
ShellSh0ck wrote:
xkcd wrote:
ShellSh0ck wrote:Ah, this is easy. Took me maybe about 10 seconds.

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 hate bananas.
Posts: 904
Joined: Fri Apr 14, 2006 4:21 am UTC
Location: school
Contact:
I assumed you were deriding. Maybe that's just because I would have deridden. Derode. Derided.

posiduck
Posts: 136
Joined: Fri Aug 11, 2006 4:47 am UTC
Location: Geography City, CA
Contact:
you need a fist shaking emoticon to use when you are actually complaining about us kids these days.
blistering guitar solo

SClay
Posts: 3
Joined: Thu Sep 14, 2006 9:29 pm UTC

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

Teaspoon
Posts: 351
Joined: Tue Sep 12, 2006 11:37 pm UTC
Location: Where you least expect me
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
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!)

DaveFP
Posts: 76
Joined: Thu Jul 20, 2006 11:43 pm UTC
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
Posts: 4
Joined: Wed Sep 20, 2006 12:05 pm UTC
DaveFP wrote: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
Posts: 180
Joined: Thu Sep 21, 2006 4:47 am 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.

Penguin
Posts: 98
Joined: Wed Jul 05, 2006 2:54 pm UTC
Location: Cambridge, MA
Contact:
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.
<3!

peri_renna
Posts: 85
Joined: Wed Sep 20, 2006 2:52 pm UTC
Contact:
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
Posts: 351
Joined: Tue Sep 12, 2006 11:37 pm UTC
Location: Where you least expect me
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
Posts: 351
Joined: Tue Sep 12, 2006 11:37 pm UTC
Location: Where you least expect me
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
Posts: 351
Joined: Tue Sep 12, 2006 11:37 pm UTC
Location: Where you least expect me
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
Posts: 180
Joined: Thu Sep 21, 2006 4:47 am UTC
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.

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?!
Last edited by jwwells on Sat Sep 23, 2006 9:06 am UTC, edited 1 time in total.

jwwells
Posts: 180
Joined: Thu Sep 21, 2006 4:47 am UTC
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:

Penguin
Posts: 98
Joined: Wed Jul 05, 2006 2:54 pm UTC
Location: Cambridge, MA
Contact:
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.
<3!