This is a notoriously hard problem that comes in many flavors. I don't know where it comes from originally, but it garnered quite a bit of attention from mathematicians in the midtwentieth century. Apparently some versions of it may have even distracted scientists away from their defense research during WWII !
The problem was popular on both sides of the Atlantic during World War II; it was even suggested that it should be dropped over Germany in an attempt to sabotage their war effort... (Guy & Nowakowski 1995) Guy, Richard, and Richard Nowakowski. "CoinWeighing Problems," The American Mathematical Monthly Vol. 102, No. 2 (Feb. 1995). JSTOR link
Here's the version I set out to solve:
You have twelve coins, to appearance exactly identical; but possibly one is counterfeit (we'll call it a "dud"). You do not know if a dud is present, nor whether it is heavier or lighter than the good coins. Can you determine in three weighings on a balance scale: (1) whether there is a dud, (2) if so, which coin, and (3) its relative weight (lighter or heavier than the good coins)?
An additional detail:
 You can assume that the coins are distinguishable in a balance pan (or on the table).
This doesn't contradict the "exactly identical" condition in the problem statement, because you can group them in the pan or on the table spatially to distinguish them. This means that if you have grouped the coins into, say, two groups,
and , and you put some coins from each group into a single pan, you know which of those coins are from and which are from .
You can also find this puzzle (or some version of it) online as "The Twelve Balls problem." I made a point of not looking at any online solutions, but I did skim the Guy and Nowakowski paper cited aboveit does not have a solution, just some history and other details. Mostly, I used the observation that the coins are distinguishable in a balance pan. Without that allowance, I don't think the problem is solvable for twelve coins.
John Mount skimmed the format of other solutions (he swears he didn't read any of them); they tend to be structured as a long and tedious case tree. So in addition to finding a solution, he and I also came up with a somewhat more consise notation and presentation for the solution. It does shorten the description of the identification procedure somewhat. Hopefully, it also makes it easier to read.
Our solution is after the threecent nickel.
Our Solution #
To make the ultimate identification procedure (hopefully) easier to follow, we'll present our notation, and some useful transformation rules and lemmas before we get to the solution procedure.
Notation #
We will annotate the coins as follows:
: coin of unknown state : the coin is known to be a good coin : the coin is possibly a dud, and if so, is lighter than a good coin : the coin is possibly a dud, and if so, is heavier than a good coin
We'll count how many coins of a type we have with a superscript; so for example,
The goal is to end up in the state
We'll annotate a weighing as
[ Set_left  Set_right ]

Table
where Set_left
are the coins in the left pan, Set_right
in the right pan, and Table
what remains on the table.
Some transformation rules #
Transformation 1. is a terminal state #
Once you know a coin is good, it can never go bad.
Transformation 2. and can only go to , not to the opposite weight #
If a coin has been on the heavy side of the scale, then it must either be neutral (a good coin) or heavy. It cannot ever become light. Similarly for coins that have been on the light side of the scale.
As a corollary, if a coin marked
Transformation 3. Transformation on a balanced weighing #
[ X^L  X^R ]

X^T
balanced> X^L, X^R > G^{L+R}, table states unchanged
In other words, if the scale is balanced, everything on the scale is good, and the dud must be on the table.
Transformation 4. Transformation on an unbalanced weighing #
[ X^L  X^R ]

X^T
unbalanced> X^{T} > G^{T}, states on scale change depending
on coin location and previous state.
In other words, if the scale is unbalanced, then the dud must be on the scale, and everything on the table must be good. Everything on the heavy side of the scale is either
Some Useful Lemmas #
Lemma 1. and can be resolved in one weighing if a dud is known to be present. #
I'll do the
Weigh as
[L  L]

H
If the scale is balanced, then by transformation 3 this goes to
If the scale is unbalanced, then by transformation 4 the table becomes
Lemma 2. can be resolved in one weighing if a dud in known to be present. #
To make the argument simple, we'll again assume these are the only three coins in the world (any remaining coins are already G).
Weigh as
[H  G]

L
(or vice versa). If the scale balances, then
Lemma 3. can be resolved in one weighing. #
This is fairly obvious, but I'll state it. Again, we'll assume these are the only two coins in the world (any remaining coins are also already G). Weigh as:
[?  G]

If the scale is balanced, the last coin is
The Solution Procedure #
Let's assume for the moment that there is a dud. We'll do the "possibly no dud" case afterwards.
The initial state is
w1 = [?^4  ?^4]

?^4
There are two outcomes:
 The scale is balanced, which gives us
(the dud is on the table).  The scale is not balanced, which gives us
(the dud is on the scale).
If the scale is balanced on the first weighing #
Then we are in the state
w2 = [?^2  ? G]

? G^7
(put three of the remaining unknowns back on the scale, with one good coin).

If the scale is balanced, then everything on the scales is
, and we have . By Lemma 3, we can resolve this in one weighing for three total, and we are done. ✅ 
If the scale is not balanced then everything on the table is
, and we have either if the left side is lighter, or if the right side is lighter.
Either way, by Lemma 1 we can resolve this in one weighing for three total, and we are done. ✅
If the scale is not balanced on the first weighing #
Then we are in the state
w2 = [L^2 H  L H G]

L H^2 G^3
This is not obvious, and I confess we found it by trial and error. The key insights that lead to this are that (1) you can't resolve more than 3 coins in one weighing (so you can't have more than three unresolved coins on either side of the scale, or on the table); and (2) symmetric weighings don't give you enough information.

If the scale is balanced, then everything on the scales is
, and on the table you have . By Lemma 1 we can resolve this in one weighing for three total, and we are done. ✅ 
If the scale is not balanced then everything on the table is
, and on the scale we have either (by transformation 2) if the left side is lighter, or (by transformation 2) if the right side is lighter.
In the first case, Lemma 1 resolves it in one weighing; in the second case, Lemma 2 resolves it in one weighing. That's three total, and we are done. ✅
This resolves all cases when a dud is known to be present. But what about the case when a dud is not known to be present? If there is no dud, then the scale will always balance, and if you trace back through the above, you'll see there is only one path:
and by Lemma 3, that last state can be resolved in one weighing, whether or not there is a dud.
This resolves all cases, including the "no dud" case. We can identify the dud if it exists, and determine its relative weight. And we are done. ✅✅
Some Further Discussion #
After we finished our solution, we dug into some others. As referenced by Guy and Nowakowski, Freeman J. Dyson gave an "elegant" solution to the general problem (resolve
Dyson (and others) also show that twelve coins is the most that you can resolve in three weighings, under the conditions I gave in the problem statement. I suspect (though I don't see a proof for it, and I'm too lazy to prove it myself) that if we relax the problem to assume that there is a dud, and try to identify it, but not necessarily its weight, we can resolve up to thirteen coins in three weighings. Dyson does show that if you have one extra coin that is known to be good, you can resolve 13 unknown coins in three weighings (and determine the weight of a dud).
If you remove the accomodation that coins are distinguishable in the balance pan (meaning that once you dump a bunch of coins in the pan, you can't tell where any individual coin came from), the maximum number of coins you can resolve in three weighings appears to be ten (from a formula given by Guy and Nowakowski).