Есть 12 монет и чашечные весы. Одна монета фальшивая и отличается по массе. Как за три взвешивания определить монету и легче она или тяжелее.
Разбиваем на три кучки по четыре и номеруем кучки X, Y, Z. Переберём все возможные варианты первым взвешиванием:
[1] X > Y (Z подлинные)
[1] X < Y (Z подлинные)
[1] X = Y (X, Y подлинные)
Заново переименуем кучки, и получим такие варианты.
[1] X > Y (Z подлинные)
[1] X = Y (X, Y подлинные)
Решаем лёгкий случай.
[1] X = Y (X, Y подлинные)
[2] X1, Z1 > Z2, Z3 (Z4 подлинная)
[3] Z2 = Z3 (Z1 фальшивка и она тяжелее)
[3] Z2 > Z3 (Z3 фальшивка и она легче)
[3] Z2 < Z3 (Z2 фальшивка и она легче)
[2] X1, Z1 = Z2, Z3 (Z4 фальшивая)
[3] X1 > Z4 : Z4 фальшивка и она легче
[3] X1 < Z4 : Z4 фальшивка и она тяжелее
Решаем тяжёлый случай.
[1] X > Y (Z подлинные)
[2] Y1, Z2, X3 = X1, Y2, Y3 (X2, X4, Y4 фальшивые)
[3] X2 = X4 (Y4 фальшивая и она легче)
[3] X2 > X4 (X2 фальшивая и она тяжелее)
[3] X2 < X4 (X4 фальшивая и она тяжелее)
[2] Y1, Z2, X3 > X1, Y2, Y3 (X3, Y2, Y3 фальшивые) (X3, Y2, Y3)
[3] Y2 = Y3 (X3 фальшивая и она тяжелее)
[3] Y2 > Y3 (Y3 фальшивая и она легче)
[3] Y2 < Y3 (Y2 фальшивая и она легче)
[2] Y1, Z2, X3 < X1, Y2, Y3 (X1, X3, Y1 фальшивые) (X1, Y1)
[3] Z1 = X1 (Y1 фальшивая и она легче)
[3] Z1 < X1 (X1 фальшивая и она легче)
Если не узнавать, тяжелее или легче монета, то задача решается с 13ю монетами.