Задача 2.8. Есть 27 монет, часть из них серебряные, остальные — медные. Известно, что одна из них фальшивая, остальные настоящие. Настоящие серебряные монеты отличаются по весу от настоящих медных, а фальшивая монетка легче настоящей монеты из того же металла. Как найти фальшивую монету за 3 взвешивания?

Обозначим три взвешивания координатами $1,2,3$. Каждой монете заранее сопоставим тройку символов из $\{+,0,-\}$. Символ означает:

• $+$ — монета кладётся на левую чашу;

• $-$ — на правую;

• $0$ — в этом взвешивании не участвует.

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

Используем все $27$ троек из $\{+,0,-\}^3$. Их удобно разбить на следующие «блоки»:

Знак $\pm(a,b,c)$ означает две тройки:

В каждом блоке по каждой координате число плюсов равно числу минусов. Например, в блоке $A_3$ по первой координате стоят $1,0,-1$, по второй — $0,1,-1$, по третьей — $-1,1,0$.

Теперь пусть серебряных монет $s$. Числа размеров блоков

позволяют составить любое число от $0$ до $27$. Поэтому выбираем несколько блоков, суммарный размер которых равен $s$, и размещаем серебряные монеты в клетках выбранных блоков. Все остальные клетки занимаем медными монетами.

Например:

значит, при $13$ серебряных монетах можно отдать серебру блоки $A_6,A_5,A_2$, а остальные клетки — меди.

После этого проводим три взвешивания:

1. В первом взвешивании на левую чашу кладём все монеты, у которых первая координата $+$, на правую — с первой координатой $-$.

2. Во втором — аналогично по второй координате.

3. В третьем — по третьей.

Поскольку на обеих чашах каждый раз одинаковое число серебряных и одинаковое число медных монет, настоящие монеты дают точное равновесие.

Записываем результат каждого взвешивания так:

• левая чаша легче — ставим $+$;

• равновесие — ставим $0$;

• правая чаша легче — ставим $-$.

Полученная тройка и есть код фальшивой монеты. Например, результаты

означают, что фальшивая монета — та, которой был присвоен код $(+,0,-)$.

Таким образом, за три взвешивания однозначно определяется одна монета из $27$.