пятница, 8 июня 2012 г.

Распределение по весам

Имеется пять монет двух разных весов, но внешне совершенно одинаковых. Число монет, отличных по весу от остальных, неизвестно. Можно ли определить какие из монет более легкие, а какие более тяжелые, с помощью всего лишь трех взвешиваний? Если можно, то как? Если нельзя, то почему?

Ещё головоломки на определение фальшивых монет:


update
Первым правильно ответил Илья.
Ответ
Пять монет обеспечивают 30 различных возможных распределений тяжелые-легкие. При этом три взвешивания позволяют выбрать одну из 27 возможностей. Следовательно, с помощью всего лишь трех взвешиваний отыскать нужно распределение тяжелые-легкие для пяти монет невозможно.

5 комментариев:

  1. Всего легких монет может быть от 1 до 4 (должна быть по крайней мере одна монета каждого из весов).
    Итого: 2^5-2=30 возможных вариантов.

    Каждым взвешиванием исключается не более 2/3 вариантов (поскольку у взвешивания три возможных исхода). Таким оразом, за k взвешиваний можно выявить нужный вариант из не более чем 3^k, в нашем случае 27.

    Вердикт: гарантированно найти все легкие монеты за 3 взвешивания нельзя.

    ОтветитьУдалить
  2. *образом

    Прошу прощения за допущенную опечатку. )

    ОтветитьУдалить
  3. Интересно было бы решить такой вариант задачи: за минимальное число взвешиваний определить количество лёгких монет. )

    ОтветитьУдалить
    Ответы
    1. Как раз за три взвешивания определить число фальшивых монет в данном случае можно. Менее трех взвешиваний недостаточно.

      Удалить