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

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