Задача с монетами.
Задача есть в двух вариантах:

A. Среди 12-ти монет может быть одна фальшивая, отличающаяся от остальных по весу. Требуется найти её за три взвешивания на чашечных весах и сказать, легче она или тяжелее; либо определить её отсутствие.

B. Среди 13-ти монет есть одна фальшивая, отличающаяся от остальных по весу. Требуется найти её за три взвешивания на чашечных весах.

Самое популярное решение имеет удобную мнемонику: обозначив 12 монет буквами FAKE MIND CLOT, провести три взвешивания по такой схеме: MA DO — LIKE, ME TO — FIND, FAKE — COIN.

Таким образом можно определить, есть ли подделка среди 12-ти монет, и в какую сторону она отличается по весу. Если среди 12-ти подделки нет, то о массе 13-й уже ничего не сказать.

Указанное решение интересно тем, что взвешивания в нём однозначны и независимы; их можно проводить в любом порядке. Однако, составляя «программу» взвешиваний поэтапно, с учётом промежуточных результатов, лучшего результата всё равно не добиться.

За k взвешиваний можно решить задачу A не более чем для (3^k — 3) / 2 монет. То есть, 12 за три взвешивания. Соответственно, 13 в задаче B.

Имея лишнюю заведомо нефальшивую монету, можно снизить оценку до (3^k-1) / 2, и решить задачу B для 14 монет за те же три взвешивания.

Оба неравенства доказаны по индукции.