воскресенье, 6 ноября 2011 г.

12 монет, 3 взвешивания

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

Решение
Для удобства пронумеруем монеты от 1 до 12.

Первым взвешиванием сравним две группы по четыре монеты: 1, 2, 3, 4 и 5, 6, 7, 8.

Случай I: первое взвешивание показало равенство
Если весы покажут равенство, то фальшивая монета находится среди оставшихся четырёх монет. Тогда вторым взвешиванием мы сравним три монеты 9, 10, 11 с заведомо настоящими 1, 2, 3.

Если и в этот раз весы покажут равенство, то фальшивка - монета номер 12, и третьим взвешиванием мы сравним её с настоящей и узнаем, легче она или тяжелее.

Если же три монеты 9, 10, 11 оказались легче (тяжелее), то третьим взвешиванием сравним друг с другом монеты 9 и 10. Если они равны, то монета 11 - фальшивая, и она легче (тяжелее) настоящей. Иначе заключаем, что из монет 9 и 10 фальшивая та, которая легче (тяжелее) другой.

Случай II: первое взвешивание показало неравенство
Теперь предположим, что первое взвешивание показало, что монеты 1, 2, 3, 4 тяжелее, чем 5, 6, 7, 8. Случай, когда первые монеты оказались легче, симметричен.

Во втором взвешивании на одну чашу поместим монеты 1, 2, 5, а на другую - монеты 3, 4, 9 (монета 9 - заведомо настоящая).

Если второе взвешивание показало равенство, то у нас остаются три монеты 6, 7, 8, одна и которых легче остальных. Третьим взвешиванием сравниваем монеты 6 и 7. Если они равны, то монета 8 легче остальных. Иначе фальшивой является та, которая легче другой.

Теперь предположим, что во втором взвешивании монеты 1, 2, 5 оказались тяжелее, чем 3, 4, 9. Это означает, что фальшивка находится среди монет 1 и 2, причём она тяжелее остальных. Сравнив в третьем взвешивании эти две монеты друг с другом, мы определим фальшивую.

Предположим, что во втором взвешивании монеты 1, 2, 5 оказались легче, чем 3, 4, 9. Это означает, что либо монета 5 легче остальных, либо одна из монет 3 и 4 тяжелее остальных. Третьим взвешиванием мы сравним друг с другом монеты 3 и 4 и найдём ответ.

31 комментарий:

  1. "Это означает, что фальшивка находится среди монет 1 и 2, причём она тяжелее остальны". Вы забыли, что еще есть вариант, что 3 или 4 может быть легче, поэтому за 3 взвешивания эта задача решения не имеет. Нужно еще одно дополнительное взвешивание.

    ОтветитьУдалить
    Ответы
    1. Влад, спасибо за комментарий. Обсуждение случая II начинается с такого предположения:

      "Теперь предположим, что первое взвешивание показало, что монеты 1, 2, 3, 4 _ТЯЖЕЛЕЕ_, чем 5, 6, 7, 8. Случай, когда первые монеты оказались легче, симметричен."

      Ясно, что если монеты 1,2,3,4 оказались тяжелее, то никак не может быть, чтобы 3 или 4 были ЛЕГЧЕ остальных.

      Если вдруг первом взвешивании 1,2,3,4 оказались легче, чем 5,6,7,8, то мы бы рассматривали симметричный случай. Нужно было бы в последних пяти абзацах всюду заменить "легче" на "тяжелее" и наоборот.

      В лучших традициях учебников по математике, я не стал заниматься копи-пастом, а написал, что случай симметричен, предоставив читателю самому восстановить цепочку рассуждений.

      Так что все честно, в любом случае мы управимся за три взвешивания.

      Удалить
    2. Так возможно же что не 1234 оказались легче 5678, а 5678 оказались тяжелее 1234

      Удалить
    3. не обращай внимания, автор просто туп как палено

      Удалить
    4. Артем, я даже дома на весах проверил, твой случай 2 во втором взвешивании - чушь собачья

      Удалить
    5. Читайте внимательнее объяснение, не нужно оскорблять никого, если вы просто чего-то не можете понять

      Удалить
  2. Случай I: первое взвешивание показало равенство

    А где тут верное решение? да еще и за 4 взвешивания :)

    ОтветитьУдалить
    Ответы
    1. Якщо 1234=5678
      Тоді важемо
      91011 і 123
      Якшо 91011=123, то фальшива 12, якшо 91011>123, то важемо 9 і 10, якшо = то фальшива 11, якшо ні, то фальшива та шо важча.

      Удалить
    2. у меня чуть другое решение.
      Перше зваженн 1234<5678
      Х - правильна монета.(9,10,11,12)
      Якшо 12х<345
      То важемо 1і2
      Якшо = то відп 5, якшо ні , то та шо менша фальшива.
      Якшо 12х>345
      То важемо 3 і 4; та шо менша -фальшива.
      Якшо 12х=345, важемо 67
      Там шо більше фальшива. Якшо рівно то фальшива 8

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

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

      Удалить
    2. За три взвешивания определить фальшивую монету можно, но узнать легче она или тяжелее за три попытки получится не во всех случаях

      Удалить
  4. я решил задачу, но 2-е взвешивание не такое! и в моем взвешивании находится правильно и монета и дельта этой монеты!

    ОтветитьУдалить
  5. Есть еще один вариант решения
    Можно во втором взвешивании выбирать
    1,2,5,6,7 и 8,9,10,11,12 (++--- и -хххх)
    Если = взвешиваем 3 и 4
    Если > 1?2 и 8
    Если < 5,6,7

    ОтветитьУдалить
  6. 1 взвешивание: по 4 монеты на весы. Если равно, дальше тривиально. Интереснее, если неравенство. Мы получаем след картину: тттт > лллл; ээээ. т-монета, которая возможно фальшивая и тяжелее. л - соответственно монета, которая возможно легче. э - эталонная монета.
    2 взвешивание: ттллл ? лээээ. а)Если равно, то какая то из двух предположительно тяжелых монет, не участвовавших во взвешивании - фальшивая. б)Если < , то какая то из 3х ллл монет, что на левых весах, легче. в)Если > , то фальшивая монет - либо одна из двух предположительно тяжелых на левых весах, либо легкая на левых весах. Все случаи а, б, в уже решаемы.

    ОтветитьУдалить
  7. вариантов результатов за три взвешивания - 27 минус 1(три раза равенство быть не может)
    вариантов неизвестная монета из 12 - всего 24
    значит, правильно группируя монеты по четыре на каждую чашку и четыре откладывая, можно результатами 3-х взвешиваний однозначно закодировать варианты расположения фальшивой монеты. Вариантов группировок довольно много, интересно выяснить сколько точно )))

    ОтветитьУдалить
  8. Вообще не правильно, за 3 взвешивания тут не получится

    ОтветитьУдалить
  9. Еще важно помнить 1 условие - какого типа весы! Если старинные (как знак зодиака весы, такие весы), то все понятно, а если электронные, то тут у вас не получится решить задачу :)

    ОтветитьУдалить
  10. Как оказалось, Темыч свое мастерство пропил xd

    ОтветитьУдалить
  11. За первое взвешивание во всех случаях однозначно определяется в какой четверке фальшивка.
    Во втором три из этих четырёх монет путём сравнения с гарантированно чистыми тремя другими монетами показывают среди них ли фальшивка? И тяжелее или легче она. Если не среди них, то она уже ясна, но вывешиванием с любой чистой монетой определяем легче тли тяжелее.
    Если фальшивка среди трёх, то беря две из них сразу находим отловят соответственно легче/тяжелее или при равенстве понимаем что фальшивка оставшаяся третья.

    ОтветитьУдалить
  12. Формулировка расширенной задачи звучит так - определить фальшивую среди 13 3-мя взвешиваниями без указания веса. Принцип решения тот же, но вес уже определить невозможно

    ОтветитьУдалить
  13. Правильное решение автору молодец
    красава

    ОтветитьУдалить
  14. автор ошибся, когда сделал предположение что 125>349 и фальшивая монета в куче 125. Фальшивая монета может быть и в куче 349, тогда она легче

    ОтветитьУдалить
    Ответы
    1. Неправда. Педположим, что во втором взвешивании 125 > 349, и, как вы говорите, фальшивая монета в кучке 349 и она легче. Но монета 9 - заведомо настоящая. Значит, фальшивая лёгкая монета - либо 3, либо 4. Но тогда первое взвешивание показало бы, что 1234 < 5678, а у нас 1234 > 5678. Противоречие. Следовательно, монеты 3 и 4 - настоящие.

      Удалить
  15. Я не совсем понимаю концовку случая 1, может быть кто-то объяснит?
    Мне не понятна фраза "Иначе заключаем, что из монет 9 и 10 фальшивая та, которая легче (тяжелее) другой", мы не знаем какая из них легче а какая тяжелее ведь в данной ситуации у нас нет эталона, а условие задачи говорит, что фальшивка может быть легче, а может быть тяжелее. То есть фальшивой монет опять же может быть или №9 или же №10. Задача не решена.

    ОтветитьУдалить
    Ответы
    1. Допустим, что 9,10,11 < 1,2,3. Мы уже выяснили, что монеты 1,2,3 настоящие. Значит, фальшивая монета точно среди монет 9,10,11, и она точно легче остальных. Фальшивка не может быть тяжелее, потому что тогда весы показали бы 9,10,11 > 1,2,3.

      Если после этого оказалось, что 9 < 10, то мы точно знаем, что 9 легче, и именно она фальшивая. Если 9 = 10, то фальшивая монета 11, и она точно легче.

      Удалить
  16. Я в седьмом классе так и не решил эту задачу. В восьмом товарищ показал мне книгу с решением, но сейчас я его не вспомню, конечно.
    Вот, нашел такое, хотя я его и не понимаю.

    Поскольку взвешивний 3, и каждое взвешивание дает 3 результата (правая чаша весов легче, тяжелее или равны), то всего результатов может быть 3*3*3 = 27.
    Если правая часть весов идет вверх, пусть это бутет 1. Если вниз - то -1. Если равны - то 0.
    Работаем в троичной системе - первое взвешивние получает коэффициент 9, второе - 3, третье - 1.
    Первое взвешивание 5,6,8,10 против 7,9,11,12.
    Второе 2,3,4,7 против 5,6,11,12
    Третье 1,4,10,11 против 2,5,7,8.

    теперь берем каждый из трех результатов 1, 0 или -1, умножаем на 9, 3 или 1, прибавляем. Ответ дает номер фальшивой монеты, знак +/- тяжелее она или легче.

    Примеры
    а) первое было тажелее слева 1, второе тяжелее справа -1, третье равно 0. Итого 9 - 3 + 0 = +6. Фальшивая шестая и она тяжелее.
    б) первое было тажелее справа -1, второе тяжелее слева 1, третье тоже слева 1. -9 + 3 + 1 = -5. Фальшивая 5, и она легче


    Знак решения нужно менять для монет 7,9, 11, 12.
    Например взвешивания дали -1, 1, -1, -9 + 3 -1 = -7
    7 монета фальшивая, но она тяжелее.

    Преимущество этого метода в том, что взвешивания 2 и 3 не зависят от предыдущих, и не надо рассматривать все 27 вариантов.

    Но может кто-то объяснит, почему именно так выбраны взвешивания?

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