Man stelle sich 12 identisch aussehende Würfel vor. 11 davon haben das gleiche Gewicht, der 12. ist minimal leichter oder schwerer, als die anderen.

Gesucht ist der Würfel mit dem abweichenden Gewicht und die Information, ob er schwerer oder leichter als die anderen Würfel ist.

Als einziges erlaubtes Hilfsmittel steht ausschließlich eine präzise Balkenwaage zur Verfügung, welche maximal 3 Mal benutzt werden darf.

Referenzgewichte gibt es keine - man kann mit der Waage nur Vergleiche anstellen.

Wie kann man mit der Waage mit maximal 3 Messungen eindeutig den abweichenden Würfel bestimmen und feststellen, ob er leichter oder schwerer als die anderen ist?

edit: Ich bin noch keinem Menschen begegnet, der diese Aufgabe lösen konnte, ohne sich alle möglichen Ereignisbäume aufzuzeichnen...

edit2: Diese Aufgabe wurde einem Bekannten auch bei einem Jobinterview von Google vorgelegt. Er war gut vorbereitet.