Cтраница 3
Требуется за два взвешивания на двухчашечных весах без гирь найти фальшивую монету. [31]
Нетрудно показать, что с помощью трех взвешиваний всегда можно определить фальшивую монету. Для того чтобы информация, получаемая при проведении опыта ос4, была возможно большей, надо, чтобы исходы этого опыта имели возможно более близкие вероятности. Предположим, что на каждую чашку весов нами положено по т монет ( ясно, что не имеет смысла класть на чашки разное число монет: в этом случае исход соответствующего опыта будет заранее известен и полученная информация будет равна нулю); не положены на весы будут 25 - 2т монет. [32]
Если же одна из чашек перетянула, то на ней и находится фальшивая монета. [33]
Поскольку 27 3 - 9, то кучку, в которой находится фальшивая монета, также можно разделить на 3 равные части и снова взвесить две из них. Тем самым после второго взвешивания удастся установить, в какой из трех групп по 9 монет находится фальшивая монета. [34]
За три взвешивания на чашечных весах без гирь нужно определить, есть ли фальшивые монеты и какие монеты тяжелее - фальшивые или настоящие. [35]
Покажем теперь, используя понятие энтропии, что п взвешиваний недостаточно для обнаружения фальшивой монеты среди ( Зп - 1) / 2 монет. V имеет вид ЗМ 1, где М - целое число. Нетрудно заметить, что наибольшее приращение энтропии достигается, если прежде всего разделить монеты на три равные группы. На каждую чашку весов помещается по М монет, так что остается М 1 монет. [36]
Этой небольшой разницы уже оказывается достаточно для того, чтобы обеспечить возможность выделения фальшивой монеты и определения того, легче ли она или тяжелее других, при помощи k взвешиваний. [37]
Каково наименьшее число взвешиваний на чашечных весах без гирь, которое позволяет обнаружить фальшивую монету и выяснить, легче ли она, чем остальные монеты, или тяжелее. [38]
I мы кратко исполыовали деревья при изучении необходимого числа взвешиваний в задаче о фальшивой монете с п монетами. Так рано деревья появились не случайно, ибо понятие дерева используется в различных важных аспектах в каждой главе книги. [39]
Если на чашки весов было положено одинаковое число монет и весы уравновесились, то фальшивая монета заведомо находится в группе монет, не попавших при взвешивании ни на одну чашку. Если одна из чашек перетянет, ( при равном числе монет на чашках), то фальшивая монета находится на второй чашке. Наконец, если на чашки весов было положено разное число монет, то в случае, когда перетянула чашка, где монет больше, фальшивая монета может оказаться в любой из трех групп и такое взвешивание вообще не даст нам никаких сведений о местонахождении фальшивой монеты. [40]
Читатель, наверное, с детства знаком с такой развлекательной задачей: меняле подсунули фальшивую монету, он должен разыскать ее в куче других, настоящих золотых монет, на которые фальшивая внешне похожа. Сходство, конечно, не может обмануть опытного менялу: он отлично знает, что фальшивка отличается от золотого по весу. [41]
Если на каждой чашке весов помещать равное количество монет, то в предположении, что фальшивая монета может появиться при любом таком взвешивании, получим границу величины энтропии. [42]
Стоит рассказать о нескольких грустных историях современных лжеучений лишь для одной цели - научиться узнавать фальшивые монеты. Примеры будут взяты из относительно недавнего прошлого. Полезнее заняться вытаскиванием сучков из своих глаз. [43]
Было бы интересно определить, какое наименьшее число взвешиваний необходимо для того, чтобы выделить одну фальшивую монету из 1000 монет, если не требуется определить, легче она или тяжелее остальных. [44]
Это утверждение имеет одно очевидное исключение: если п 2, а 6 1, то фальшивую монету, разумеется, вовсе невозможно выделить. [45]