Puzzle time!

[fluffymark]

Insomnia makes me do odd things. Last night I decided to twist a well known puzzle to make it more evil, and then solve it, which I did. And this stopped me thinking of monsters under the bed and other scaries (I read the Nightmares and Fairy tales graphic novel yesterday, and it may have gotten to me...ooops), so was actually a good thing, I'm trying to tell myself.

Anyway, lets see which of you clever people solves this first: (all comments initially screened)

You have a balance scale and a big bag of marbles. The marbles are all identical in weight. You take 39 of the identical marbles and mix in another special marble (so 40 marbles now), which may be heavier or lighter than the others, or may not, but looks identical, so can be identified by weight alone. Allowing only 4 weighings, how can you identify whether the special marble is heavier or lighter than the others, and if so, which marble it is?

Update: Congratulations to the clever ixwin who solved it by adding more marbles from the bag. So, lets make the problem HARDER. Assume the bag only has one more marble left in it. You have the original 40 marbles (39 identical and one special) and a bag with one more marble in it. Now solve it.

Comments

[fluffymormegil.livejournal.com]

Ooof. That one's bad enough with a rather smaller number of marbles.

[fluffymark]

*evilgrin* I know. ;)

[karen2205]

Umm - how about

1, Weigh the whole bag - this gives you the weight of 39× + y.
2, Weigh an individual marble - this either gives you × or y.
3, Weigh another individual marble - again you either get × or y.

If 2 and 3 are the same weight then you know they were both ×, so multiply that weight by 39 - giving the weight of the 39 original marbles and subtract that from the total weight of the bag. The answer is the weight of y and you can tell from this whether × is greater than y.

If 2 and 3 are different weights then one is × and one is y, so weigh another marble to find out which one is which.

(am I anywhere close to the mark with this? am I missing something obvious? eg. 39 marbles identical in weight - doesn't mean they're identical in other respects.)

[fluffymark]

Ooops. No, thats way out.

Clarification: It's a balance scale. You put some marbles on one tray, some others in another tray, and it either balances or one side goes up and the other side goes down. That is all it tells you.

You also need to identify which marble is the odd marble, if it is not the same weight as the others. This is the real challenge.

The marbles are all totally identical in appearance. One marble may have a different weight. You can label them 1-40 for identification purposes.

[deborah_c]

For further clarification: are you required to work out which of "lighter" or "heavier" the odd marble is, assuming that it is one of them, or simply that it is different from the others?

[fluffymark]

Yes, you are required to find out which of "heavier" or "lighter" it is.

[zotz]

I can see how to narrow it down to five and know whether the ringer's lighter or heavier, but I can't see how to get further in only four weighings. I think I could maybe get that far in three, actually, but narrowing it down past 5 remains a problem.

[fluffymark]

Close, but not close enough. I don't claim the answer is simple, easy or obvious. But I do claim it can be solved. :)

[ixwin.livejournal.com]

My initial reasoning suggests it isn't possible for the following reason.

Okay, for each weighing you've got 3 possible outcomes - left side of the scale down, right side of the scale down, or a balance. So after 4 weighings you've got 3x3x3x3=81 possible results (e.g. balance, left, right, right) to point to 80 possible situations (i.e one each of 40 marbles, each of which might be lighter or heavier than average). So far, so good.

By the same logic, after the first weighing, you must be down to no more than 3x3x3=27 possible states, whatever the result of that first weighing.

Now the only thing that makes any sense is weighing x against x marbles. If you weight x against x and they don't balance, you know the marble is either on the lighter side and lighter, or on the heavier side and heavier, i.e. if you identify the marble from this point on, that in itself will tell you whether it's heavier or lighter. If they do balance, all you know is that the remaining marble is one of the ones not currently on the scale, and you don't yet know if it's heavier or lighter.

Therefore, if you weigh x against x marbles, and they balance, you have 2*(40-2x) possible options left (e.g. if you weigh 12 against 12, and they balance, you know the uneven marble is one of the remaining 16, but it might be either lighter or heavier i.e. you have 32 remaining possibilities and only 27 possible results, so that doesn't work. To have 27 or fewer possibilities at the end of the first weighing if they balance, you need to weigh at least 14 against 14 in the first weighing.

BUT if you weigh 14 against 14 in the first weighing, and they don't balance, you have 28 possible balls to choose from, and you can't pick one of 28 balls from 3 weighings (because of the only 3x3x3=27 possible results).

I may very well be wrong about this, but if so I'd be very interested to know why the above doesn't hold.

[fluffymark]

*nods*. Good start, and you're entirely correct so far. :)

Hint: There are still more marbles in the bag.

[ixwin.livejournal.com]

Ah cunning...

[fluffymark]

I am evil. ;)

[fluffymormegil.livejournal.com]

Thirteen, against thirteen from the bag, gives either a pool of thirteen to chop, or a pool of 27, and reveals the direction.
If the thirteen are out of balance, weigh six against six; if they match, the thirteenth is the ringer, otherwise split the six with the ringer 3/3 and then match two of the three with the ringer.
If the 27 are out, weigh nine against nine; weigh three against three from whichever of the three nines is the ringer; weigh two of the three with the ringer.
(and I don't think your wrinkle is evil, I think it's obnoxious.)

[fluffymark]

Not quite, but close. What happens if your first weighing is balanced? You then have 27 untested marbles, and no clue about direction. All bad.

[ixwin.livejournal.com]

...in which case, you can start by weighing 27 of the 40 against 27 of the others in the bag. That gives you either 27 where you know which of heavier or lighter the marble is (if the scales don't balance), or 13 where you don't (i.e. 26 possibilities) (if they do).

[fluffymark]

Yep yep yep. :)

[ixwin.livejournal.com]

Then, if you've got it down to 27 and you know one of them's lighter (obviously exactly the same would apply for heavier), it's 9 against 9 to get which 9 it's in, then of that 9 3 against 3 to get which 3 it's in, and then of that 3, 1 against 1. In each case, it's whichever end of the scales tip up, if they're unbalanced, and the ones not on the scales if they do balance.

If you've got it down to 13, and you don't know which way they balance then...(back in a minute)

[fluffymark]

You've got the right idea. Keep going.... :)

[ixwin.livejournal.com]

...then you're back in the same bind that weighing them against each other will give you more than 9 possibilities from some results.

So instead, weigh 9 of the 13 against 9 of known weight. If the scale doesn't balance, you're back in the previous scenario - 2 weighings to identify 1 of 9 where you already know if it's heavier or lighter.

If the scale balances you're down to 4 and so weigh 3 of them against 3 of known weight. Then you've either got 1 weighing for 1 of 3 where you know if it's heavier or lighter (same as above), or 1 known odd-one-out ball, which you can weigh against any of known weight to work out if it's heavier or lighter.

That is a very nice puzzle...

[fluffymark]

*bounces* Solved. Yaaaaaay! Well done! :)

That was the easier version. Next assume you only have 1 spare marble in the bag to play with. It can still be solved.

[ixwin.livejournal.com]

Now that is evil.

Maybe later. I must do some actual work...

[fluffymark]

*nods* I must do work too...but this has been lots of fun. :)

[ixwin.livejournal.com]

Okay, having done some work...

Weighing 1

Weigh 14 of the unknown against 13 of the unknown and the 1 known.

If they balance, you know it's one of the 13 not on the scales, and you can solve as the previous case (as you now know that all of the marbles on the scales are of standard weight).

If they don't balance (and assuming the side with 14 of known weight was heavier - obviously just reverse light and heavy if the reverse is true),call the ones on the heavy side, possibly-heavy marbles, and the ones on the light side possibly-light marbles. You have 14 possibly-heavy, 13 possibly-light and 14 of known standard weight.

Weighing 2

Put 5 possibly-heavy marbles and 9 possibly light marbles on the left side of the scales, and 4 possibly-light and 10 known-weight marbles on the right side. This leaves 9 possibly-heavy marbles not in this weighing.

If the scales balance, you know the odd marble is heavier and one of the 9 not currently on the scales. It reduces to the previously solved case, where you are choosing between 9 and the direction is known and you have 2 weighings left.

If the left side of the scales rises, you similarly know that the odd marble is lighter, and one of the 9 possibly lighter ones on the left side. Again, you've reduced it to the previous case.

If the right side of the scales rises, you know it's either one of the 5 possibly-heavy ones on the left hand side, or one of the 4 possibly-light ones on the right hand side. In which case, proceed to weighing 3.

Weighing 3
Put 3 of the possibly-heavy and 3 of the possibly-light on one side of the scale, and 6 of known weight on the other.

If the left side rises you know it's one of the 3 possibly-light ones on the left hand side, and likewise if it falls you know it's one of the three possibly-heavy ones on the left hand side. (either way, reducing it again to the previously solved case for the final weighing)

If it balances, you know it's one of the two possibly-heavy ones, or the one possibly-light one that were left off the scales for weighing 3. In which case, weighing 4 comprises one possibly-heavy, and one possibly-light against 2 of known weight, which gives you your final answer by the same process of deduction as used for weighing 3.

[fluffymark]

We have a winner. :) Easy when you know how. Very clever Liz! :)

And for my next trick, take 120 identical marbles and the special one, and 1 more in the bag, and solve it with 5 weighings...

[fluffymormegil.livejournal.com]

I can't do four. Here's how to do it in a maximum of six.
Weigh 12 against 12. This leaves 16 unweighed. If the 12s match, we have a reference marble weight; weighing 16 reference marbles against the unweighed 16 gives us the direction of the difference. If the 12s don't match, swapping out one of the 12s for the other lets us get the reference marble weight and the direction. [two weighings]
OK. We now have the bad marble narrowed down to one of 12 or 16 marbles, and know whether it's heavy or light.
If 12: Split into sixes, balance. Split the anomalous six into threes, balance. Take two of the anomalous three and balance; if the match, the third is the odd one out; if they don't, the known direction of imbalance tells us which of the tested pair is bad. [three more weighings for a total of five]
If 16: Split into eights, balance. Split the anomalous eight into fours, balance. Split the anomalous four into twos, and balance. Take the anomalous pair, balance, and use the known sign to determine which of them is bad. [four more weighings for a total of six]

[fluffymark]

Sounds plausible for 6 weighings. You're wasting known information. You can do better than halving the unknown in each weighing.

[the-alchemist.livejournal.com]

OK, this seems obvious to me. Tell me what I'm doing wrong! *wince*

WEIGHING 1
You put twenty marbles in each side. If the scale doesn't balance then the special marble is either heavier or lighter than the others.

WEIGHING 2
You lay marbles 1-20 aside.
You put marbles 21-30 in one side of the balance
You put marbles 31-40 in the other side.
If they balance, then go to 'weighing 3a'. If they don't, go to 'weighing 3b'.

WEIGHING 3a
Discard marbles 21-30 altogether and put marbles 1-10 in their place.
If marbles 1-10 weigh more than marbles 31-40, then the special marble is heavier.
If marbles 1-10 weigh less than marbles 31-40, then the special marble is lighter.
If they weigh the same, go to 'weighing 4a'

WEIGHING 3b
Lay marbles 31-40 aside.
Put marbles 1-10 in their place.
If marbles 21-30 are heavier than marbles 1-10 then the special marble is heavier.
If marbles 21-30 are lighter than marbles 1-10 then the special marble is lighter.
If they weigh the same, go on to weighing 4b.

WEIGHING 4a
Discard marbles 1-10, and repeat 'weighing 3a' using marbles 11-20 instead of them.
If marbles 11-20 weigh more than marbles 31-40, then the special marble is heavier.
If marbles 11-20 weigh less than marbles 31-40, then the special marble is lighter.
If they weigh the same then something has gone wrong!

WEIGHING 4b
Discard marbles 1-10, and repeat 'weighing 3b' using marbles 11-20 instead of them.
If marbles 11-20 weigh more than marbles 31-40, then the special marble is lighter.
If marbles 11-20 weigh less than marbles 31-40, then the special marble is heavier.
If they weigh the same then something has gone wrong!


Couldn't it be done in three weighings, leaving off weighing one? I'm sure I'm missing something here (and if I'm right, I bet there's a less long-winded way of expressing it.)

[fluffymark]

The key problem is to identify *which* of the 40 marbles it is, not just whether is is heavier or lighter. ;)

[the-alchemist.livejournal.com]

I still think I win. My superior English-studenty sentence-parsing skills cut through the Gordian Knot of your mathematical cunning.

[fluffymark]

The question was never ambiguous. Look at it. It says marble. It is your memory of an ambiguous question that is incorrect. ;)

(Orwell taught me everything I need to know...)

[the-alchemist.livejournal.com]

Hmm... looking at the other comments, I think I might have misinterpreted the question. You said: "how can you identify whether the special marble is heavier or lighter than the others, and if so, which one it is?" I interpreted "which one" as meaning "which one:heavier or lighter?" but perhaps you meant which one of the marbles, which would be much more difficult. Clarify?

(I still think I win due to the ambiguity though!)

[fluffymark]

Bah! Edited to remove ambiguity. ;)

[fluffymormegil.livejournal.com]

Overall: I think the use of "big" is bad; it fails to make clear that there are an arbitrarily large number of extra marbles available.

[fluffymark]

Bonus question: Assume only 1 extra marble is available. Now attempt to solve it. This is *EXTRA* hard, but can still be done. I've done it.

[deborah_c]

(We got to the first solution a little after ixwin, but I have been trying to work as well.)

In each case, we want to partition state space exactly in three.

Start by weighing 1-14 vs 15-27 + spare

If they balance, then either the 40th ball is of the same weight as the others (1 case), or one of 28-40 is either heavier (13) or lighter (13) than the others, and we've reduced to one of the cases from the original problem - 13 unknown balls.

If the left side goes down, then weigh 1-5,15-18 vs 6-10,19-22

If these balance, then either one of 11-14 is heavier, or one of 23-27 is lighter (4+5 = 9 cases)
If the left side goes down, then either one of 1-5 is heavier, or one of 19-22 is lighter (5+4 = 9 cases)
If the right side goes down, then either one of 6-10 is heavier, or one of 15-18 is lighter (5+4 = 9 cases)

Suppose the first of these cases. Then weigh 11,12,23 vs 13,14,24.
This divides into (balanced) 25 light, 26 light, or 27 light; (left down) 11 heavy, 12 heavy or 24 light; (right down) 13 heavy, 14 heavy, 23 light.
In the first case, weigh 25 vs 26, as in the original. In the second and third cases, weigh the two potentially heavy marbles against each other.

Similarly for the other branches, which I won't work out here to save my remaining vestigial sanity, but where the same procedure holds.

[fluffymark]

Sounds all in order and correct! Well done! Have to tell you ixwin got there first again, but I've been in a meeting until now and unable to unscreen the comments. Actually your solution is different to ixwin's slightly (different choice of balls at the 2nd weighing) but is the same as mine (I think). Is a very nice problem, I think.

[(Anonymous)]

After the first weighing of 1..14 and 15..27+known good one you've got tons of known good marbles anyway?

Joe

[fluffymark]

True, but you're in a more complicated situation in that you still don't know if the special marble is heavier or lighter yet, so have to design the subsequent weighings far more subtly. See ixwin's and deborah_c's solutions (now unscreened) above - the solution is non-trivial!

[(Anonymous)]

I'd seen it for 12 and 13 before, so I knew the naughty trick with the spare marble. Once you know that you've just got to work it down.

Incidentally, how about finding the odd marble from 41, given it definately does weigh more or less than the others and you have a spare good marble.

Also, I've got a special puzzle for you and any physicists you know -

If you have an n dimensional hypercube of 1 ohm resistors, where each edge of the hypercube is a resistor, what is the resistance between the two opposite corners?

Joe

[fluffymark]

Oh evil Joe - last I heard the hypercube resistor problem had no known general solution for opposite corners. It can be solved for any particular n by slogging through reconnecting all the equipotential points and redefining it as a series of n parallel slabs of resistors, and working out the resistance of each slab. Or there is a solution for adjacent corners, I think. But I'm not working it out right now.

[feanelwa.livejournal.com]

I'm not allowed to pick them up one by one and guess, am I?

[fluffymark]

Especially for you, lets assume the special marble is only different by the weight of an atom, and you have a wonderful atomic scale balance that measures to that accuracy. Your fingers are not an atomic scale balance. ;)

[feanelwa.livejournal.com]

If it's only different by the mass of one atom, and assuming the marbles are all of the same size, then the increment in density is negligible or can be put down to experimental error, the extra marble is the same as all the others and it is a trick question.

[fluffymark]

hooray! The physicist's solution. I suppose that might be valid. :)

[dreamfracture.livejournal.com]

Ahh. Done it for the version with 40 and only one spare marble. I'm not sure I feel like writing out the full solution, it would take forever...

Is there a formula for the maximum number of marbles you can sort out for N uses of the scales?

[fluffymark]

Yay - well done! ixwin has written out *a* solution above somewhere, and yes, it is very long isn't it? :)

Formula is easy to work out - each use of the scale has 3 possible results (balanced, left side down or right side down), so N uses of the scales gives 3^N possible results. Now if there are M marbles, there are M results where a marble is heavier, and M results where a marble is lighter, and also the single possible case where the special marble is the same weight as all the others. Hence we must have that 3^N = 2M+1, which we can rearrange to get the formula for the number of marbles M = (3^N - 1)/2 (which correctly gives M=40 when N=4).

I must sound like a maths teacher. Forgive me.

Anyway, I'm wondering who you are. Have I met you on my wanderings in Cambridge or not?