Теория информации — страница 5

  • Просмотров 2364
  • Скачиваний 229
  • Размер файла 28
    Кб

окажется в данной группе из n монет, равна 1 будут иметь наиболее близкие вероятности, если n = 8 и 25 - 2n = 9. При любом исходе опыта при втором взвешивании (опыт б2) на обе чашки весов следует положить по 3 монеты из определившейся после предыдущего опыта группы, а третьим взвешиванием мы из группы из трёх монет найдём фальшивую, положив по одной монете на обе чашки весов.    Имеется 12 монет одного достоинства; 11 из них имеют

одинаковый вес, а одна – фальшивая – отличается по весу от остальных (причём неизвестно, легче она или тяжелее настоящих). Каково наименьшее число взвешиваний на чашечных весах без гирь, которое позволяет обнаружить фальшивую монету и выяснить, легче она, чем остальные монеты, или тяжелее? Здесь рассматривается опыт А, имеющий 24 возможных равновероятных исхода. Энтропия Н (А) опыта А равна log 24. Таким образом, нам нужно получить log

24 единиц информации. Так как, произведя сложный опыт Ак = а1а2…ак, состоящий в k взвешиваниях, мы можем получить информацию, не большую, чем k log 3 = log 3, а 33 = 27, то с первого взгляда кажется ясным, что трёх взвешиваний будет достаточно. Пусть при первом взвешивании мы положили на обе чашки по n монет. Если чашки весов при этом остались в равновесии, то фальшивой является одна из 12−2n отложенных монет, что отвечает 2(12−2n) исходам

рассматриваемого опыта А (из общего числа 24 исходов). Если перевесила правая чашка, то либо фальшивой и более тяжёлой является одна из n «правых» монет, либо фальшивой и более лёгкой является одна из n «левых» монет − эти случаи отвечают 2n исходам А, точно так же, случаю, когда перевесила левая чашка, отвечают 2n исходов А. Таким образом, три исхода первого взвешивания имеют вероятности и Отсюда сразу следует, что наибольшую

энтропию опыт будет иметь при n = 4, три исхода которого равновероятны. Далее рассмотрим отдельно 2 случая. 1). При первом взвешивании чашки весов остались в равновесии. В таком случае фальшивой является одна из четырёх отложенных монет. Нам надо при помощи двух взвешиваний определить, какая именно из них является фальшивой, и выяснить, легче она или тяжелее остальных; так как у нас осталось 2∙4 = 8 возможных исходов опыта А, а 2 log 3 =

log 9 > log 8, то можно ожидать, что это возможно. Если, однако, положить на каждую чашку весов по одной монете, и они останутся в равновесии, то следующим опытом нам надо будет определить исход опыта, имеющего 4 возможных исхода, что невозможно. То же самое получится, если положить на каждую чашку по две монеты. Однако рано говорить, что трёх взвешиваний недостаточно для выполнения задачи – ведь у нас ещё остались заведомо настоящие