Решение задач на определение фальшивой монеты взвешиванием 2.0

    Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.



    Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:

    1) неизвестно какая она по весу;
    2) известно, что она легче/тяжелее остальных.

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



    1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.



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

    N >= log3A,


    где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
    A — количество монет.
    Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)

    Сам алгоритм решения простой, и я покажу его на примерах

    1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее

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

    A = 2 * B + C,

    где A — количество монет;
    B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
    C — остаток.

    По условию задачи

    26/3 = 8.666(6),

    26 = 2 * 9 + 8,

    При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.

    Далее у нас возможны два варианта:

    1) фальшивая монета в левой/правой группе (9 монет)
    2) фальшивая монета в остатке (8 монет)

    для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3;
    для 2 варианта — 8 = 2 * 3 + 2

    Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее

    Этот же результат я приведу в таблице
    № взвешивания Число монет ЛГ ПГ Остаток
    1 26 9 9 8
    2 8 3 3 2
    2 9 3 3 3
    3 2 1 1 0
    3 3 1 1 1


    по формуле — log326 =2.9656 — соответственно количество взвешиваний — 3.

    еще пример:
    число монет- 71. По формуле log371 =3.8800 — количество взвешиваний — 4. Проверяем

    № взвешивания Число монет ЛГ ПГ Остаток
    1 71 24 24 23
    2 23 8 8 7
    2 24 8 8 8
    3 7 3 3 1
    3 8 3 3 2
    4 2 1 1 0
    4 3 1 1 1


    Ну с алгоритм решения этих задач, я думаю, понятен.

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


    В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.

    A = 3 * B + C,

    где A — количество монет;
    B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону;
    C — остаток.

    Например, для 58-ми монет — это будет 58 = 3 * 19 + 1, для 23 = 3 * 7 + 2, для 15 = 3 * 5 + 0 и т. д.

    Далее выполняем два взвешивания:
    1) первая и вторая группы;
    2) первая и третья группы;
    и анализируем результат.
    Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке. Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.

    Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.
    Что касается формулы, то она примет следующий вид

    N >= log3B + 2,

    где N — максимально необходимое количество взвешиваний, натуральное число;
    B — количество монет в группе после второго взвешивания.
    А если учесть, что B = A/3, где A — количество всех монет, тогда получим:

    log3B = log3A — 1,


    N >= log3A + 1



    Итог:


    1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:

    N >= log3A



    2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:

    N >= log3A + 1



    где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
    А — количество монет.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 42

      +5
      Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.

      Не понял, зачем еще два взвешивания, если у нас к этому моменту целая куча эталонных монет?
        0
        Вот еще интересная задачка: есть семь мешков с монетами, много монет в каждом мешке, но количество необязательно равное. В одном мешке монеты фальшивые. Вес настоящей монеты 5 грамм, фальшивой — 4. За сколько взвешиваний можно определить мешок с фальшивками, если имеются в распоряжении весы (не две чаши, а электронные весы, показывающие граммы).

        Но самая интересная задача, которая мне попадалась — это про цвета глаз жителей племени на необитаемом острове.
          +1
          Ох уж этот подвох с формулировками
          Можно за одно взвешивание определить
            +1
            Вы не поверите, но ответ таки и есть «за одно взвешивание». Решение несложное, не буду спойлерить.
              0
              Аааа… можно )))) не ожидал такого коварства ))
                +1
                Ок, суть я понял, осталось подобрать коэффициенты для случая когда в мешках меньше миллиона монет
                  +3
                  Или для случая, когда может быть меньше семи монет?
              –1
              за 3 взвешивания. нужно просто достать из каждого мешка по монете, потом взвешивать частями (4,3), (2,2) и (2,1), и проверять кратность 5.
                +5
                Нет, там нужно только одно взвешивание.

                Спойлер
                1 монета с первого мешка, 2 со второго… 7 с последнего седьмого мешка. Кладем на весы все эти монеты, весы показывают x грамм.
                далее:
                (1+2+3+4+5+6+7)*5 — x = y
                где y и будет номером мешка с фальшивыми монетами
                  +2
                  Окак… А граждане вот сверху намекали на формулировку, выделяя слово «Можно». Я чего то решил, что взять монету из любого мешка и взвесить ее. Если 4 гр. попалось с первого раза, то действительно МОЖНО! )))
                    +1
                    из первого мешка одну монету, из второго две из третьего три и т.п., отличие полученного веса от нормального (если бы все были по 5 грамм) и будет номером мешка с фальшивыми монетами.
                      0
                      Угу, мне сверху уже объяснили :)
              0
              Должно быть N<= так как алгоритм может быть не оптимальным.

              Например для 12и монет можно найти фальшивую за 3 взвешивания а не за 4.
                –1
                Для 12 монет существует способ требующий всего 2 взвешивания
                  0
                  Для какой формулировки задачи требуется всего 2 взвешивания?
                    –1
                    Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?
                      +2
                      В таком случае ваше утверждение неверно. Вы не сможете определить монету, даже если вам сказать легче она или тяжелее настоящей. 2 взвешивания — это всего 9 различных возможных исходов, каждому исходу соответствует ровно один ответ (скажем, монета под номером 3 — фальшивая), а вариантов расположения фальшивой монеты — 12.
                  +1
                  По ссылке оценка ½(3n – 3), то есть для двух взвешиваний это 6. Если я не так понял, поясните, пожалуйста, как за 2 взвешивания определить фальшивую монету из 12.
                    0
                    Да, все верно. Был неправ. Для 12 монет минимумом, таки, являются 3 взвешивания. Ушёл выправлять знания того смутьяна, который убедил меня в ином.
                      0
                      Кстати, оценка Дайсона для количества монет меньше на одну монету, чем лучшая оценка. В частности, за 3 взвешивания можно определить фальшивую не среди 12 монет максимум, а среди 13 монет.
                        0
                        там же есть пример.
                        Например, для 12 монет, замаркированных так, как показано в таблице, нужно проделать такие три взвешивания: (1,4,7,10) – (3,6,9,12), (3,6,9,10) – (2,5,8,12), (3,4,8,12) – (2,6,7,11).
                          0
                          Я не спорю с примером. Я говорю, что по оценке Дайсона получается, что для 13 монет нужно 4 взвешивания, когда хватит трёх.
                            0
                            максимальное количество монет для трех взвешиваний – 13,5.
                              +1
                              Если монет 13.5, то я без взвешиваний покажу фальшивую :)
                                –1
                                Это следует из формулы
                                m=½(3n – 3) = (33 — 3)/2 = 13.5
                                т.е. либо 13, а возможно и все 14 монет можно взвесить за три взвешивания. А если принять, что половинка монеты существует где-нибудь в 4D+ измерении, то взвешивать все равно придется.
                                  +2
                                  Простите мне мою неправославную арифметику, но мне кажется, что (33–3)/2 = (27–3)/2 = 24/2 = 12
                                    0
                                    Действительно. Снова косячу. Интересно, что не так с Дайсоном в таком случае.
                +4
                Ваша оценка для первого случая верна, а для второго — нет.

                Давайте воспользуемся информационным подходом: в первом случае (когда известно, тяжелее монета или легче) у нас есть A случаев, а каждое взвешивание может дать три исхода (больше, меньше и равно) и в лучшем случае должно уменьшать количество случаев в 3 раза, поэтому, действительно
                image

                Если нам неизвестно, тяжелее фальшивая монета или легче, у нас 2A случаев, и оценка должна быть порядка
                image
                Что меньше, чем ваша оценка «сверху».

                Прежде чем приводить алгоритм, можно ещё улучшить оценку: представим себе, что мы провели все взвешивания, и весы всё время оказывались в равновесии. Даже если в этом случае мы сможем определить фальшивую монету, мы не сможем сказать, тяжелее она или легче (а в задаче это в общем-то и не спрашивается). Таким образом, два случая «сливаются» в один и мы можем, вообще говоря, определить фальшивую за image взвешиваний. Однако, это можно сделать только в одном случае: если у нас в кармане есть заведомо настоящая монета.

                Утверждение 1: если у нас в кармане есть заведомо настоящая монета, то мы можем определить за n взвешиваний фальшивую среди image монет.

                Доказательство проведём по индукции. База для n=1. За одно взвешивание мы можем определить фальшивую среди image монет. Мы достаём монету из кармана и кладём на одну из чаш весов, а на вторую чашу кладём одну из двух монет среди которых нам нужно определить фальшивку. Если весы в равновесии, то фальшивая монета не участвовала во взвешивании, если не в равновесии — фальшивая та, что на чаше весов.

                Допустим, утверждение 1 справедливо для n. Докажем, что за n+1 взвешивание мы сможем определить фальшивую среди image монет. Заметим, что если мы добавим к тестовым монетам нашу монету из кармана, то их количество поделится на три:
                image
                Тогда разделим наши монеты на три равные кучки, две кучки положим на чаши весов, одну отложим в сторону. Также убедимся, что монета из кармана попала на правую чашу (а не осталась в стороне). Проведём взвешивание. Если оказалось, что весы в равновесии, то фальшивая монета среди отложенных, и за n взвешиваний мы умеем её находить. Если оказалось, что весы не в равновесии, то мы делаем следующий трюк: склеиваем монеты попарно с правой и левой чаш весов. У нас должно получиться image «толстых» монет. Среди этих «толстых» монет за n взвешиваний мы умеем определять фальшивую (теперь у нас нет монетки из кармана: она склеена, но мы можем изготовить новую «толстую» монету, склеив две настоящие монеты из кучки, отложенной на первом взвешивании). Единственно, за чем нужно следить, чтобы теперь «толстая» монета, «внутри» которой есть монета из кармана, всегда попадала в откладываемую стопку в последующих взвешиваниях.

                Когда мы определили, какая из «толстых» монет фальшивая, мы также определили легче она или тяжелее настоящей. Теперь можно вспомнить результат первого взвешивания: если в первом взвешивании перевесила правая чаша, а фальшивая монета легче, то из двух монет, входящих в «толстую» монету, фальшивая та, которая пришла с левой чаши весов (напомню, в каждой «толстой» монете одна монета с правой чаши, а другая — с левой). Лишь в одном случае мы не можем определить, легче фальшивая или тяжелее: когда во всех взвешиваниях весы были в равновесии. Но в этом случае мы знаем, что «внутри» всё время откладываемой «толстой» монеты, которая оказалось фальшивой, одна из монет — это монета из кармана, поэтому фальшивая вторая монета. Таким образом, мы доказали базу индукции и шаг индукции.

                Утверждение 2: если у нас нет дополнительных монет, то за n взвешиваний мы можем определить фальшивую среди image монет (на одну меньше, чем в утверждении 1).

                Сначала надо пояснить, почему мы не можем достичь максимальной оценки как в утверждении 1. Если у нас нет дополнительной монеты, то мы не можем разделить image монет на три кучки. Если мы на чаши весов положим по image монет, то в случае если весы окажутся не в равновесии, нам не хватит n−1 взвешиваний, чтобы различить image случаев (а именно столько монет сейчас на чашах весов, и каждая может быть фальшивая). А если мы отложим image монет, то оставшееся нечётное количество монет мы не сможем уравновесить.

                Если же количество монет на одну меньше, то на две чаши весов положим по image монет, а в сторону отложим image монет. Если весы в равновесии, то за оставшиеся взвешивания мы сможем (согласно утверждению 1) определить фальшивую в отложенных монетах (роль монеты из кармана может играть любая монета с уравновешенных весов). Если весы не в равновесии, то мы также склеиваем монетки как в доказательстве утверждения 1 и добавляем виртуальную монету, которая во всех последующих взвешиваниях будет откладываться.

                Простите за простыню.
                • UFO just landed and posted this here
                  • UFO just landed and posted this here
                      0
                      1. Смотрите, допустим мы произвели взвешивание 4х4, и оказалось, что
                      1 2 3 4 < 5 6 7 8
                      Следующее взвешивание, которую нужно сделать (и которое следует из моего решения), это
                      (1 5) (2 6) ? (3 7) (12 13)
                      Если происходит равенство, то все монеты, участвующие во взвешивании настоящие, следовательно фальшивой является толстая монета (4 8), которая не участвовала во взвешивании. Последним взвешиванием мы узнаём легче толстая фальшивая монета или тяжелее.
                      (4 8) ? (12 13)
                      Если монета (4 8) легче, то фальшивая монета 4, если тяжелее — 8.
                      Если вы внимательно прочитаете ещё раз моё решение, то вам не составит труда разобрать все остальные случаи.

                      2.
                      Во-вторых, вы не совсем верно используете «информационный подход»

                      >>Здесь должен быть аргумент «нет, ты!» =)
                      Мы не сможем склеить все случаи, просто не сможем. Если какое-либо из взвешиваний закончится перевесом, то когда мы найдём фальшивую монету мы обязательно будем знать, тяжелее она или легче: для этого достаточно вспомнить на какой стороне весов она лежала (здесь можно придумать задачу про квантовые монеты, где эту несправедливость жизни можно обойти, но наши монеты классические, увы). Таким образом, в одном и ровно в одном случае мы не узнаем ничего про вес фальшивой монеты: когда все взвешивания закончатся равенством. Но это позволяет скостить нам только один вариант. Так что image это точная нижняя оценка (и она достижима при наличии настоящей монетки в кармане).
                      • UFO just landed and posted this here
                          0
                          Так мы и действуем по индукции. Только для индукции нужно пять монет и одна монета из кармана, одна монета у нас виртуальная — мы её будем всё время откладывать, а монету из кармана делаем из заведомо настоящих монет (12 13), например.

                          Попробуйте сначала по алгоритму 1 (с одной настоящей монетой в кармане) найти за одно взвешивание фальшивую среди двух, потом за два взвешивания — среди пяти, потом проследите как работает индукция для 13 и далее, и вы увидите, что наш алгоритм абсолютно детерменирован. Вы же математик всё-таки, у вас получится.
                          • UFO just landed and posted this here
                    • UFO just landed and posted this here
                      • UFO just landed and posted this here
                          0
                          Можно поделить людей на три категории: те кто умеет решать задачи, те кто не умеют и те кто скрывает свое неумение решать задачи нытьем про гравитацию луны.
                          Вы небось еще когда решаете задачу про «из пункта а в пункт б выехал мотоциклист...» при расчетах учитываете радиус закругления Земли.
                            0
                            Вы небось еще когда решаете задачу про «из пункта а в пункт б выехал мотоциклист...» при расчетах учитываете радиус закругления Земли.

                            Когда этот мотоциклист едет на юг, потом на восток, а потом на север, то ничего другого не остаётся :(
                            • UFO just landed and posted this here
                                0
                                Можно поподробнее, что такого интересного в этой формуле?
                                • UFO just landed and posted this here

                          Only users with full accounts can post comments. Log in, please.