vikodin17 ноя 2014 в 20:21

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

3 мин

235K

Алгоритмы *

+16

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

Eleon 18 ноя 2014 в 00:42

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

Не понял, зачем еще два взвешивания, если у нас к этому моменту целая куча эталонных монет?

Jokerjar 18 ноя 2014 в 04:52

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

Но самая интересная задача, которая мне попадалась — это про цвета глаз жителей племени на необитаемом острове.

phikus 18 ноя 2014 в 05:48

Ох уж этот подвох с формулировками
Можно за одно взвешивание определить

AraneusAdoro 18 ноя 2014 в 05:59

Вы не поверите, но ответ таки и есть «за одно взвешивание». Решение несложное, не буду спойлерить.

zorgzerg 18 ноя 2014 в 06:12

Аааа… можно )))) не ожидал такого коварства ))

phikus 18 ноя 2014 в 06:30

Ок, суть я понял, осталось подобрать коэффициенты для случая когда в мешках меньше миллиона монет

Mrrl 18 ноя 2014 в 06:53

Или для случая, когда может быть меньше семи монет?

zorgzerg 18 ноя 2014 в 06:10

за 3 взвешивания. нужно просто достать из каждого мешка по монете, потом взвешивать частями (4,3), (2,2) и (2,1), и проверять кратность 5.

mekegi 18 ноя 2014 в 07:09

Нет, там нужно только одно взвешивание.

Спойлер

1 монета с первого мешка, 2 со второго… 7 с последнего седьмого мешка. Кладем на весы все эти монеты, весы показывают x грамм.
далее:
(1+2+3+4+5+6+7)*5 — x = y
где y и будет номером мешка с фальшивыми монетами

zorgzerg 18 ноя 2014 в 07:11

Окак… А граждане вот сверху намекали на формулировку, выделяя слово «Можно». Я чего то решил, что взять монету из любого мешка и взвесить ее. Если 4 гр. попалось с первого раза, то действительно МОЖНО! )))

НЛО прилетело и опубликовало эту надпись здесь

zorgzerg 18 ноя 2014 в 11:58

Угу, мне сверху уже объяснили :)

staker 18 ноя 2014 в 06:30

Должно быть N<= так как алгоритм может быть не оптимальным.

Например для 12и монет можно найти фальшивую за 3 взвешивания а не за 4.

domix32 18 ноя 2014 в 08:03

Для 12 монет существует способ требующий всего 2 взвешивания

lemelisk 18 ноя 2014 в 08:41

Для какой формулировки задачи требуется всего 2 взвешивания?

domix32 18 ноя 2014 в 08:58

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

lemelisk 18 ноя 2014 в 09:05

В таком случае ваше утверждение неверно. Вы не сможете определить монету, даже если вам сказать легче она или тяжелее настоящей. 2 взвешивания — это всего 9 различных возможных исходов, каждому исходу соответствует ровно один ответ (скажем, монета под номером 3 — фальшивая), а вариантов расположения фальшивой монеты — 12.

domix32 18 ноя 2014 в 09:16

Каюсь, был не прав

p53 18 ноя 2014 в 08:42

По ссылке оценка ½(3ⁿ – 3), то есть для двух взвешиваний это 6. Если я не так понял, поясните, пожалуйста, как за 2 взвешивания определить фальшивую монету из 12.

domix32 18 ноя 2014 в 09:15

Да, все верно. Был неправ. Для 12 монет минимумом, таки, являются 3 взвешивания. Ушёл выправлять знания того смутьяна, который убедил меня в ином.

p53 18 ноя 2014 в 10:34

Кстати, оценка Дайсона для количества монет меньше на одну монету, чем лучшая оценка. В частности, за 3 взвешивания можно определить фальшивую не среди 12 монет максимум, а среди 13 монет.

domix32 18 ноя 2014 в 10:44

там же есть пример.

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

p53 18 ноя 2014 в 10:47

Я не спорю с примером. Я говорю, что по оценке Дайсона получается, что для 13 монет нужно 4 взвешивания, когда хватит трёх.

domix32 18 ноя 2014 в 11:02

максимальное количество монет для трех взвешиваний – 13,5.

alcr 18 ноя 2014 в 11:37

Если монет 13.5, то я без взвешиваний покажу фальшивую :)

domix32 18 ноя 2014 в 14:14

Это следует из формулы

m=½(3ⁿ – 3) = (3³ — 3)/2 = 13.5

т.е. либо 13, а возможно и все 14 монет можно взвесить за три взвешивания. А если принять, что половинка монеты существует где-нибудь в 4D+ измерении, то взвешивать все равно придется.

p53 18 ноя 2014 в 15:10

Простите мне мою неправославную арифметику, но мне кажется, что (3³–3)/2 = (27–3)/2 = 24/2 = 12

domix32 19 ноя 2014 в 07:02

Действительно. Снова косячу. Интересно, что не так с Дайсоном в таком случае.

p53 18 ноя 2014 в 08:32

Ваша оценка для первого случая верна, а для второго — нет.

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

Если нам неизвестно, тяжелее фальшивая монета или легче, у нас 2A случаев, и оценка должна быть порядка
$n=\lceil \log_32A\rceil \le \lceil \log_3A+1\rceil=\lceil \log_33A\rceil$
Что меньше, чем ваша оценка «сверху».

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

взвешиваний. Однако, это можно сделать только в одном случае: если у нас в кармане есть заведомо настоящая монета.

Утверждение 1: если у нас в кармане есть заведомо настоящая монета, то мы можем определить за n взвешиваний фальшивую среди $A=\frac{3^n+1}{2}$ монет.

Доказательство проведём по индукции. База для n=1. За одно взвешивание мы можем определить фальшивую среди $A=\frac{3^n+1}{2}=2$ монет. Мы достаём монету из кармана и кладём на одну из чаш весов, а на вторую чашу кладём одну из двух монет среди которых нам нужно определить фальшивку. Если весы в равновесии, то фальшивая монета не участвовала во взвешивании, если не в равновесии — фальшивая та, что на чаше весов.

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

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

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

Сначала надо пояснить, почему мы не можем достичь максимальной оценки как в утверждении 1. Если у нас нет дополнительной монеты, то мы не можем разделить $\frac{3^n+1}{2}$ монет на три кучки. Если мы на чаши весов положим по $\frac{3^{n-1}+1}{2}$ монет, то в случае если весы окажутся не в равновесии, нам не хватит n−1 взвешиваний, чтобы различить $3^{n-1}+1$ случаев (а именно столько монет сейчас на чашах весов, и каждая может быть фальшивая). А если мы отложим $\frac{3^{n-1}+1}{2}$ монет, то оставшееся нечётное количество монет мы не сможем уравновесить.

Если же количество монет на одну меньше, то на две чаши весов положим по

монет, а в сторону отложим $\frac{3^{n-1}+1}{2}$ монет. Если весы в равновесии, то за оставшиеся взвешивания мы сможем (согласно утверждению 1) определить фальшивую в отложенных монетах (роль монеты из кармана может играть любая монета с уравновешенных весов). Если весы не в равновесии, то мы также склеиваем монетки как в доказательстве утверждения 1 и добавляем виртуальную монету, которая во всех последующих взвешиваниях будет откладываться.

Простите за простыню.

НЛО прилетело и опубликовало эту надпись здесь

p53 21 ноя 2014 в 13:06

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.

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

>>Здесь должен быть аргумент «нет, ты!» =)
Мы не сможем склеить все случаи, просто не сможем. Если какое-либо из взвешиваний закончится перевесом, то когда мы найдём фальшивую монету мы обязательно будем знать, тяжелее она или легче: для этого достаточно вспомнить на какой стороне весов она лежала (здесь можно придумать задачу про квантовые монеты, где эту несправедливость жизни можно обойти, но наши монеты классические, увы). Таким образом, в одном и ровно в одном случае мы не узнаем ничего про вес фальшивой монеты: когда все взвешивания закончатся равенством. Но это позволяет скостить нам только один вариант. Так что

это точная нижняя оценка (и она достижима при наличии настоящей монетки в кармане).

НЛО прилетело и опубликовало эту надпись здесь

p53 21 ноя 2014 в 14:47

Так мы и действуем по индукции. Только для индукции нужно пять монет и одна монета из кармана, одна монета у нас виртуальная — мы её будем всё время откладывать, а монету из кармана делаем из заведомо настоящих монет (12 13), например.

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

НЛО прилетело и опубликовало эту надпись здесь

mekegi 20 ноя 2014 в 14:33

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

Mrrl 20 ноя 2014 в 16:04

Вы небось еще когда решаете задачу про «из пункта а в пункт б выехал мотоциклист...» при расчетах учитываете радиус закругления Земли.

Когда этот мотоциклист едет на юг, потом на восток, а потом на север, то ничего другого не остаётся :(

НЛО прилетело и опубликовало эту надпись здесь

AraneusAdoro 21 ноя 2014 в 00:02

Можно поподробнее, что такого интересного в этой формуле?

НЛО прилетело и опубликовало эту надпись здесь

Зарегистрируйтесь на Хабре, чтобы оставить комментарий