четверг, 1 января 2015 г.

Одно взвешивание

Вариация на тему про фальшивые монеты и одно взвешивание. Имеется шесть мешочков с монетами и в каждом из них достаточно большое число монет. При этом все монеты в каждом мешочке либо фальшивые, либо настоящие. Вес настоящей монеты известен (допустим, 5 грамм). Также известно, что фальшивая монета весит на один грамм меньше настоящей. Точное количество мешочков с фальшивыми монетами неизвестно - их может быть несколько. Как за одно взвешивание на точных весах, показывающих вес, определить все мешочки с фальшивыми монетами?

update
Первый - Илья.
Ответ
Нужно взять 1 монету из первого мешочка, 2 из второго, 4 из третьего, 8 из четвёртого, 16 из пятого и 32 из шестого. Если бы все выбранные монеты (63 штуки) были настоящие, то их суммарный вес был бы равен 315 грамм. Разница между полученным при взвешивании значением и 315 будет однозначно определять набор мешочков с фальшивыми монетами. Например, вес 336 грамм может быть получен в единственном случае - если фальшивые монеты находятся в первом, третьем и пятом мешочках (336-315=21=1+4+16).

4 комментария:

  1. Если вес монет известен, то все очевидно.
    А если нет, то я в замешательстве :)

    ОтветитьУдалить
    Ответы
    1. Про слона я забыл. Вес известен. Поправил.

      Удалить
    2. Тогда нужно занумеровать мешки от 0 до 5 и взять из i-того мешка 2^i монет, всего 21 штуку. Разница между 21*5=105 и весом этих монет, записанная в двоичной системе счисления, покажет набор мешков с фальшивыми монетами.

      Удалить
    3. Только всего будет взято 63 монеты, а не 21.

      Удалить