Взвешивания и количество информации

Сначала заметим, что за три взвешивания на чашечных весах можно получить только 27 результатов за каждое взвешивание на чашечных весах можно получить только 3 результата — левая чашка легче правой, чашки уравновешены, правая чашка Но так как количество вариантов фальшивой монеты и ее относительного веса равно то должно выполняться неравенство Следовательно,

Пусть

Докажем методом от противного, что определить фальшивую монету и одновременно её относительный вес требуемым способом невозможно. Для этого предположим противное, то есть то, что есть такой способ.

Заметим, что так как за одно взвешивание на чашечных весах можно получить только 3 результата легче правой, чашки уравновешены, правая чашка то за два взвешивания на чашечных весах можно получить только 9 результатов.

Теперь покажем, что в первом взвешивании должно участвовать не менее 10 монет . Действительно, в противном случае в первом взвешивании участвует не более 8 монет быть чётным, так как взвешивание происходит на чашечных весах, а на чашки весов надо класть равные

Значит, если в результате первого взвешивания чашки весов уравновесятся, то фальшивая монета — одна из не менее, чем 5 монет, не участвовавших в первом взвешивании, она может быть как легче, так и тяжелее настоящих, и, следовательно, у нас возможно не менее 10 вариантов и её

А так как число результатов, которые можно получить за два взвешивания, меньше числа вариантов, то определение фальшивой монеты и её относительного веса невозможно.

В первом взвешивании участвует не менее 10 монет — не менее 5 на каждой чаше весов. Если в результате первого взвешивания одна чашка чем 5 оказалась легче, а другая не менее, чем 5 — тяжелее, то у нас возможно не менее 10 вариантов и ее Вновь число результатов за 2 взвешивания будет меньше числа вариантов.

Таким образом, предположив существование способа с помощью чашечных весов определить фальшивую монету и одновременно её относительный вес, мы пришли к заключению, что способ не существует, то есть — к противоречию с предположением.

Пусть

В описании способа определения фальшивой монеты будем использовать следующие обозначения:

1.

Монеты будем обозначать а —

2.

Выражения вида для взвешивания, в котором, в данном случае, пара монет и помещены на левую чашку весов, а пара других монет и (тоже из монет и гирьки) — на правую.

3.

У взвешивания может быть три исхода: < левая чашка = чашки и > правая чашка

4.

означает «для такого выражения возможны следующие случаи» (и далее — случаи для =, > и <).

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

(сначала мы кладем на левую чашу монеты с 1 по 4, а на вторую — с 5 по 8, остальные подобные выражения читаются аналогично)
(получили равенство, тогда фальшивая среди , а все — настоящие):

• (то есть фальшивая (12)):
  

  : фальшивая монета (12) и тяжелее;

  : фальшивая монета (12) и легче;

• (то есть фальшивая среди (9) и легче или среди (10) и (11) и тяжелее):
  

  (возможно только если (9) фальшивая и легче): фальшивая монета (9) и легче;

  (возможно только если (11) фальшивая и тяжелее): фальшивая монета (11) и тяжелее;

  (возможно только если (10) фальшивая и тяжелее): фальшивая монета (10) и тяжелее;

• (то есть фальшивая среди (9) и тяжелее или среди (10) и (11) и легче):
  

  • (возможно только если (9) фальшивая и тяжелее): фальшивая монета (9) и тяжелее;
  • (возможно только если (10) фальшивая и легче): фальшивая монета (10) и легче;
  • (возможно только если (11) фальшивая и легче): фальшивая монета (11) и легче;

(то есть фальшивая среди и легче, или среди и тяжелее, а все — настоящие):

• (то есть фальшивая среди (4) и легче, или (7) и (8) и тяжелее, а все остальные монеты — настоящие):
  

  (возможно только если фальшивая (4) и легче): фальшивая монета (4) и легче;

  (возможна только если фальшивая (8) и тяжелее): фальшивая монета (8) и тяжелее;

  (возможна только если фальшивая (7) и тяжелее): фальшивая монета (7) и тяжелее;

• (возможно только если фальшивая среди (1) и (2) и легче):
  

  (возможна только если фальшивая (1) и легче): фальшивая монета (1) и легче;

  (возможна только если фальшивая (2) и легче): фальшивая монета (2) и легче;

• (возможно только если фальшивая среди (5) и (6) и тяжелее):
  

  (возможна только если фальшивая (6) и тяжелее): фальшивая монета (6) и тяжелее;

  (возможна только если фальшивая (5) и тяжелее): фальшивая монета (5) и тяжелее;

(то есть фальшивая среди и тяжелее, или среди и легче, а все — настоящие):

• (то есть фальшивая среди (4) и тяжелее, или (7) и (8) и легче, а все остальные монеты — настоящие):
  

  (возможно только если фальшивая (4) и тяжелее): фальшивая монета (4) и тяжелее;

  (возможна только если фальшивая (7) и легче): фальшивая монета (7) и легче;

  (возможна только если фальшивая (8) и легче): фальшивая монета (8) и легче;

• (возможно только если фальшивая среди (3) и тяжелее или (5) и (6) и легче):
  

  (возможно только если фальшивая (3) и тяжелее): фальшивая монета (3) и тяжелее;

  (возможна только если фальшивая (5) и легче): фальшивая монета (5) и легче;

  (возможна только если фальшивая (6) и легче): фальшивая монета (6) и легче;

• (возможно только если фальшивая среди (1) и (2) и тяжелее):
  

  (возможна только если фальшивая (2) и тяжелее): фальшивая монета (2) и тяжелее;

  (возможна только если фальшивая (1) и тяжелее): фальшивая монета (1) и тяжелее.

Итак, искомое