Обобщённая задача о фальшивых монетах

27

М. Мамикон

Обобщенная задача о фальшивых монетах

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

Задача о мешке с фальшивыми монетами

Имеются N мешков и в каждом из них достаточно количество монет. Все мешки, кроме одного, содержат одинаковые «normальные» монеты, в одном же мешке все монеты фальшивые. Известен все нормальной монеты и известно, что фальшивая монета на 1 грамм легко нормаль-ной. Требуется при помощи одного взвешивания на весах с разновесками обнаружить мешок с фальшивыми монетами.

Вот как решается эта задача. Мешки последовательно numерюются и из каждой мешка берется количество монет, равное номеру этого мешка. Суммарный вес всех взятых таким образом монет будет «не дотягивать» до веса такого же количество нормальных монет (которые нам известен) на количество граммов, равное номеру именно того мешка, который содержит фальшивые монеты*).

Раздувавая над этой задачей, я пришел к более удивительному выводу о том, что одним взвешиванием может быть решение и более сложная задача:

*) Эта задача решается — правда, хитрее — и в том случае, когда все нормальной монеты неизвестен и разновесков нет. Подумайте, как.

28

Задача о нескольких мешках с фальшивыми монетами

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

Решив и эту задачу, я осмелился на дальнейшие условия. Задача оказалась разрешимой при еще более удивительных условиях:

Задача о мешках
с тяжелыми и легкими монетами
Среди N мешков имеются неотрое (неизвестное) количество мешков с тяжелыми и неотрое (то же неизвестное) количество мешков с легкими монетами. Леская монета на 1 глече нормальной, а тяжелая, наоборот, на 1 глече нормальной. Требуется при помощи одного взвеси ваня на весах с разновесами узнать, какие мешки содержат нормальные монеты, какие — тяжелые, а какие — легкие. (Напомним, что внутри данного мешка все монеты одинакового веса и что все нормальной монеты известен.)

Разрешимость и этой задачи входновила меня на дальнейшее обобщение, которое уже направалось само собой. До сих пор мы фактически рассматривали задачи о двух или трех сортах (типах) монет, поэтому естественно следует

Задача о мешках
с разновостями монетами

Пусть имеется N мешков и в каждом достаточно колисего монет. Имеются монеты разных сортов, но в каждом мешке содержатся монеты только одного сорта. Колисего мешков с монетами данного сорта произвольное, и нам оно неизвестно. Монеты разных сортов отличия друг от друга по весу, причем на целое число граммов. Все монеты каждого сорта изменен. Требуется при помощи одного взвеси ваня на весах с раз-

новесами определить, к какому сорту приадлежат монеты в каждом мешке.

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

Решение задачи о мешках
с разновостями монетами

Перенумеруем последовательно мешки от 0 до N—1. Обозначим все самой легкой монеты через m. Пусть мешок под номером j содержит монеты веса m+Δj, то есть Δj определяет сорт монеты в j-м мешке. Пусть в зависимости от сорта монеты величины Δ могут принимать (целые) значения 0, 1, 2,…, меньше k, то есть колисего сортов монет равно k.

Теперь возьмем из мешка с номером j колисего монет, равное kj, то есть из первого мешка — одну монету, из второго — k,…, из последнего — kN−1 монет. Всего взязывах монет будет

$$M = \sum_{j=0}^{N-1} k^j = 1 + k + k^2 + \dots + k^{N-1} = \frac{k^N - 1}{k - 1}.$$

Их суммарный вес S на весах будет равен

$$S = \sum_{j=0}^{N-1} (m + \Delta_j) k_j = m \sum_{j=0}^{N-1} k^j + \sum_{j=0}^{N-1} \Delta_j k^j = m \cdot M + \sum_{j=0}^{N-1} \Delta_j k^j.$$

Поскольку всегда Δj < k, вторая сумма в правой части

$$\Delta = \sum_{j=0}^{N-1} \Delta_j k^j = \Delta_0 + \Delta_1 k + \Delta_2 k^2 + \dots + \Delta_{N-1} k^N - 1$$

представляет собой перевод числа Δ из десятичной системы численения (в котором работает весы) в системе численения с основанием, равным k. В этой системе Δ записьается в виде числа со следующей последо-