Задача о взвешивании
Вот одна из классических задач, решить которую можно сразу же, если
выбрать систему счисления с подходящим основанием. Эта задача приведена
в математической книге знаменитого математика XIII в. Леонардо Пизанского.
Ею интересовался также в XVIII в. и Л. Эйлер.
Требуется выбрать 5 гирь так, чтобы с их помощью можно было взвесить
(с точностью до 1 кг) любой груз до 30 кг при условии, что гири ставятся
только на одну чашу весов и масса гирь различна. Какие же гири нужно
выбрать?
Сумма масс всех гирь должна быть не меньше 30 кг. Но, конечно, этого
недостаточно. Если мы выберем, например, гири в 1, 2, 3, 10и 15 кг, то
с их помощью нельзя будет взвесить грузы в 7, 8, 9, 22, 23 и 24 кг.
Разберем математический смысл задачи. Чтобы взвесить' некоторый груз,
помещая гири только на одну чашу весов, надо представить его массу в виде
суммы масс имеющихся гирь, причем так, чтобы каждая гиря бралась не более
одного раза. Если выбранные нами гири имеют массу т1, т2,
m3, т4, т5, то груз массой
М=<30 кг должен представляться так:
где каждый коэффициент равен единице, если кладем соответствующую гирю
на чашу весов, и нулю, если не пользуемся ею при взвешивании.
При такой постановке вопроса видно сходство с представлением числа М
в двоичной системе счисления. Нужно только в качестве т1,
т2, т3, m4, m5
взять гири массой: т1 = 1 кг, m2=2 кг, m3
= 4 кг, m4 = 8 кг, m5 = 16 кг. Сумма их масс
1 + 2 + 4,+ 8 + 16 = 31 кг. Кроме того, каждое число М, не большее
31, можно представить в виде:
где каждый из коэффициентов b0, b1, b2,
b3, b4 будет, как нам и нужно, либо нулем, либо
единицей.
Пусть, например, надо взвесить груз в 22 кг. Запишем число 22 по двоичной
системе: 22=101102.
Значит, нужно взять гири m2 = 2 кг, m3 = 4 кг
и m5 = 16 кг.
Теперь несколько видоизменим задачу: пусть требуется выбрать 4 гири,
с помощью которых можно было бы взвесить любой груз до 40 кг, при условии,
что гири можно класть и на левую и на правую чашу весов.
Нетрудно убедиться, что для решения этой задачи можно воспользоваться
троичной системой счисления, выбрав следующие 4 гири: m1
- 1 кг, m2 = 3 кг, m3 = 9 кг, m4 = 27
кг. Нужно только заметить, что двойной вес гирь т1, m2,
m3 можно заменять разностью двух разных гирь, например:
2m2 = m3 - m2, m3 = m4
- т3 и т. п.
Следует помнить, что, хотя в различных системах счисления числа записываются
по-разному, основные свойства их от этого не меняются: так, число 20 будет
делиться на 2, в какой бы системе мы его ни записали, а 27 не разделится
на 2, но будет делиться на 3. Числа 3, 5, 7 останутся простыми в любых
системах счисления. Однако признаки делимости, которые устанавливаются
исходя из записи числа в определенной системе счисления, будут меняться
вместе с основанием системы. Так, число делится на 5, если его запись в
десятичной позиционной системе оканчивается нулем или пятеркой. Но число
не всегда делится на 5, если на 0 оканчивается его запись в троичной системе,
например, числа 103 (т. е. 3), 1003 (т. е. 9), 10003
(т. е. 27) не делятся на 5, а число 1203 (т. е. 15) будет делиться
на 5.
|