You are given 12 marbles and a balance. All of the marbles look the same. 11 marbles are the same weight, but 1 marble is different. You may use the balance 3 times to determine which marble is different, and if it is lighter or heavier than the others.
There are a couple of ways to solve this problem. The first is through a series of balances, each one depending on information learned in prior balances to decide what to do. The second is by mapping each possible set of 3 balance outcomes (3 possibilities for each balance, although in order to determine weight differences you must make sure that you don’t map mirror outcomes to different marbles) to individual marbles, and then figuring out how to group the marbles so that you can get each outcome. I haven’t thought through the process of making those groups for the second solution, but have a possible version of the first.
Edit: OK, worked through the second solution too.
Before you weigh anything, every marble is full of possibility. Any one of the 12 could be the impostor, and either heavier or lighter.
We can start eliminating possibilities with our first use of the balance.
To start, we split up our 12 marbles into 3 groups of 4, and weigh two of them against each other, holding one group of four out in reserve.
Either the scale comes up equal, or it is imbalanced. In this case, the direction of the imbalance doesn’t really matter too much; either way, you have one side that could contain the heavier marble and one side that could contain the lighter.
In the diagrams, I’ve used purple to indicate that we know that a marble could be the impostor and it could be either heavier or lighter, red to indicate that it could be the impostor and if it is we know that it must be heavier, blue to indicate that it could be the impostor and if it is it must be lighter, and grey to indicate that we know that the marble is not the impostor. For each balance, it shows the group to be put on the left side of the scale, the group that goes on the right, and then the marbles of interest in reserve. The outcomes are shown on the scale with the marbles coded to the information gained from the balance.
If the balance is equal, we can eliminate the 8 marbles we’ve just weighed - the impostor is not among them. At the end of this step, we have narrowed down the possible impostor to one of 4, but we don’t have any information yet about whether it is heavier or lighter.
At this point, we can set aside 5 of the marbles that we know are not the impostor, and use the remaining 3 of those against 3 of our mystery marbles to get some more information. We set one of the mystery marbles to the side.
4 mysterious impostor candidates
If the balance comes up equal, we now know the impostor. But we still don’t know if it is heavier or lighter.
One mysterious impostor, no direction
It’s pretty simple to figure out that last bit from here; we take the mystery impostor and weigh it against one of the marbles we’ve determined is standard.
At this point, the scale can only be imbalanced and we can use its direction to determine if the impostor is heavier or lighter:
The impostor is lighter.
The impostor is heavier.
If the side with our 3 mystery marbles goes down, we’ve narrowed it down to 3 possibilities, and we know that the impostor is heavier.
If the side with our 3 mystery marbles goes up, we’ve narrowed it down to 3 possibilities, and we know that the impostor is lighter.
At this point, we’ve narrowed it down to three possible impostors and have a direction, which is enough to solve the puzzle with one more weigh.
3 possible impostors and a direction
We only need to concern ourselves with the possible impostors at this point. We put one on each side of the scale, and hold one in reserve. Here’s how that looks if the possibilities are heavier, but the same principle can be applied to a lighter set of potential impostors.
If the scale is unequal, whichever side of the scale matches the direction we’ve already found contains the impostor. If we have a balance, the marble held in reserve is the impostor.
If the balance is unequal, the impostor could be one of the 8 marbles on the balance. The 4 held in reserve are going to be our standard weight, and none of them are the impostor.
We do have a little bit more information - we know, within each group of 4 that was weighed, that if the impostor is in that group it must be heavier or lighter. We can make new groups where we spread about the known information in ways that can help us narrow down the impostor with just 2 more balances. In my head, it works if these are divided in a “lopsided” manner (technical term), where we only have one from each group where possible (since there are 4 marbles in each group and we have to split them up into left, right, and reserve that isn’t exactly possible). I feel like there’s probably a more rigorous way to understand how to make these groups, but one way that works is to put 2 of the lighter marbles on the left with one heavier, one heavier and one lighter on the right along with a standard marble, and keep the remaining 2 heavier and 1 lighter out in reserve.
8 impostor candidates, 4 that would be heavier and 4 that would be lighter
If the scale is unequal, we can use that to eliminate possibilities. In this case, we can say that possible impostors that had to be lighter cannot be the impostor if they are on the heavy side (and vice versa).
We know that none of our marbles held in reserve are the impostor, since we know that it has to be on the scale for the scale to be imbalanced.
Because of the way that we grouped our marbles, if the scale is unequal one way we now have two possible candidates, and we know whether they would be lighter or heavier.
2 possible impostors, different directions
To solve this, we put one of the possibilities in reserve, and weigh the other against a known standard marble:
If the scale is unequal, the marble that we weighed is the impostor, and if it is equal, the marble held in reserve is the impostor.
If the scale goes the other way, because of our grouping, we have a situation similar to what happens if the scale balances - we have 3 possible candidates, 2 of which are one direction and 1 which is the opposite.
If the scale is equal, none of the marbles on the scale are the impostor. We still have 3 candidates, 2 heavier and one lighter (or the opposite, depending on how we placed the groups earlier).
3 possible impostors, mixed directions
If we have 3 possible candidates, with 2 that might be heavier and one lighter, we can determine the impostor in one more move by measuring one heavy candidate and one light candidate together against 2 standard marbles, and holding the spare heavy candidate in reserve (same principle if we have 2 light and one heavy, just in reverse).
If the scale is imbalanced, the impostor is the possibility that matches the direction that it goes.
If the scale is balanced, the impostor is the marble that we held in reserve.