I got this problem from Rustan Leino, who got it from Ernie Cohen. He'd also heard it from a student who got it from Ernie at Marktoberdorf.
I solved it and wrote up my solution.
You have 12 coins, 11 of which are the same weight and one counterfeit coin which has a different weight from the others. You have a balance that in each weighing tells you whether the two sides are of equal weight, or which side weighs more. How many weighings do you need to determine which is the counterfeit coin, and whether it weighs more or less than the other coins? How can you determine these in that number of weighings?
There's a procedure that does it in at most three weighings, which we'll describe below. This is the optimal number of weighings by the following reasoning. Each weighing can produce only three different results: "the left side weighs more", "the left side weighs less", or "both sides balance". So, two weighings can only produce nine different results. You have to distinguish between 24 different results, so two weighings aren't sufficient.
We define the parity as $\cal L$ if the counterfeit weighs less than the other coins, and $\cal M$ if the counterfeit weighs more than the other coins. We say a procedure succeeds if it identifies the counterfeit and finds the parity. We build up a successful procedure for 12 coins by starting with some useful subroutines.
Subroutine 1 (uses one weighing). You can use this subroutine to succeed if you've narrowed down the counterfeit to three coins and you know the parity.
Put two of the potential counterfeits on the balance, one on each side. If they have equal weight, the remaining third potential counterfeit is the counterfeit. Otherwise, the counterfeit is the one that weighs less if the parity is ${\cal L},$ and the one that weighs more if the parity is ${\cal M}.$
Subroutine 2 (uses one weighing). You can use this subroutine to succeed if you know which coin is counterfeit but don't know the parity.
Put the counterfeit coin on the left side of the balance and a different coin on the right side. Conclude that the parity is $\cal L$ if the left side weighs less, and $\cal M$ if the left side weighs more.
Subroutine 3 (uses two weighings). You can use this subroutine to succeed once you've narrowed down the counterfeit to four coins but don't know the parity.
Put three of the potential counterfeits on the left side of the balance; put three of the coins known not to be counterfeits on the right side. If the sides have equal weight, then the remaining fourth potential counterfeit is the counterfeit; use subroutine 2 to finish. If the left side weighs less, then one of those three coins is the counterfeit and the parity is ${\cal L};$ use subroutine 1 to finish. If the left side weighs more, then one of those three coins is the counterfeit and the parity is ${\cal M};$ use subroutine 1 to finish.
Solution procedure (uses three weighings).
Put four of the coins on the left side of the balance and four on the right side. If the sides weigh the same, the counterfeit is among the remaining four coins; use subroutine 3 to finish. If the sides don't balance, assign the coins on the side that weighs less the names $L_1, L_2, L_3, L_4;$ assign the coins on the side that weighs more the names $M_1, M_2, M_3, M_4;$ and assign the remaining known-good coins the names $K_1, K_2, K_3, K_4.$ Then continue as discussed in the next paragraph.
For the second weighing, put $L_1, L_2, L_3, M_4$ on the left side of the balance and $K_1, K_2, K_3, L_4$ on the right side of the balance. If the sides have equal weight, the counterfeit must be among the potential counterfeits you didn't use. This means that the counterfeit must be among $M_1, M_2, M_3$ and the parity must be ${\cal M};$ use subroutine 1 to finish. If the left side weighs less, the counterfeit must be among $L_1, L_2, L_3$ and the parity must be ${\cal L};$ use subroutine 1 to finish. Finally, if the left side weighs more, the counterfeit must be either $L_4$ or $M_4.$ Perform a final weighing between $M_4$ and $K_4.$ If $M_4$ weighs more than $K_4$, $M_4$ is the counterfeit and the parity is ${\cal M};$ otherwise, $L_4$ is the counterfeit and the parity is ${\cal L}.$