Из иностранного юмора

29

вательность цифр:
$$\Delta \rightarrow \Delta_{N-1} \Delta_{N-2} \dots \Delta_{2} \Delta_{1} \Delta_{0}.$$

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

Итак, из суммарного веса S всех выбранных M монет вычитаем величины Mm — вес того же количества монет наилегчайшего сорта и оставшееся число $\Delta = S - Mm$ переводим в систему счисления с основанием $k$ (разлагаем по степеням $k$, начная со стартей). Тогда мы получим число вида (*). Его $j$-я цифра с конца (счет ведется от нуля) показывает сорт монеты $\Delta_j$ в мешке под номером $j$.

Пример

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

| номер мешка $j$ | 4 | 3 | 2 | 1 | 0 |
| :— | :— | :— | :— | :— | :— |
| $11\text{ r}$ | $12\text{ r}$ | $10\text{ r}$ | $12\text{ r}$ | $10\text{ r}$ | $10\text{ r}$ |
| $1$ | $2$ | $0$ | $2$ | $0$ | $0$ |
| $81$ | $27$ | $9$ | $3$ | $1$ | $1$ |

В этом случае $k=3$ и количество взятых монет соответствует степеней, как показано в последней строке таблицы. Все мы взяли $M=121$ монету. Их общий вес на весах будет равен $S=1351$ г. Вычитая величины $M \cdot m=121 \cdot 10$, получим $\Delta=141$ г. Переводя $\Delta$ в троичную систему
$$\Delta = 1 \cdot 3^4 + 2 \cdot 3^3 + 0 \cdot 3^2 + 2 \cdot 3^1 + +0 \cdot 3^2,$$
получим число $\overline{12020}$, последовательность цифра которого совпадает с исходной последовательностью сортов, приведенной в таблице.

Если $k=10$, то надоность перевода $\Delta$ из одной системы счисления в другую отпадает. Для случая $k=3$ существует несколько отличия от нашей интерпретации решения задачи. Найти ее мы предоставляем читателю.

Немного истории

Классический задачу об одном мешке с фальшивыми монетами можно найти во многих популяриных книжках по математике. Говорят, что во время второй мировой войны английане «сбросили» эту задачу над немецкими солдатами с целью их dezорганизации и что те потеряли над ее решением более 40 000 человек-часов.

В книге Д. Бизама и Я. Герцега «Многосветная логика» (М., «Мир», 1978 г.) рассматривается также случай двух мешков с фальшивыми монетами и приводится решение этой задачи при помощи двух взвешивания.

Классический задача о фальшивых монетах в последнее время нашла применение в теории кодирования и информации — для обнаружения ошибки в коде.

ИЗ ИНОСТРАННОГО ЮМОРА

Кто из студентов здоровался со мной за руку
«Альфа» 77 — № 3