Solve the 12-coin balance puzzle

You are given 12 coins that look identical. One coin is counterfeit and may be either heavier or lighter than the rest, but you do not know which. You may use a balance scale with no weights, and you are allowed exactly three weighings. Give a weighing procedure that always finds the counterfeit coin and determines whether it is heavier or lighter. Lay out the complete decision tree: for every weighing, specify which coins are placed on each pan, and explain how the next weighing depends on the three possible outcomes (left pan heavy, right pan heavy, or balanced). Show that the strategy is correct and that three weighings are the minimum required.

Overview: This question tests combinatorial reasoning, information-theoretic thinking, and the ability to build a decision tree for finding one counterfeit coin and its weight direction under limited balance-scale observations.