Наши недавний набор головоломок были представлены скромные весы с двумя чашами, которые исторически были символом торговли и правительства, искусства и науки. Весы баланса также популярны в развлекательной математике. Головоломки с балансом требуют четких логических рассуждений и хорошо поддаются математическому обобщению. посмотрим как Quanta читатели уравновесили эти качества в головоломках ниже.
Головоломка 1
У вас есть восемь одинаковых на вид монет. Одна фальшивая и легче остальных, имеющих одинаковый вес. Найдите плохую монету за два взвешивания. Найдите общую формулу максимального количества монет, при котором можно найти фальшивую в x взвешивания.
Решение простой версии проблемы часто открывает ключ к решению. В этом случае представьте, что у вас есть всего три монеты, одна из которых легче двух других. Если вы сопоставите любой из них с одним из двух других, они либо уравновесятся, либо нет. Если нет, вы знаете, что легче. Если они балансируют, то третий — светлый. Вам нужно только одно взвешивание.
Таким образом, в этой головоломке, если вы можете изолировать группу из трех (или меньше), содержащих легкую монету при первом взвешивании, вам потребуется еще одно взвешивание. Вы можете сделать это, уравновешивая любые три против любых других трех. Если две группы не сбалансированы, вы нашли группу, содержащую легкую, и можете действовать, как описано выше, для второго взвешивания. Если они уравновесятся, просто взвесьте оставшиеся две монеты друг против друга, и вы найдете более легкую.
Обратите внимание, что это также работает, если в невзвешенной группе три монеты, поэтому мы могли бы начать с девяти монет. Следуя этой логике и начиная с трех монет, при каждом дополнительном взвешивании мы можем найти легкую монету в количестве, в три раза превышающем количество монет, которое у нас было ранее. Формула, дающая нам максимальное количество монет n in w взвешивания. поэтому n = 3w.
Головоломка 2
У вас есть 12 одинаковых на вид монет. Один из них либо тяжелее, либо легче остальных, имеющих одинаковый вес.
-
Найдите плохую монету за три взвешивания.
-
При каком максимальном количестве монет можно найти плохую за четыре взвешивания? Опишите, как бы вы нашли фальшивую монету.
Решение этой загадки хорошо описал Тед, который также показал, что вы можете обнаружить плохую монету среди 13 монет за три взвешивания. Вот решение Теда (с отступами для разделения трех взвешиваний в каждом случае):
Начните со взвешивания 4 монет против 4 монет.
Случай 1: В случае дисбаланса при втором взвешивании положите по 2 веса более тяжелой стороны на обе стороны весов, а также по 1 весу на более легкую сторону.
1a: В случае несбалансированности плохой монетой являются либо 2 монеты, все еще находящиеся на тяжелой стороне, либо единственная монета, все еще на светлой стороне.
Взвесьте 2 возможные тяжелые монеты, плохой является либо более тяжелой из двух, либо единственной легкой, если они уравновешены.
1b: Если второе взвешивание уравновешено, плохой монетой является одна из 2 неиспользованных монет с более легкой стороны первого взвешивания.
Сравните их друг с другом, более легкий - плохой.
Случай 2: При балансировке плохая монета — одна из 5 оставшихся. Взвесьте 3 из них против любых 3 уже взвешенных (которые, как известно, хороши).
Случай 2a: Если вы не сбалансированы, вы знаете, что плохая монета — одна из этих 3, и независимо от того, легкая она или тяжелая.
Третье взвешивание - это любые 2 из них друг против друга - если они не сбалансированы, это идентифицирует плохую монету, если сбалансировано, это последняя из трех.
Случай 2b: если второе взвешивание уравновешивается, плохой монетой является одна из оставшихся 2.
Взвесьте любой из них против заведомо хорошей монеты. Если этот результат несбалансирован, эта новая монета плохая, и вы знаете, тяжелая она или легкая. Если этот результат уравновешен, 13-я монета плохая, но неизвестно, тяжелая она или легкая (что нам не нужно знать, так что мы закончили).
Тед также показал, что максимальное количество монет для четырех взвешиваний равно 40. Формула для этой головоломки: n = (3w − 1)/2.
Для остальных головоломок обобщенные формулы все еще исследуются профессиональными математиками и являются предметом опубликованных статей, некоторые из которых были процитированы Райнер из весны. Я ограничусь решениями для небольшого числа монет, которые мы рассматриваем в задачах, и упомяну только об обобщениях, которые естественным образом вытекают из используемых в этих случаях методов.
Головоломка 3
Это вариант головоломки 1. У вас снова есть восемь одинаковых на вид монет, одна из которых светлее других. Однако теперь у вас есть три шкалы. Две шкалы работают, а третья сломана и дает случайные результаты (иногда правильные, иногда неправильные). Вы не знаете, какая шкала сломана. Сколько взвешиваний потребуется, чтобы найти легкую монету?
Как мы видели в задаче 1, для этого требуется всего два взвешивания с хорошими весами. Мы также знаем, что два хороших весов всегда будут совпадать, поэтому, если мы просто повторим каждое взвешивание на всех трех весах, мы получим ответ за шесть взвешиваний, как предложил читатель. Если мы попытаемся сделать это за меньшее количество взвешиваний, это станет немного сложнее. Мы не можем определить хорошие весы, просто взвешивая одни и те же монеты на двух весах, потому что, даже если они совпадут, любая из них может быть плохой. (Это также показывает, как легко дезинформация или случайная информация могут скрыть правду.)
На самом деле, эту задачу можно решить, очень умно, всего за четыре взвешивания! Райнер из весны опубликовал решение, используя новомодную нотацию, которая, кажется, была создана для этой головоломки. Но прежде чем вы отправитесь туда, я хочу, чтобы вы представили сценарий, который, я надеюсь, сделает все более интуитивным.
Представьте, что вы детектив, расследующий наезд и побег в крошечной стране, чьи автомобили имеют двузначные номерные знаки, используя только цифры 0, 1 и 2. Три человека, A, B и C, наблюдали за инцидентом. Двое из них всегда правильно отвечают на вопрос с тремя вариантами ответов, а один дает совершенно случайные ответы. Вы не знаете, кто является случайным ответчиком. Вы должны задать каждому из них один вопрос с тремя вариантами ответов, а затем выбрать того, кто определенно говорит правду, чтобы получить больше информации.
Вот как вы это делаете. Спросите А, является ли первая цифра 0, 1 или 2. Допустим, А говорит 2. Спросите Б, является ли вторая цифра 0, 1 или 2. Допустим, В говорит 1. Затем попросите С сделать выбор между этими тремя утверждениями:
- Только А говорит правду.
- Только Б говорит правду.
- Оба говорят правду.
Вы можете поверить тому, что вам говорит С, и расспросить этого человека о другой цифре. Чтобы понять почему, представим, что если А лжет, то С надежен и скажет, что Б говорит правду. Вторая цифра на самом деле будет 1, и тогда вы можете задать вопрос Б о первой цифре. Точно так же, если B лжет, то C снова надежен и скажет, что A говорит правду. Тогда первая цифра на самом деле 2, и вы можете спросить А о второй цифре. Наконец, если C лжет, то и A, и B надежны, поэтому вы все равно можете поверить и выбрать того, кому C скажет. (И если С говорит, что и А, и В говорят правду, то они оба должны быть правы.) Ключевым моментом здесь является то, что ваш выбор вопросов не позволяет С лгать таким образом, чтобы поставить под сомнение и А, и В. Поскольку по крайней мере один из ответов A и B должен быть надежным, вы всегда можете выбрать тот, с которым согласен C, даже если это просто случайный ответ. Если все трое согласны, то у вас уже есть обе цифры номерного знака.
Вот как перевести эту сказку обратно в нашу головоломку. Шкалы A, B и C. Вы можете перевести две цифры номерного знака на монеты следующим образом: 01 — монета 1, 02 — монета 2, 10 — монета 3, 11 — монета 4, 12 — монета 5, 20 — это монета 6, 21 — это монета 7, а 22 — это монета 8. Проницательные читатели поймут, что это система счисления с основанием 3 (или троичная). Также обратите внимание, что есть дополнительный возможный номер 00, который вы можете использовать для девятой монеты, для которой этот метод также будет работать, как в головоломке 1.
Для первого взвешивания вы делите монеты на их первую (по основанию 3) цифру, поэтому ваши три группы будут монетами [1, 2], [3, 4, 5] и [6, 7, 8]. Взвесьте [3, 4, 5] против [6, 7, 8] на весах A. Если A работает хорошо, у вас будет правильная первая группа цифр, как в задаче 1. Аналогично, для второго взвешивания на весах B ваши группы будут те, у которых одна и та же вторая цифра: [1, 4, 7], [2, 5, 8] и [3, 6]. Если B работает хорошо, у вас будет правильная вторая цифра. Для третьего взвешивания на весах С вы взвешиваете группу, которую определил А, против группы, которую сделал В. Следуя нашему примеру, для 21 группы будут [6, 7, 8] и [1, 4, 7]. Монету 7 нельзя положить обеими сторонами одновременно, поэтому мы опускаем ее и взвешиваем [6, 8] и [1, 4] друг против друга. Обратите внимание, что если A и B оба надежны, то 7 на самом деле является правильным ответом, и не имеет значения, какая сторона окажется легче на C. Если случайно взвешивание на C уравновешено, то все три весы совпадают, и у вас есть ответ (монета 7) всего за три взвешивания. Если А надежен, а В нет, то более светлая монета находится в [6, 8], что подтвердит шкала С, а если В надежна, а А нет, то более легкая монета находится в [1, 4], какую шкалу С также подтвердит.
Таким образом, за три взвешивания мы либо определили легкую монету, либо сузили ее до группы из двух, а также определили рабочие весы. Четвертое взвешивание либо на весах А, либо на весах В (в зависимости от того, с какими весами согласится С) сделает все остальное.
Это решение кажется мне удивительно красивым!
Этот метод можно обобщить, чтобы найти легкую монету среди 32x монеты в 3x + 1 взвешивание с данным комплектом весов. Таким образом, вам потребуется семь взвешиваний для 81 монеты. Для большего количества монет (> ~ 1,000) более надежное решение существует.
Головоломка 4
У вас есть 16 монет, восемь из которых тяжелые и одного веса. Остальные восемь легкие и такого же веса. Вы не знаете, какие монеты тяжелые или легкие. Монеты выглядят одинаково, за исключением одной со специальной маркировкой. С одними хорошими весами сможете ли вы определить, легкая или тяжелая особая монета, за три взвешивания? С каким максимальным количеством монет можно начать и успешно решить эту задачу за четыре взвешивания?
На первый взгляд кажется, что решить эту головоломку за три взвешивания почти невозможно, как заключил один из наших читателей. Тем не менее, при некоторой хитрости это можно сделать, и оба Тед и Райнер из весны дали правильные решения. Тед предложил несколько бесценных общих принципов, на которые стоит обратить внимание.
Во-первых, пока вы не получите несбалансированный результат взвешивания, у вас не будет достаточно информации, чтобы определить, тяжелая или легкая особая монета. Таким образом, вы должны попытаться добиться несбалансированного результата.
Во-вторых, если вы получаете сбалансированный результат (скажем, специальная монета A уравновешивает монету B), вы можете объединить сбалансированные монеты и взвесить их с еще двумя монетами, C и D. Если они не сбалансированы, у вас есть ответ; в противном случае вы удвоили количество одинаковых монет, что может помочь вам получить несбалансированный ответ при следующем взвешивании. Вы также можете выполнить этот процесс в обратном порядке с количеством монет, которое является степенью двойки (4, 8 и т. д.), если у вас есть начальный несбалансированный результат, как показано в следующем решении.
Ниже представлена вся процедура, позволяющая определить тип специальной монеты А во всех случаях за три взвешивания. (B, C и D — три монеты, лежащие на той же стороне, что и A, весом 1 (W1); X и Y — две монеты, не используемые в W1.)
Эту головоломку придумал русский математик Константин Кноп, мировой авторитет в области головоломок для взвешивания монет. Многие из его статей на русском языке, но вы можете найти несколько головоломок с монетами (среди других интересных головоломок) на Блог его соратницы Тани Ховановой.
Что касается обобщения, я оставлю вам посмотреть, работает ли этот же метод для определения типа специальной монеты среди 32 монет, из которых 16 тяжелых и 16 легких.
Головоломка 5
У тебя есть n одинаковые на вид монеты, некоторые из которых фальшивые и легче других. Все, что вы знаете, это то, что существует по крайней мере одна фальшивая монета и что нормальных монет больше, чем поддельных. Ваша задача - обнаружить все фальшивые монеты.
Тот факт, что есть по крайней мере одна светлая монета и что обычных монет больше, чем светлых, делает эту головоломку менее сложной, чем кажется на первый взгляд, по крайней мере, для небольших чисел. Посмотрим на количество взвешиваний от одной до восьми монет.
Для одной и двух монет легких монет по второму условию быть не может, поэтому взвешивания не требуются.
Три монеты: Только одна светлая монета. Для каждой головоломки 1 требуется одно взвешивание.
Четыре монеты: Только одна светлая монета. Требуется одно дополнительное взвешивание, поэтому w = 2.
Пять монет: от одной до двух легких монет. Это первый интересный случай. Вопрос в том, должны ли мы взвешивать одну монету против одной или две монеты против двух?
Если мы взвесим один против одного, то мы можем иметь:
- Два несбалансированных взвешивания: обнаружены две монеты; мы сделали.
- Одно сбалансированное взвешивание из двух: сбалансированные монеты должны быть нормальными, поэтому последняя монета нуждается в другом взвешивании, w = 3.
- Два уравновешенных взвешивания: при третьем взвешивании взвесьте одну монету из каждого предыдущего взвешивания против другой. Если они уравновешены, то все четыре нормальные, а монета 5 — светлая. Мы сделали; w = 3 снова. Если они не уравновешены, мы нашли две легкие монеты, и мы закончили взвешивание за три взвешивания.
Если вместо этого мы взвешиваем два против двух, нам все равно потребуется три взвешивания, потому что мы должны различать возможности того, что монеты могут быть разными или похожими с любой стороны. Взвешивание с использованием небольшого количества монет, сгруппированных вместе, по-видимому, не имеет никаких преимуществ перед взвешиванием с использованием отдельных монет.
Это подтверждается:
Шесть монет: от одной до двух легких монет; w = 4.
Семь монет: от одной до трех легких монет; w = 5.
Восемь монет: от одной до трех легких монет; w = 6. Это решение имеет простую структуру:
- Сначала сделайте четыре взвешивания одной монеты против другой. Используются все монеты.
- Наихудший случай: все четыре взвешивания уравновешены (есть две легкие монеты, которые уравновешивают друг друга).
- Следующие два взвешивания: Взвешивание монеты весом 1 против монеты весом 2; аналогично взвесьте монету весом 3 против монеты весом 4.
- Одно из этих взвешиваний будет несбалансированным, идентифицируя две легкие монеты. Мы закончили шесть взвешиваний.
Извините, наша последовательность 0, 0, 1, 2, 3, 4, 5, 6 определенно недостаточно интересна, чтобы представить ее на рассмотрение. Он-лайн энциклопедия целочисленных последовательностей!
As Йонас Тёгерсен Кьельстадли указал, решение кажется w = n − 2 для малых чисел, но мы не доказали, что это не изменится для больших чисел. Некоторые n, использование нескольких взвешиваний монет может начать работать лучше или больше взвешиваний, чем n − 2 может потребоваться. Мы можем просто обобщить решение для восьми монет на все степени двойки, дав n − 2 как верхнюю границу количества взвешиваний для всех степеней двойки.
Марк Пирсон обсудил сходство этой проблемы с кодами, исправляющими ошибки, и предложил использовать подход теории информации, основанный на количестве возможных результатов. Используя такой подход, Майк Робертс опубликовал нижнюю границу для более общего случая, который Райнер из весны получил приближение для. Райнер также опубликовал верхняя граница из опубликованной статьи, но отметил, что границы не точны для низких n и поэтому бесполезна для малых чисел, которые мы рассмотрели выше. Таким образом, для семи монет приведенные границы дают диапазон от 4 до 16, между которыми находится наш ответ 5. Дж. Пайетт дает дополнительные математические ссылки и оценки для всех головоломок.
Спасибо всем, кто принял участие. Приз Insights за этот месяц вручается Теду и Райнеру вместе с Весной. Поздравляем!
Увидимся в следующий раз за новыми Инсайты.
