Задача о фальшивой монете (#11)

Вы - величайший математик королевства, но за критику налоговой системы император заточил вас в темницу, где вам ничего не остается, кроме как считать дни, отмечая их карандашом на стене. Но однажды вас приводят к императору, еще более свирепому чем обычно. Один из его двенадцати наместников обвиняется в уплате налогов фальшивой монетой, которая уже попала в казну. Вам как величайшему математику дан шанс обрести свободу, если сумеете найти ту фальшивую монету.

Перед вами весы и 12 одинаковых на вид монет. Вам известно, что фальшивая монета будет отличаться от остальных по весу в бОльшую или меньшую сторону. Но император нетерпелив, и вам дозволено провести взвешивание всего трижды, после чего вас опять бросят в темницу. Вы оглядываетесь в поисках чего-нибудь полезного, но в комнате ничего нет кроме монет, весов и вашего верного карандаша. Как вычислить подделку? Ответ под картинкой.

ОТВЕТ:

Очевидно, что нельзя взвешивать монеты по отдельности, их нужно взвешивать по несколько раз, разделив все монеты на несколько частей и постепенно подбираясь к фальшивой. Для начала разделите 12 монет на три группы по 4 монеты в каждой. Взвешивание двух групп из 4 монет может дать два результата:

1) Если их вес окажется равен, то все 8 монет настоящие, а подделка - среди оставшихся монет. Как отслеживать результаты? Отметьте нулем ("0") все настоящие монеты. Возьмите три из них и сравните с тремя оставшимися невзвешенными
монетами. Если их вес будет равен, то последняя невзвешенная монета - фальшивая. Если их вес не равен, нарисуйте на трех монетах плюс ("+"), если они тяжелее, и минус ("-"), если легче. Сравните две из монет, помеченных плюсом или минусом. Если их вес равен, то третья монета фальшивая. Если не равен, взгляните на знаки: среди монет с плюсом фальшивой будет та, что тяжелее, а с минусом - которая легче.

2) Но что, если при первом взвешивании вес будет неравен? Отметьте тяжелую группу плюсом ("+"), а легкую - минусом ("-"). Невзвешенные монеты пометьте нулем, так как известно, что фальшивая монета была на весах. Нужно думать стратегически, чтобы определенно решить задачу всего за два взвешивания. Нужно перегруппировать монеты. Один из способов: взять вместо трех монет с плюсом три монеты с минусом, а на их место положить три монеты с нулем (см. рис).

Далее следует три возможных варианта:

* Если та чаша весов, которая была тяжелее, все еще перевешивает, значит либо старая монета со знаком плюс на ней тяжелее остальных, либо оставшаяся на другой чаше весов монета со знаком минус - легче. Выберите любую из них и сравните с обычной монетой, чтобы найти фальшивую.

* Если же та чаша весов, которая была тяжелее, стала легче, значит одна из трех перемещенных вами монет со знаком минус и есть самая легкая. Сравните на весах две из них. При равенстве весов третья будет поддельной. При неравенстве - поддельная та, что легче.

* Аналогично, если после замены чаши уравновесились, одна из трех снятых с весов монет со знаком плюс тяжелее остальных. Сравните две из них. При их равенстве - третья поддельная. При неравенстве поддельная та, что тяжелее.

Император одобрительно кивает, выслушивая ваш ответ, а мошенник занимает ваше место в темнице.

Источник: ed.ted.com