Метод Дайсона выявления фальшивой монеты

Размещено на http://www.allbest.ru/

[Введите текст]

Новосибирск - 2009/10

Управление образования мэрии города Новосибирска

Управление образования Центрального района

Муниципальное бюджетное образовательное учреждение средняя общеобразовательная школа №4

Секция математики

Реферат по теме:

Метод Дайсона выявления фальшивой монеты

Выполнил

Щекотько Михаил

Учитель математики высшей квалификационной категории

Токмакова О.А.

Научный руководитель Тропина Н.В.

к.п.н., доцент кафедры математического анализа НГПУ

Содержание

Введение

1. Метод Дайсона. Решение задачи на выявление фальшивой монеты

1.1 Алгоритм решения для случая

1.2 Алгоритм решения для случая

1.3 Обоснование оптимальности найденного решения

2. Решение задач

Заключение

Список литературы

Введение

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

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

Такие задачи уже давно привлёкали математиков. Со временем появились различные их решения. Долгое время лучшим считалось решение Р. Гудстейна, который указал метод определения фальшивой монеты и её типа за , если число монет .

Но это решение оказалось не самым лучшим. Оказалось, что за n взвешиваний можно выделить фальшивую монету из большего количества монет. Это доказал Ф. Дж. Дайсон.

Целью исследовательской работы является рассмотрение метода Дайсона и решение некоторых задач на его применение.

Работа состоит из двух параграфов

В первом рассматривается метод Дайсона.

Во втором приводятся решения задач с применением метода Дайсона.

1. Метод Дайсона. Решение задачи на выявление фальшивой монеты

Как уже говорилось, Дайсон предложил более оптимальный вариант решения, чем Гудстейн. Он определил, что за n взвешиваний можно выделить фальшивую монету и её тип из числа монет.

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

Для начала введём необходимые для изложения решения задачи обозначения и определения. Для решения задач возьмём все n-значные «троичные числа» (наборы из цифр 0,1,2). Всего в итоге их получается . Далее следует маркировка: монетам присваиваются «левые» и «правые» маркеры, исключая наборы, состоящие из одинаковых цифр (0…0), (1..1), (2…2). «Правыми» маркерами мы считаем те, у которых первая слева пара - пара неравных чисел (например, 01, 12 или 20). Если же это условие не выполняется, то маркер называется «левым».

Решение разделяется на два возможных случая:

Если , то для выделения фальшивой монеты достаточно произвести n взвешиваний.

Если то для взвешивания так же будет хватать n взвешиваний.

Особенно привлекательным при этом методе оказывается независимость выбора монет для последующего взвешивания от результата предыдущего.

В данном параграфе будет рассматриваться каждое из решений в отдельности, как в теории, так и на примерах и обоснование оптимальности метода Дайсона.

1.1 Алгоритм решения для случая

Опишем основные положения этого варианта решения. У нас есть m монет, одна из которых фальшивая, при этом неизвестно, легче она или тяжелее остальных.

Как мы рассматривали в предыдущем параграфе, сперва нужно произвести маркирование. Разбив маркеры на пары, мы нумеруем монеты и в произвольном порядке присваиваем каждой монете пару маркеров Обозначим через M(i, 0), M(i, 1), M(i, 2) , множества монет, где i-й разряд соответствующего правого маркера равен 0, 1 или 2.

После начинаем взвешивания. Последовательно производится n взвешиваний. При i-м взвешивании (i =1,2…) на чаши весов кладутся все монеты множеств M(i, 0) (левая) и M(i, 2)(правая). Результат каждого взвешивания будем обозначать цифрами 0(если перевесила левая чаша), 1(если весы остались в равновесии) и 2(если перевесила правая). Результат i-ого взвешивания будем обозначать . Из цифр составим маркер .

Рассмотрим более подробно.

При каждом взвешивании могут быть три варианта:

Весы остались в равновесии, значит фальшивая монета во множестве M(i, 1), следовательно =1

Перевесила правая чаша, что, в свою очередь, может быть в случаях: когда фальшивая монета тяжелее и лежит на правой чаше, следовательно принадлежит ко множеству M(i, 2), и когда монета легче и она принадлежит ко множеству M(i, 0). В обоих случаях =2.

И «симметричный» предыдущему варианту случай, когда перевешивает левая чаша. Тогда =0.

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

Теперь рассмотрим этот алгоритм на конкретном примере.

У нас имеется 12 монет, среди которых одна фальшивая, предположим, что это монета 6 и она тяжелее остальных. Маркируем монеты и разбиваем их на множества. Как видно из таблицы, множества содержат одинаковое количество монет и не имеют между собой общих элементов.

Теперь проводим мысленное взвешивание. На левой чаше весов множество M(1,0) (монеты 011,010,012 и 001), на правой - M(1, 2) (монеты 200,202,201,220).

Т.к. фальшивая монета присутствует во множестве M(1, 2),то правая чаша перевесит. Однако, не зная типа, нельзя сделать однозначный вывод, и можно взять любой из вариантов. Остановимся на варианте, что правая чаша оказалась тяжелее, значит маркер =2.

Теперь берём монеты, 2-е разряды которых равны 0 и 2. Это монеты 200,202,201,001(левая чаша) и 122,121,120 и 220 (правая чаша). Перевешивает левая чаша весов, значит маркер =0. И по результатам этого взвешивания и предыдущего, устанавливается тип монеты - она тяжелее.

Приходит черёд следующего взвешивания. Выбираются монеты с 3-м разрядом. На левой чаше оказываются монеты 200,010,120 и 220; на правой - 122,202,012 и 112. Так как предположенная монета на правой чаше, то именно она и перевесит. Маркер =2.

Теперь из всех результатов получаем маркер . Он равен 202. Это правый маркер монеты №6 и она тяжелее, о чём стало известно из взвешиваний и из того, что маркер правый.

1.2 Алгоритм решения для случая

В отличии от предыдущего случая, если разбивать монеты на множества произвольно, то возможно неравномерное распределение монет. Поэтому разделение здесь будет другое: в правые маркеры отнесём те, которые получаются друг из друга циклической заменой цифр (т.е. 0-1, 1-2 и 2-0)., парные им - в левые. При этом особо выделяется группа из маркеров (00…01),(11…12) и (22..20).

Разделим монеты во множества, число монет в которых кратны трём, пока это возможно, и замаркируем вышеуказанным образом. Маркеры для оставшихся монет возьмём из группы выделенных маркеров. Если монета одна, то маркер (11…12), если две, то (00…01) и (22..20) соответственно.

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

Однако, в этих случаях, последнее взвешивание происходит иначе.

Случай 1.

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

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

После проводим взвешивания по алгоритму до последнего взвешивания. Перед ним должны были образоваться все цифры маркера, кроме последней. Предположим, что фальшивая монета шестая и она тяжелее. Тогда должен был сформироваться маркер 12.. . У нас всего две монеты с таким началом. Разбиваем их на множества по старому принципу (M(3, 0) и M(3, 2)) и взвешиваем между собой. Перевесит правая чаша и последняя цифра маркера равна 2.

В результате маркер получается 122, а это правый маркер шестой монеты, а так как маркер правый, то монета тяжелее.

Если бы фальшивой была монета №7, то по результатам первых взвешиваний получается маркер 11.. , следовательно, фальшивая монета выявлена, и, чтобы определить её тип, взвешиваем её с любой из оставшихся.

Случай 2

Если же остаток равен двум монетам и фальшивая - одна из них, то более удобным вариантом станет монета с маркером 22..20. Последнее взвешивание производится между этой и любой произвольной монетой. Результат этого взвешивания станет решающим, он определяет как фальшивую монету, так и её тип.

Предположим, что фальшивая монета тяжелее.

Если фальшивая монета среди тех, что в группах, то алгоритм аналогичен предыдущему.

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

1.3 Обоснование оптимальности найденного решения

Для того, чтобы удостовериться в оптимальности метода, проведём мысленный эксперимент.

Занумеруем монеты числами 1,2,…,m и приготовим 2m бумажек, на которых будут написаны все возможные варианты: первая монета тяжелее, первая монета легче, вторая монета тяжелее и т.д. Обозначать результат взвешиваний будем так же, как и прежде : 0, 1 и 2.

Отберём для первого взвешивания монеты, не проводя его. На бумажках, соответствующих монетам, напишем возможные результаты взвешиваний и объединим все бумажки по группам (0, 1 и 2). В любом случае, в одной из групп окажется не меньше, чем бумажек, которые и окажутся под подозрением. Разбиваем эти бумажки на группы и поступаем точно так же, как и в предыдущий раз. В итоге получается, что уже бумажек останутся под подозрением. Аналогично, что после n взвешиваний под подозрением останется бумажек. Следовательно, если , то n взвешиваний не хватит для определения монеты и типа. Поэтому если n взвешиваний достаточно, то должно выполняться неравенство .

Для случая вышесказанного недостаточно. В этом случае после первого взвешивания число бумажек с 0 будет равно числу бумажек с числом 2. Т.к. и тех, и других по p штук, то кол-во бумажек с цифрой 1 будет равна , где p - целое число (т.к. если на правой и левой чаше весов лежит по k монет, то ). Если и , то оставшихся взвешиваний будет недостаточно. Если же и,то т.к. - нечётное число, . Т.к. бумажек с 0 и 2 одинаковое p кол-во, то в общем их будет 2p и соответственно .

Складывая неравенства,* и ** получим

.

Откуда . Итак, если n взвешиваний достаточно, то

2. Решение задач

Задача 1. Дано m монет и известно, что фальшивых среди них - не больше одной. За какое число взвешиваний можно найти фальшивую монету и определить её тип или убедиться, что фальшивой монеты нет?

Решение. Применение метода Дайсона позволяет утверждать, что если ,то n взвешиваний будет достаточно для определения фальшивой монеты и её типа.

Действительно, т.к. фальшивой монеты не больше одной, то рассмотрим два случая:

Одна монета фальшивая. Это _ задача, рассмотренная в первом параграфе работы.

Нет фальшивой монеты

При реализации метода Дайсона при каждом взвешивании в маркер будет добавляться 1. Значит, через n взвешиваний мы получим маркер 11….1, который не соответствует ни одной из взвешиваемых монет? Следовательно, фальшивой монеты нет.

Значит, при тех же n взвешиваниях будет выявлено, что все монеты настоящие.

Задача 2. Известно, что среди m монет одна фальшивая и что она тяжелее остальных. За какое минимальное число взвешиваний можно её выявить?

Решение: Проводим первое взвешивание по алгоритму метода Дайсона и получаем первую цифру в маркере фальшивой монеты. С таким началом есть только у m/3 монет. Отбираем эти монеты, делим на множества , разделив число монет на 2, выделяя остаток отдельно (если он имеется). Т.к. тип монеты известен, то результат взвешивания будет однозначным. И, через n-1 взвешиваний выявится фальшивая монета. Стоит заметить, что такое решение справедливо только тогда, когда .

Заключение

дайсон метод монета счисление

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

В п. 1.1 изложен алгоритм взвешивания (формула). В п. 1.2. самостоятельно были предложены варианты последних взвешиваний в алгоритме Дайсона и приведён конкретный пример.

В §2 приведены решения задач на выявление фальшивой монеты.

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

Список литературы

1. Кноп К. Двенадцать монет. //Компьютера. - 1997. - №51.

2. Шестопал Г. Как обнаружить фальшивую монету. //Квант. - 1979. - №10. - с. 21-25.

Размещено на Allbest.ru