Меню

Имеются чашечные весы одна монета фальшивая



Имеются чашечные весы одна монета фальшивая

Имеются чашечные весы без гирь и 3 одинаковые по внешнему виду монеты. Одна из монет фальшивая, причём неизвестно, легче она настоящих монет или тяжелее (настоящие монеты одного веса). Сколько надо взвешиваний, чтобы определить фальшивую монету? Решите ту же задачу в случаях, когда имеется 4 монеты и 9 монет.

Подсказка

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

Решение

Если у нас 3 монеты, достаточно двух взвешиваний. Кладём на каждую чашку весов по одной монете. Если весы не в равновесии, значит, та монета, которая осталась, — настоящая. Кладём её на весы с любой из остальных и сразу определяем, какая из них фальшивая. Если же весы в равновесии, значит, фальшивая монета та, которая осталась, и вторым взвешиванием можно даже определить, легче она или тяжелее, чем настоящие. Если у нас 4 монеты, опять достаточно двух взвешиваний. Разделим наши монеты на две кучки по 2 монеты и положим одну из кучек на весы — по монете на каждую чашку. Если весы в равновесии, то обе монеты на них настоящие. Если весы не в равновесии, то обе монеты на столе настоящие. Итак, теперь мы знаем, в какой кучке лежит фальшивая монета. Положим на одну чашку весов монету из кучки, где обе настоящие, на вторую — монету из кучки, где фальшивая. Если при этом весы будут в равновесии, значит, фальшивая монета осталась на столе, а если не в равновесии, значит, мы положили её на весы (в этом случае мы даже узнаем, легче она или тяжелее). Если у нас монет 9, потребуется три взвешивания. Делим монеты на три кучки по 3 монеты и кладём две из этих троек на две чашки весов. Если весы в равновесии — в оставшейся кучке находится фальшивая монета, и за два взвешивания (как это показано в случае 1 настоящей задачи) мы определим фальшивую монету. Итак, всего нам понадобится три взвешивания. Пусть теперь весы не будут в равновесии, значит, одна из кучек на весах — с фальшивой монетой, а в той кучке, которая осталась, только настоящие. Кладём на весы эту кучку и любую из первых двух. Так мы найдём не просто кучку с фальшивой монетой, но и сразу определим, легче эта монета или тяжелее настоящих. Мы проделали два взвешивания, но зато теперь уже только одним взвешиванием (как показано в случае 1 задачи 49) можем определить фальшивую монету. Итак, всего нам понадобится три взвешивания.

Ответ

Источники и прецеденты использования

книга
Автор Козлова Е.Г.
Название Сказки и подсказки
задача
Номер 81

Проект осуществляется при поддержке и .

Источник

Имеются чашечные весы одна монета фальшивая

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

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

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

Поставим теперь задачу в общем виде.

Имеется m ≥3 одинаковых по виду монет. Все монеты, кроме одной, имеют одинаковый вес, а одна отличается от них по весу, но неизвестно, в какую сторону. Каким наименьшим числом взвешиваний на чашечных весах без гирь можно найти эту монету и выяснить её тип ? 1

Эта задача более тридцати лет назад привлекла к себе внимание многих математиков, главным образом в Англии и США. В 1945 году в английском журнале «The Mathematical Gazette», похожем по своему направлению на «Квант», появилось решение этой задачи. Его автор Р. Л. Гудстейн впоследствии стал известным специалистом в области математической логики.

Читайте также:  1 shilling 1795г монета

Гудстейн указал метод определения фальшивой монеты и её типа за n взвешиваний, n ≥3 , если число монет

(заметьте, что для трёх взвешиваний число монет не превышает двенадцати). Однако оказалось, что для n >3 его решение не является лучшим: за n взвешиваний можно выделить фальшивую монету и определить её тип из большего числа монет:

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

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

В последующие годы были напечатаны другие решения этой задачи 2 , а метод Дайсона был незаслуженно забыт.

Поэтому интересно рассказать о нём подробно.

Всё решение Дайсона можно разбить на два этапа.

А Если

то для выделения одной фальшивой монеты из общего числа m монет и определения её типа достаточно произвести n взвешиваний.

Б Если

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

Рассмотрим каждый этап в отдельности.

Пусть число монет

Рассмотрим все «троичные числа» (наборы из цифр 0, 1, 2) Их 3 n . Используем их для маркировки монет следующим образом: в качестве маркеров возьмём все эти числа, за исключением трёх, состоящих из одинаковых цифр:

«Построим» все маркеры в пары: в одну пару «поставим» два дополнительных маркера — таких, у которых цифры соответствующих разрядов в сумме составляют 2 (другими словами, дополнительными будут те маркеры, сумма которых равна

Назовём маркер правым , если в нём первая слева пара неравных цифр — 01, 12 или 20. В противном случае маркер будем называть левым . Очевидно, в каждой паре дополнительных маркеров один всегда будет правым, другой — левым.

Заметим, что число пар маркеров как раз равно общему числу монет m . Перенумеруем монеты номерами от 1 до m и произвольно сопоставим каждой монете одну пару маркеров. Например, 12 монет можно «замаркировать» так, как показано в таблице.

Номер
монеты
Левый
маркер
Правый
маркер
1 211 011
2 100 122
3 022 200
4 212 010
5 101 121
6 020 202
7 210 012
8 102 120
9 021 201
10 221 001
11 110 112
12 002 220

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

Легко видеть, что число монет в каждом из множеств и одинаково и что эти множества не имеют общих элементов (см., например, таблицу).

Метод взвешивания монет, придуманный Дайсоном, состоит в следующем:

Производится последовательно n взвешиваний монет.

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

Из цифр l 1 , l 2 , . l n составим маркер 3

Оказывается, l — маркер фальшивой монеты F и если l — правый маркер, то F тяжелее остальных монет, а если l — левый маркер, то F легче остальных монет.

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

Если весы остались в равновесии, то фальшивой монеты на них нет, следовательно, она — в множестве Но это означает, что разряд её правого (и левого) маркера равен 1, на что и указывает результат взвешивания

Если одна из чашек весов перевесила, то фальшивая монета лежит на весах. Пусть, например, перевесила правая чашка, т.е. Этот результат возможен в двух случаях:

— фальшивая монета лежит на правой чашке (тогда она тяжелее остальных монет), значит, она находится во множестве разряд её правого маркера равен 2, следовательно, результат взвешивания совпадает с разрядом её правого маркера;

— фальшивая монета лежит на левой чашке (тогда она легче остальных монет), значит, она находится во множестве следовательно, разряд её правого маркера равен 0 и результат взвешивания совпадает с разрядом её левого маркера.

Совершенно аналогичен «симметричный» случай, когда перевесит левая чашка весов

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

Интересно отметить, что тип монеты, как правило, определится раньше, чем произведены все взвешивания, — как только в процессе формирования маркера l появятся две различные цифры.

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

Например, для 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).

Коротко наметим метод Дайсона для случая

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

В каждой группе окажется по три правых маркера и три левых маркера. Группу, содержащую правые маркеры выделим особо. Разобьём монеты на группы по три, пока это возможно, и замаркируем их следующим образом. Монетам из одной группы сопоставим пары маркеров из одной группы, а для остатка, если он есть, используем пары маркеров из выделенной группы. Если останется одна монета, не вошедшая в тройки, то сопоставим ей правый маркер а если две, — то правые маркеры и (и соответствующие левые маркеры).

При такой маркировке первые n –1 взвешиваний производятся по старым правилам. Как производить последнее взвешивание, сообразите самостоятельно.

Метод Дайсона описан. Убедимся теперь, что он в определённом смысле является наилучшим. А именно, покажем, что если из m монет можно выделить n взвешиваниями фальшивую монету и определить её тип, то Разумеется, мы не будем учитывать возможного «везения»: при нём для определения фальшивой монеты из любого числа монет может хватить и двух взвешиваний.

Итак, предположим, что n взвешиваний достаточно.

Занумеруем монеты числами 1, m и приготовим 2 m бумажек. Напишем на них все возможные варианты: первая монета легче, первая монета тяжелее, вторая монета легче и т.д. Ясно, что при этом все 2 m бумажек окажутся использованными и ни один из возможных вариантов не будет упущен. Будем обозначать, как мы условились выше, результат взвешивания цифрами 0, 1 или 2. Каждое взвешивание показывает, что часть возможных ответов не подходит, а часть — остаётся под подозрением. Отберём монеты для первого взвешивания. Не производя его фактически, напишем на каждой из бумажек тот результат первого взвешивания, который оставляет её под подозрением. Ясно, что на каждой бумажке будет написана одна из цифр 0, 1 или 2. Таким образом, все бумажки будут разбиты на три группы. Поэтому в наиболее многочисленной группе окажется не меньше бумажек. Значит, как бы мы ни организовывали первое взвешивание, может оказаться, что после него под подозрением останутся не меньше бумажек.

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

Но это ещё не всё! Мы не разобрались ещё со случаем (чётное число 2 m не может равняться ни ни Для него изложенных выше соображений недостаточно.

Рассмотрим более внимательно первое взвешивание. Ясно, что число бумажек, на которых написана цифра 0, равно числу бумажек, на которых написана цифра 2. Пусть тех и других — по p штук, тогда на бумажках будет написана 1.

Заметим, что p — чётное число. Действительно, если на левой и правой чашке весов лежит по k монет, то Если p или больше то по рассмотренному для определения нужной бумажки может не хватить оставшихся взвешиваний. Если же и то, поскольку — число нечётное, Но тогда Итак, если n взвешиваний достаточно, то

В заключение — несколько задач, которые могут быть решены методом Дайсона.

Источник

Решение задач на определение фальшивой монеты взвешиванием 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 — остаток.

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

При первом взвешивании будут сравниваться две группы: правая (ПГ) — 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
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
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 — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.

Источник