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]

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.