У вас есть рычажные весы и две гири весом 10 и 40 граммов. Разделите 1 килограмм муки на две части – 200 и 800 граммов – за три взвешивания.
Предположим, у нас есть набор килограммовых гирь, соответствующих первым шести членам последовательности удваивающихся чисел: 1, 2, 4, 8, 16, 32. Комбинируя эти шесть гирь, можно получить любой вес от 1 до 63 килограммов. Например:
3 = 2 + 1.
Другими словами, для того чтобы получить 3 килограмма, необходимо взять две гири весом 2 и 1 килограмм.
13 = 8 + 4 + 1;
27 = 16 + 8 + 2 + 1;
63 = 32 + 16 + 8 + 4 + 2 + 1.
В действительности шесть гирь образуют минимальный набор, позволяющий измерить любой вес в килограммах от 1 до 63.
Почему это так, можно понять, рассматривая выражение веса в двоичных числах. В двоичной системе счисления используются только цифры 1 и 0. Двоичные числа – это числа десятичной системы, записанные с помощью 1 и 0: 1, 10, 11, 100, 110 и т. д. Числа 1, 10, 100, 1000, 10 000 и 100 000 в двоичной системе счисления соответствуют десятичным числам 1, 2, 4, 8, 16 и 32. Таким образом, двоичные числа – это своего рода инструкции в отношении того, как выстраивать числа с помощью последовательности, в которой каждый очередной член в два раза больше предыдущего. Таким образом, в двоичной системе следующие числа записываются так:
3 – это 11
13 – 1101
27 – 11 011
63 – 111 111
Цифра 1 в крайнем правом столбце соответствует 1, цифра 1 в соседнем столбце – 2, цифра 1 в следующем столбце – 4 и т. д. Аналогичным образом цифра 0 в крайнем правом столбце означает отсутствие цифры 1, цифра 0 в соседнем столбце означает отсутствие цифры 2, цифра 0 в следующем столбце – отсутствие цифры 4 и т. д.
Итак, возьмем число 13, которое записывается в двоичной системе как 1101. Эта группа цифр справа налево означает: одна цифра 1, нет цифры 2, одна цифра 4 и одна цифра 8. Другими словами, 13 = 1 + 4 + 8 – как и было сказано.
Но давайте больше не будем отвлекаться на двоичные числа, какой бы интересной ни была эта тема. Вернемся к весам и гирям.
Поскольку наш набор гирь (1, 2, 4, 8, 16, 32) позволяет измерить любой вес в килограммах от 1 до 63, мы можем взвесить любое целое количество килограммов от 1 до 63, положив на одну из чаш весов соответствующую комбинацию гирь. А что, если использовать обе чаши?
62. ЗАДАЧА БАШЕ О ВЗВЕШИВАНИИ
У вас есть рычажные весы. С помощью какого минимального набора гирь можно измерить любой вес от 1 до 40 килограммов в целых числах, если гири можно класть на любую чашу?
Эта задача включена в книгу Леонардо Пизанского Liber Abaci («Книга абака», или «Трактат об арифметике»), хотя она более известна как задача о гирях французского математика Клода Гаспара Баше.
Баше был поэтом, переводчиком и математиком, а также автором сборника головоломок. В 1612 году он опубликовал первое издание книги Problèmes Plaisants et Délectables Qui Se Font Par Les Nombres («Занимательные и приятные числовые задачи»). В ней собраны многие из тех головоломок, с которыми вы здесь уже встречались, такие как переправа через реку, покупка сотни птиц и переливание жидкости в трех кувшинах. На протяжении трех столетий сборник Problèmes Plaisants считался стандартным текстом по занимательной математике, на нем основывалась вся последующая литература о головоломках. Кроме того, в книге Баше представлен самый известный анализ задачи с рычажными весами.
Баше внес еще один важнейший вклад в историю математики: перевел «Арифметику» древнегреческого математика Диофанта на латынь. Именно на одной из страниц этого перевода французский математик Пьер Ферма написал, что нашел чудесное доказательство теоремы, сформулированной под влиянием этого текста, но не может записать его, поскольку поля книги слишком узкие. Доказательство последней теоремы Ферма (уравнение an + bn = cn не имеет решений, выраженных в целых ненулевых числах a, b и c, если n больше 2) ускользало от математиков на протяжении 350 лет, что сделало ее за это время самой знаменитой нерешенной задачей в математике.
Вот вам задача для подготовки:
У вас есть восемь идентичных монет. Девятая монета фальшивая: она выглядит так же, но весит чуть меньше остальных монет. Сможете ли вы найти ее всего за два взвешивания?
Возможно, вы захотите решить эту задачу самостоятельно, в таком случае не читайте написанное далее. Я привожу здесь решение, чтобы вы смогли справиться со следующими головоломками.
Чтобы решить задачу о фальшивой монете, разделите монеты на три группы по три монеты. Если мы обозначим их номерами 1, 2, 3, 4, 5, 6, 7, 8 и 9, то первый раз взвешиваем монеты 1, 2, 3 и монеты 4, 5, 6. При этом чаши весов будут либо уравновешены, либо нет.
Если чаши весов уравновешены, как показано на рисунке слева, значит, более легкая монета – это номер 7, 8 или 9. Если одна чаша весов перевешивает другую, как на среднем рисунке, то более легкая монета – это номер 1, 2 или 3. Если же чаши весов расположены как на рисунке справа, значит, это монета номер 4, 5 или 6. Во всех трех случаях мы можем сузить вероятность поиска более легкой монеты с одной из девяти до одной из трех.
Теперь, при втором взвешивании, нам остается только сравнить вес одной из оставшихся монет с другой монетой, отложив третью в сторону. Более тяжелая монета перевесит чашу весов, а если чаши будут уравновешены, то фальшивая монета – та, что вы отложили. Вот и все.
Следующая задача стала широко известной во время Второй мировой войны. Она привела лучшие умы союзников в такое смятение, что кто-то даже предложил подкинуть фальшивую монету на вражескую территорию, чтобы вызвать хаос в мозговом центре немцев.
63. ФАЛЬШИВАЯ МОНЕТА
У вас есть 11 одинаковых монет. Двенадцатая монета – фальшивая. С виду она такая же, как все, но отличается весом. Вам неизвестно, легче она или тяжелее остальных.
Сможете ли вы за три взвешивания найти фальшивую монету и определить, легче она или тяжелее других монет?
Кстати, для весов с одной чашей (таких как современные цифровые весы, показывающие вес в килограммах) тоже можно придумать интересные головоломки с фальшивыми монетами.
