Измерения и информация

Заголовок получился многозначительным, но речь пойдет не о принципах квантовой механики, а о задачах на взвешивание и измерение.

Все, наверное, решали задачу про 12 монет:

Как за три взвешивания на обычных чашечных весах найти одну фальшивую (легче или тяжелее настоящей) монету из двенадцати?

Задача не тривиальная, но все же, немного подумав, решить можно. Сразу возникает вопрос: а нельзя ли увеличить общее количество монет? Оказывается, что можно до 13. А если есть эталонная, то и до 14. А из скольки монет можно найти фальшивую за четыре взвешивания, за пять?

Сформулируем задачу для любителей обобщений:

Из какого максимального количества монет и каким образом можно найти одну фальшивую за $n$ взвешиваний?

Задачу эту я узнал, на школе Ландау в Черноголовке в далеком 1997 году. На этой школе еще были интересные лекции про криптографию, например, нам рассказали как работает алгоритм шифрования с открытым ключом RSA . Но сейчас не об этом. Со мной был один товарищ, который предложил рекурсивный подход: сначала сгруппировать монеты в кучки, найти среди кучек фальшивую, а затем среди монет этой кучки найти фальшивую. Например, для $n=6$ взвешиваний можно взять аж $13\cdot 14=182$ монеты и сначала применить достижения первой задачи к 13 столбикам по 14 монет, а затем их же к монетам "фальшивого столбика". Хорошая идея, но я решал задачу совсем по-другому и у меня для $6$ взвешиваний получалось $364$ монеты. С тех пор я уже не раз порывался написать какую-нибудь популярную заметку об этой и других подобных задачах, но руки так и не дошли. Я также несколько раз задавал эту задачу коллегам/товарищам, но почему-то у них она не пошла.

Недавно я вспомнил эту историю потому что решал на сайте Diofant.ru другую задачу. Для тех, кому не хочется идти по ссылке, приведу условие:

Среди нескольких компьютерных чипов есть два поддельных, которые обладают повышенной радиоактивностью, а в остальном не отличаются от настоящих. В имеющийся прибор можно засунуть любое количество чипов и узнать, есть ли среди них радиоактивный (но нельзя понять, сколько именно — один или два). Каково максимальное число чипов, среди которых можно гарантировать обнаружение обоих поддельных за 7 проверок?

Опять же, в условии можно заменить 7 на $n$. А можно и два радиоактивных (при чем тут радиоактивность?) заменить на $m$.

Итак, те, кто все-же хотят решить задачу про монеты самостоятельно, должны воздержаться от чтения текста под чертой. А те кто будут читать — пусть не обвиняют меня в том, что я испортил им удовольствие.

---

Подсказка Подумайте о том, какое количество информации можно получить за одно взвешивание. Сколько неизвестной информации останется после этого в худшем случае? В этой задаче информацию лучше считать в трибитах (точнее, в тритах).

Скрипт:
Вот еще одна подсказка — рабочий скрипт:

Введите число взвешиваний

 

0		0

 

---

Ответ Максимальное число монет при отсутствии эталонной равно
\[N=\frac{3^n-1}2\]
Максимальное число монет при наличии эталонной равно
\[N=\frac{3^n+1}2\]

Первое взвешивание: $(3^{n-1}-1)/2$ на каждой чашке. Если есть эталонная, то $(3^{n-1}+1)/2$ на одной чашке и $(3^{n-1}-1)/2$ плюс эталонная — на другой. После $k$-ого взвешивания может быть три ситуации:

1. Фальшивая монета находится среди $(3^{n-k}+1)/2$ монет.
2. Фальшивая монета содержится в одной из двух стопок, причем легче она или тяжелее определятся тем, в какой именно стопке она находится. В стопках находится $(3^{n-k}+1)/2$ и $(3^{n-k}-1)/2$ монет (если нужно, можно добавить эталонную).

В зависимости от случая, делаем следующее:

1. В первом случае кладем из стопки под подозрением $(3^{n-k-1}+1)/2$ на одну чашу и $(3^{n-k-1}-1)/2$ плюс эталонная — на вторую. После взвешивания получаем случай 1 или случай 2.
2. Во втором случае на каждую чашу кладем из большей стопки по $(3^{n-k-1}+1)/2$ монет, а из меньшей — по $(3^{n-k-1}-1)/2$. После взвешивания получаем случай 2.

Очевидно, после $k=n$ взвешиваний оба случая однозначно определяют фальшивую.