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]

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.