вторник, 30 июля 2013 г.

Фальшивая монета и неточные весы

Равновесие
Среди девяти одинаковых на вид монет есть одна фальшивая - она легче остальных. Также в нашем распоряжении есть чашечные весы в количестве двух штук. На первых весах определить фальшивую монету не получится, так как их точность не позволяет определить разницу в весе. Другие весы точнее и разница в весе на них будет заметна. Нам неизвестно где какие весы. Как с помощью всего трёх взвешиваний определить фальшивую монету?

update
Первым правильно ответил Илья.
Ответ
Пронумеруем монеты от 1 до 9. Кладём на первые весы по четыре монеты на каждую чашу: (1,2,3,4) и (5,6,7,8). Если одна группа монет перевесила, то мы нашли точные весы и далее за два взвешивания легко находим фальшивую монету из четырёх. Пусть весы оказались в равновесии. Тогда на вторых весах взвешиваем (1,2,3) и (5,6,7). Худший вариант - весы опять в равновесии. Тогда на вторых весах сравниваем монеты 4 и 8. В случае равновесия фальшивой будет монета 9.

Фальшивая монета и монета с царапиной.

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

  1. Любопытная задача. И картинка хорошая :)

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

    Алгоритм нахождения фальшивой монеты примерно такой. Первым ходом сравниваем две четверки монет на первых весах, для удобства занумеруем монеты и сравниваем 1234 с 5678. Если одна из четверок перевесила, то эти весы точные и за оставшиеся два взвешивания несложно найти легкую монету из четырех подозрительных.

    Пусть весы остались в равновесии. Тогда на вторых весах сравним 123 с 567. Если одна из чашек перевесила, то мы опять нашли точные весы и далее тривиально. Если же весы в равновесии, то эти шесть монет - настоящие. Теперь сравниваем 4 и 8 на вторых весах. Если весы в равновесии - фальшивая монета девятая. Иначе более легкая (и мы опять знаем точные весы).

    Первый ход алгоритма мне кажется однозначным, по-другому дейстовать нельзя. А вот дальше, возможно, есть и другие варианты :)

    ОтветитьУдалить
    Ответы
    1. пока формулировал и вычитывал, уже и ответ подоспел :-)

      Удалить
    2. Всё верно. Интересно, что определить фальшивую монету можно не определяя где точные весы.

      Удалить
  2. Взвешиваем монеты (1,2,3,4) и (5,6,7,8) на первых весах.

    Вариант 1 - весы в равновесии. Либо это неточные весы, а среди монет 1-8 есть фальшивая, либо все монеты верные.
    Далее взвешиваем монеты (1,2,3) и (4,5,6) на вторых весах.
    Вариант 1.1 - весы в равновесии. Взвешиваем на вторых весах монеты 7 и 8. Если весы опять в равновесии, то т.к. мы взвесили все монеты 1-8 на обоих весах, и во всех случаях вес был равный, фальшивая монета - 9. Если при взвешивании на вторых весах монет 7 и 8 одна из них окажется легче, то мы нашли фальшивую, и неточными были первые весы.
    Вариант 1.2 - одна из чашек легче. Тогда вторые весы точные, и третьим взвешиванием определяем фальшивую из соответствующей тройки.

    Вариант 2 - одна из чашек (1,2,3,4) / (5,6,7,8) легче. Значит, точные весы - первые. Двумя взвешиваниями на первых весах находим фальшивую. Например, если легче (1,2,3,4), то взвешиваем (1,2)/(3,4), и затем сравниваем более легую пару между собой)

    ОтветитьУдалить