Универсальная методика к решению задач на примере головоломки «12 монет, 3 взвешивания»

    Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку.

    Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.

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

    Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?

    Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».

    Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.

    image

    1. Подсказки
    В процессе решения поможет:

    1) Понижение энтропии (меры неопределенности) и ответы на вопросы:

    • Что узнали на предыдущем шаге?
    • Что снижает неопределённость?
    • Какой информацией располагаем?
    • Что еще нужно узнать?

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

    2) Декомпозиция. Подход от простого к сложному. Если подготовить решение простейших случаев, затем использовать их для решения задачи (алгоритм разделяй и властвуй) то, будет проще, чем представлять всю ситуацию в голове.

    Алгоритмы «разделяй и властвуй» разбивают задачу на две или более подзадачи того же типа, но меньшего размера до элементарных задач и объединяют их решения для получения ответа к исходной задаче.

    Составьте вопросы для декомпозиции. Какие бы вы предложили?

    2. Декомпозиция
    Какие вопросы вы сформулировали для декомпозиции? Есть совпадения?

    1) Какая ситуация самая элементарная? Что можем сделать за одно взвешивание?

    За одно взвешивание можем определить, какая монета тяжелее, равен ли вес монет.

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

    Необходимо взвесить монеты, и в зависимости от стрелки весов определить фальшивую.

    3) Если у нас 2 монеты, и, не известно, фальшивая тяжелее или легче, как за одно взвешивание определить фальшивую?

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

    4) Если у нас 3 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?

    Необходимо сравнить любые две из этих монет, если они равны, фальшивой является третья монета.

    5) Если у нас 3 монеты, и, неизвестно, фальшивая тяжелее или легче. Можно ли определить фальшивую за одно взвешивание?

    К сожалению, нет.

    6) Если у нас 4 монеты, и, неизвестно фальшивая тяжелее или легче, можно определить фальшивую за одно взвешивание?

    К сожалению, нет.

    7) Если у нас 4 монеты, и, неизвестно, фальшивая тяжелее или легче, за сколько взвешиваний можно определить фальшивую?

    За два взвешивания.

    Далее из элементарных случаев соберем ситуации из 8, 9, 10, 11 и 12 монет. Как вы видите решение?

    Ниже полное решение.

    3. Решение
    Первый шаг: разделим монеты на 3 группы по 4: 1 2 3 4, 5 6 7 8, 9 10 11 12.

    Сравним первые две группы. Возможны три варианта:

    1. первая группа тяжелее;
    2. вторая группа тяжелее;
    3. равны.

    image

    1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.

    image


    Делим третью группу на две: 9 10 11 12

    Сравниваем 9 и 10:

    • если они равны, то фальшивая монета во второй группе – сравниваем 9 и 11. Если 9 и 11 равны — то фальшивая – 12, если нет -11
    • если они не равны, то фальшивая в первой группе – сравниваем 10 и 12. Если 10 и 12 равны – фальшивая – 9, если нет – 10.

    Таким образом мы нашли фальшивую монету.

    2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».

    image


    Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:

    • Равны. Фальшивая монета находится среди чисел: 6 7 8. Сравниваем 6 и 7, если равны – фальшивая — 8, если 6 больше, то фальшивая – 7, если 7 больше, то фальшивая – 6, так как в данном случае фальшивая монета легче.
    • Первая группа тяжелее, то фальшивая монета либо 1, либо 5. Сравниваем 1 и 9, если они равны – фальшивая монета — 5, если нет — 1.
    • Первая группа легче, то фальшивая среди монет 2 3 4, так как известно, что 9, 10 и 11 настоящие, и перевесить вторая группа может только за счет монет 2, 3 и 4. Сравниваем 2 и 3, если равны – фальшивая 4, если 2 тяжелее, то фальшивая – 2, иначе 3-я является фальшивой.

    3) Случай когда вторая группа тяжелее первой, аналогичен второму.

    image

    Общая диаграмма «Дерева решений» представлена ниже.

    image

    Заключение
    При поступлении задачи на доработку или отладку хорошо применить рассмотренный выше подход:

    1. Определиться, что дано?
    2. На какие элементарные случаи\задачи можно разложить?
    3. Что неизвестно для решения задачи? Какие эксперименты нужно провести, чтобы снизить энтропию?
    4. Выполнить.
    5. Задача решена? Нет? Вернуться к шагу 1.

    Успешных решений.

    Поделиться публикацией

    Комментарии 46

      +15
      О, универсальная методика решения задач, ну наконец-то. Решите, пожалуйста, P = NP.
        0
        Хотя я согласен с вашим общим настроем, но отмечу, что конкретно для этой задачки зависли на 2-й стадии (декомпозиции). Пока доказывают что-то для частных случаев, но «глобальной декомпозиции» пока провести не удалось.

        P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)
          +2
          Ну, я просто не люблю неоправданно громкие заголовки. «Полезная эвристика» звучало бы гораздо лучше.

          А задачу я, кстати, в своё время решал довольно долго, чуть ли не полчаса. При том, что я был регулярный участник всероса.
            –1
            Спасибо за название.
          0
          Решите, пожалуйста, P = NP.
          Ну все ж ясно, N=1, P — любое. :)
            0
            Вы упустили случай P=0, N — любое)
              0
              Да упустил,) я вам оставил пространство для маневра :)
              0
              Мне учительница математики помню рассказывала.
              Она подрядилась быть репетитором для старшекласника. Подготовка к поступлению в ВУЗ.
              И вот на первом занятии она дает задает ему вопрос:
              как можно преобразовать
              six^2 x/cos^2 x

              Получает ответ:
              six^2 x/cos^2 x =
              six x/cos x =
              sin/cos
              in/co

              На этом месте она поняла, что работы… предстоит много.
                0
                a как еще «шесть» сокращать? ) Шучу, видимо опячатка.

                Не так много — только объяснить человеку, что такое тригонометрические функции, а сокращать дроби он умеет.)
                  0
                  Блин. Действительно опечатался.
                  Но к концу сумел исправиться))

                  Настолько не знать, что такое тригонометрические функции — это надо было постараться.:)

                  Сокращать дроби тоже не умеет, кстати. «Квадраты» так не сокращают.
                    0
                    Кстати да, еще и степени объяснять надо… многочлены, квадратные уравнения, и т.д. Все друг за друга цепляется. В общем, много получается.)
            +3
            За 3 взвешивания необходимо найти фальшивую монетку и определить легче она или тяжелее.

            Решение не до конца.

              +1
              Хм, я уверен, что я тоже это видел, но похоже автор уже изменил условия чтобы они соответствовали его решению…
              В любом случае, оригинальная задача показалась мне интереснее и я ее, кажется, решил:
              Решение
              Как найти фальшивую монетку и определить легче она или тяжелее.
              монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
              image
              image upload
                0
                del
                  0
                  В любом случае из условий
                  Неизвестно легче или тяжелее
                  — соответственно и относительный вес монеты будет найден.
                    +1
                    К сожалению, нет. Я не буду проверять все варианты, но очевидно, что алгоритм не работает на примере 12 монеты. В посте решение о том, что она фальшивая принимается в результате цепочки, в которой 12 монета вообще ни разу не оказывается на весах — 1234 = 5678, 9 = 10, 10 = 11. В данном случае она может быть легче, тяжелее, и даже точно такого же веса.
                0
                Тут было неправильное решение, я его, пожалуй, сотру. Спасибо людям из комментов ниже за указание на ошибку.
                  0
                  А если фальшивая монета легче чем оригинал?
                  UPD: О! Исправились:) Но не до конца.
                  И я тогда дополню.
                  Не известно же легче фальшивка или тяжелее)
                    +2
                    Стоило потратить ещё минуту на внимательное чтение условия) вы решили не ту задачу.
                      0
                      А почему из более тяжелой кучи? Может фальшивая монета легче?
                        0
                        Да, это я косякнул — не учел, что неизвестно, легче монетка или тяжелее.
                      0
                      Извините, в вашем решении так и не понял, как вы за одно взвешивание выделили целевую кучку из трех?
                        0
                        Я может «не догоняю», но во втором случае почему вы разбили все группы на разные веса? Должно ведь быть >,0,0 или <,0,0.
                        0
                        Раньше думал, эта задача имеет единственное решение. Теперь появилась новая задача — сколько решений имеет эта задача?
                          0
                          DEL
                            0
                            На самом деле выше я пропустил две ветви в самом конце решения. Вот тут полное дерево:
                            Решение
                            Как найти фальшивую монетку и определить легче она или тяжелее.
                            монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
                            image
                              0
                              Ну допустим я злоумышленник и подложил «облегчённую» монету №7 где для неё вариант?
                              И тут вообще только 16 вариантов из 24 (12* L-H) возможных.

                              Или я что-то упустил?
                                0
                                Похоже что упустили. Если 7 (или 5, 6 или 8) монета легче сработает блок "… swap 1234 with 5678". Алгоритм то один и тот же на самом деле, я решил сэкономить место и не расписывать оба варианта. Просто поменяйте кучки 1234 и 5678 местами и продолжайте, теперь легкая монета будет иметь индекс 3. Прошу прощения за неочевидность.
                                  0
                                  Ок да, разобрался. Странноватый алгоритм, кажется что можно проще. Интересно, сколько вообще существует алгоритмов решения данной задачи?
                                    0
                                    Я пока знаю только одно решение, мое. Решение автора я не считаю решением первоначальной задачи, так как оно не отвечает на вопрос легче или тяжелее?
                                    Вы знаете другие решения? Поделитесь?
                                      0

                                      Решение автора отвечает на вопрос "легче или тяжелее" на втором-третьем взвешивании, в зависимости от результатов взвешивания. Единственное исключение — когда после первого взвешивания, фальшивая монета оказывается в третьей группе, и в последующие 2 взвешивания она не попадает. Тогда да, ее вес неизвестен.

                                      0
                                      Три, как минимум -> mathforum.org/library/drmath/view/55618.html. Мне второе больше всех нравится, хотя (во всех) коряво то, что монеты по условию выглядят одинаково, а если их пронумеровать, то выглядеть одинаково они перестанут.
                                  0
                                  Вместо сравнения 1 2 5 6 vs 4 8 11 12 достаточно сравнить 5 6 12 vs 4 7 8. И «тройки» сравнивать чуть легче, чем «четвёрки», и «лёгкость» фальшивой монеты более однородно по случаям распределится. У Вас в каждом из трёх случаев она может быть как легче, так и тяжелее нормальной. А в данном варианте в случае "=" монета всегда H, при сохранении неравенства ">" монета всегда L, и только при смене неравенства на "<" будут смешанные варианты.
                                  +2
                                  Если не ошибаюсь, где-то во второй половине девяностых, целое семейство задач про монеты, с их подробным разбором было опубликовано в журнале Компьютерра. Я, тогда ещё школьник, здорово помучился, пока не сообразил, что, взвешивая две из трёх частей, мы не только сужаем количество монет, среди которых фальшивая, но и получаем гарантированно «настоящие» эталоны, которые можно использовать в последующих взвешиваниях.
                                    0
                                    А почему нельзя так?
                                    1 взвешивание 6vs6
                                    2 взвешивание 3vs3
                                    3 взвешивание 1vs1 и если равны то оставшаяся?
                                      0
                                      Потому что неизвестно, является ли фальшивая монета легче или тяжелее настоящей. Вы взвешиваете 6 vs 6 и одна группа монет тяжелее другой. Но что это значит? В тяжёлой группе есть тяжёлая фальшивая монета или же в лёгкой группе — лёгкая фальшивая монета? Ноль полезной информации.
                                        0
                                        В первом же взвешивании уже неизвестно, какую из шестерок брать для второго взвешивания, так как фальшивая монета может быть как легче, так и тяжелее нормальной.
                                        0
                                        2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».

                                        image

                                        Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:

                                        • Равны. Фальшивая монета находится среди чисел: 6 7 8.

                                        А двенадцатая монета куда подевалась?
                                          –1

                                          Лежит в кармане. Она не фальшивая, в решении не участвует.

                                            –1
                                            Посмотрите внимательно 1-ый случай

                                            1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.

                                            image
                                              0
                                              Ой, в данном случае с 9 по 12 — монеты настоящие.
                                                –1
                                                Верно
                                              0
                                              Дано: 12 14 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку, в распоряжении имеется одна настоящая монета.

                                              Предполагаю, что можно решить задачу в общем случае для:
                                              (3N+1)/2 монет + настоящая монета за N взвешиваний.
                                              N = 1, монет = 2 + настоящая монета
                                              N = 2, монет = 5 + настоящая монета
                                              N = 3, монет = 14 + настоящая монета
                                              и.т.д
                                              Поскольку N взвешиваний дают log2(3N) бит информации — информация о местоположении фальшивой монете среди (3N+1)/2 монет и ее весе равна log2(3N+1) бит, однако в одном из вариантов взвешиваний, когда весы всегда были в равновесии, фальшивая монета никогда не попадает на весы и мы не знаем ее вес, т.е. количество информации сокращается до log2(3N) бит.

                                              Лемма: (3N+1)/2 + 1 — всегда делится на 3 т.к (3N+1)/2 + 1 = 3*(3N-1 + 1)/2
                                              Случай N=1, монет = 2 неизвестных + настоящая:
                                              Делим монеты на 3 кучки, так чтобы настоящая была на одной из чашек весов.
                                              С вероятностью 50% определяем вес фальшивой.
                                              Случай N=2, монет = 5 неизвестных + настоящая:
                                              Делим монеты на 3 кучки по 2, так чтобы настоящая была на одной из чашек весов.
                                              Результат:
                                              весы в равновесии => переход к случаю N=1
                                              весы не в равновесии => (фальшивая монета на весах) => снимаем с весов одну неизвестную монеты, переставляем на ее место другую неизвестную монету с соседней чашки, возмещаем освободившееся место настоящей монетой.
                                              Результат:
                                              весы пришли в равновесие — фальшивую монету сняли
                                              весы сменили показания — фальшивую монету переместили на другую чашку
                                              весы не изменили показания — фальшивую монету не трогали.
                                              Случай N=3, монет = 14 неизвестных + настоящая:
                                              Делим монеты на 3 кучки по 5, так чтобы настоящая была на одной из чашек весов.
                                              Результат
                                              весы в равновесии => переход к случаю N=2
                                              весы не в равновесии => (фальшивая монета на весах) => снимаем с весов 3 неизвестных монеты, переставляем на их место другие три неизвестных монеты с соседней чашки, возмещаем освободившееся место 3-мя настоящими монетами.
                                              Результат
                                              весы пришли в равновесие — фальшивую монету сняли
                                              весы сменили показания — фальшивую монету переместили на другую чашку
                                              весы не изменили показания — фальшивую монету не трогали.
                                              + стал известен вес фальшивой монеты
                                              Третье взвешивание — определить фальшивую монету из трех монет при известном весе за одно взвешивание — тривиально.

                                              P.S. Поскольку заведомо настоящая монета появляется только после первого взвешивания, в случае когда ее нет в самом начале, приходится стартовать с 13 неизвестных монет (разбить их на группы по 5+4+4), но этот способ вы можете сами найти.

                                              P.P.S для просто 14 неизвестных монет, тоже хватает информации чтобы найти фальшивую монету, однако невозможно уравновесить весы в самом первом взвешивании.
                                                0
                                                Поставило в тупик «3 взвешивания» а в решении приводится далеко не 3!
                                                  0
                                                  Да ну? А сколько?
                                                  0
                                                  Нашел на просторах интернета

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое