Решение задачи “Мешки с фальшивыми монетами”

Уважаемые читатели!

У газеты-вкладки “В мир информатики” появился свой электронный адрес: vmi@1september.ru.

Эта задача была опубликована в 119-м номере нашей газеты (“Информатика” № 1/2009). Напомним условие.

Имеются 6 мешков с монетами. В некоторых из них все монеты фальшивые (они на 1 грамм легче настоящих). За одно взвешивание на чашечных весах, имеющих указатель разности весов на чашках, определить, в каких мешках монеты фальшивые, если известно, что фальшивые монеты не во всех мешках.

Решение

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

1m₁ + 2m₂ + 4m₃ + 8m₄ + 16m₅                                           (1)

и на правой: 31m₆,

где m₁, m₂, …, m₆ — вес одной монеты соответственно из первого, второго, …, шестого мешка.

Если бы фальшивых монет не было ни в одном из мешков, то весы были бы в равновесии (указатель разности весов на чашках показывал бы — 0).

Если перевесила правая чашка, то на ней фальшивых монет нет. А в каких мешках они?

Если бы фальшивые монеты были бы, например, во втором мешке, то указатель показывал бы значение 2, если в третьем — значение 4, если во втором и третьем — значение 6 (2 + 4) и т.п.

Далее обратим внимание на то, что формула (1) похожа на так называемую “развернутую” форму записи числа в двоичной системе счисления², а значения указателя соответствуют весомости того разряда записи, где фигурирует вес фальшивых монет. Для анализа составим табличку:

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

А если перевесила левая чашка весов? Как найти номера мешков с фальшивыми монетами по разности весов на чашках в этом случае? Ответ на этот вопрос предлагаем найти читателям.

---

² Развернутой записью, например, десятичного числа 2063 является 2 · 1000 + 0 · 100 + 6 · 10 + 3 · 1, или 2 · 10³ + 0 · 10² + 6 · 10¹ +
+ 3 · 10⁰; числа 110110, записанного в двоичной системе счисления, — 1 · 2⁵ + 1 · 2⁴ + 0 · 2³ + 1 · 2² + 1 · 2¹ +
+ 0 · 2⁰, или в десятичном виде: 1 · 32 + 1 · 16⁴ + 0 · 8 +
+ 1 · 4 + 1 · 2 + 0 · 1.