Комментарии 42
Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.
Не понял, зачем еще два взвешивания, если у нас к этому моменту целая куча эталонных монет?
Вот еще интересная задачка: есть семь мешков с монетами, много монет в каждом мешке, но количество необязательно равное. В одном мешке монеты фальшивые. Вес настоящей монеты 5 грамм, фальшивой — 4. За сколько взвешиваний можно определить мешок с фальшивками, если имеются в распоряжении весы (не две чаши, а электронные весы, показывающие граммы).
Но самая интересная задача, которая мне попадалась — это про цвета глаз жителей племени на необитаемом острове.
Но самая интересная задача, которая мне попадалась — это про цвета глаз жителей племени на необитаемом острове.
Ох уж этот подвох с формулировками
Можно за одно взвешивание определить
Можно за одно взвешивание определить
за 3 взвешивания. нужно просто достать из каждого мешка по монете, потом взвешивать частями (4,3), (2,2) и (2,1), и проверять кратность 5.
Должно быть N<= так как алгоритм может быть не оптимальным.
Например для 12и монет можно найти фальшивую за 3 взвешивания а не за 4.
Например для 12и монет можно найти фальшивую за 3 взвешивания а не за 4.
Для 12 монет существует способ требующий всего 2 взвешивания
Для какой формулировки задачи требуется всего 2 взвешивания?
Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?
В таком случае ваше утверждение неверно. Вы не сможете определить монету, даже если вам сказать легче она или тяжелее настоящей. 2 взвешивания — это всего 9 различных возможных исходов, каждому исходу соответствует ровно один ответ (скажем, монета под номером 3 — фальшивая), а вариантов расположения фальшивой монеты — 12.
Каюсь, был не прав
По ссылке оценка ½(3n – 3), то есть для двух взвешиваний это 6. Если я не так понял, поясните, пожалуйста, как за 2 взвешивания определить фальшивую монету из 12.
Да, все верно. Был неправ. Для 12 монет минимумом, таки, являются 3 взвешивания. Ушёл выправлять знания того смутьяна, который убедил меня в ином.
Кстати, оценка Дайсона для количества монет меньше на одну монету, чем лучшая оценка. В частности, за 3 взвешивания можно определить фальшивую не среди 12 монет максимум, а среди 13 монет.
там же есть пример.
Например, для 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).
Я не спорю с примером. Я говорю, что по оценке Дайсона получается, что для 13 монет нужно 4 взвешивания, когда хватит трёх.
максимальное количество монет для трех взвешиваний – 13,5.
Ваша оценка для первого случая верна, а для второго — нет.
Давайте воспользуемся информационным подходом: в первом случае (когда известно, тяжелее монета или легче) у нас есть A случаев, а каждое взвешивание может дать три исхода (больше, меньше и равно) и в лучшем случае должно уменьшать количество случаев в 3 раза, поэтому, действительно
Если нам неизвестно, тяжелее фальшивая монета или легче, у нас 2A случаев, и оценка должна быть порядка
Что меньше, чем ваша оценка «сверху».
Прежде чем приводить алгоритм, можно ещё улучшить оценку: представим себе, что мы провели все взвешивания, и весы всё время оказывались в равновесии. Даже если в этом случае мы сможем определить фальшивую монету, мы не сможем сказать, тяжелее она или легче (а в задаче это в общем-то и не спрашивается). Таким образом, два случая «сливаются» в один и мы можем, вообще говоря, определить фальшивую за
взвешиваний. Однако, это можно сделать только в одном случае: если у нас в кармане есть заведомо настоящая монета.
Утверждение 1: если у нас в кармане есть заведомо настоящая монета, то мы можем определить за n взвешиваний фальшивую среди
монет.
Доказательство проведём по индукции. База для n=1. За одно взвешивание мы можем определить фальшивую среди
монет. Мы достаём монету из кармана и кладём на одну из чаш весов, а на вторую чашу кладём одну из двух монет среди которых нам нужно определить фальшивку. Если весы в равновесии, то фальшивая монета не участвовала во взвешивании, если не в равновесии — фальшивая та, что на чаше весов.
Допустим, утверждение 1 справедливо для n. Докажем, что за n+1 взвешивание мы сможем определить фальшивую среди
монет. Заметим, что если мы добавим к тестовым монетам нашу монету из кармана, то их количество поделится на три:
Тогда разделим наши монеты на три равные кучки, две кучки положим на чаши весов, одну отложим в сторону. Также убедимся, что монета из кармана попала на правую чашу (а не осталась в стороне). Проведём взвешивание. Если оказалось, что весы в равновесии, то фальшивая монета среди отложенных, и за n взвешиваний мы умеем её находить. Если оказалось, что весы не в равновесии, то мы делаем следующий трюк: склеиваем монеты попарно с правой и левой чаш весов. У нас должно получиться
«толстых» монет. Среди этих «толстых» монет за n взвешиваний мы умеем определять фальшивую (теперь у нас нет монетки из кармана: она склеена, но мы можем изготовить новую «толстую» монету, склеив две настоящие монеты из кучки, отложенной на первом взвешивании). Единственно, за чем нужно следить, чтобы теперь «толстая» монета, «внутри» которой есть монета из кармана, всегда попадала в откладываемую стопку в последующих взвешиваниях.
Когда мы определили, какая из «толстых» монет фальшивая, мы также определили легче она или тяжелее настоящей. Теперь можно вспомнить результат первого взвешивания: если в первом взвешивании перевесила правая чаша, а фальшивая монета легче, то из двух монет, входящих в «толстую» монету, фальшивая та, которая пришла с левой чаши весов (напомню, в каждой «толстой» монете одна монета с правой чаши, а другая — с левой). Лишь в одном случае мы не можем определить, легче фальшивая или тяжелее: когда во всех взвешиваниях весы были в равновесии. Но в этом случае мы знаем, что «внутри» всё время откладываемой «толстой» монеты, которая оказалось фальшивой, одна из монет — это монета из кармана, поэтому фальшивая вторая монета. Таким образом, мы доказали базу индукции и шаг индукции.
Утверждение 2: если у нас нет дополнительных монет, то за n взвешиваний мы можем определить фальшивую среди
монет (на одну меньше, чем в утверждении 1).
Сначала надо пояснить, почему мы не можем достичь максимальной оценки как в утверждении 1. Если у нас нет дополнительной монеты, то мы не можем разделить монет на три кучки. Если мы на чаши весов положим по 
монет, то в случае если весы окажутся не в равновесии, нам не хватит n−1 взвешиваний, чтобы различить 
случаев (а именно столько монет сейчас на чашах весов, и каждая может быть фальшивая). А если мы отложим монет, то оставшееся нечётное количество монет мы не сможем уравновесить.
Если же количество монет на одну меньше, то на две чаши весов положим по
монет, а в сторону отложим монет. Если весы в равновесии, то за оставшиеся взвешивания мы сможем (согласно утверждению 1) определить фальшивую в отложенных монетах (роль монеты из кармана может играть любая монета с уравновешенных весов). Если весы не в равновесии, то мы также склеиваем монетки как в доказательстве утверждения 1 и добавляем виртуальную монету, которая во всех последующих взвешиваниях будет откладываться.
Простите за простыню.
Давайте воспользуемся информационным подходом: в первом случае (когда известно, тяжелее монета или легче) у нас есть A случаев, а каждое взвешивание может дать три исхода (больше, меньше и равно) и в лучшем случае должно уменьшать количество случаев в 3 раза, поэтому, действительно
Если нам неизвестно, тяжелее фальшивая монета или легче, у нас 2A случаев, и оценка должна быть порядка
Что меньше, чем ваша оценка «сверху».
Прежде чем приводить алгоритм, можно ещё улучшить оценку: представим себе, что мы провели все взвешивания, и весы всё время оказывались в равновесии. Даже если в этом случае мы сможем определить фальшивую монету, мы не сможем сказать, тяжелее она или легче (а в задаче это в общем-то и не спрашивается). Таким образом, два случая «сливаются» в один и мы можем, вообще говоря, определить фальшивую за
взвешиваний. Однако, это можно сделать только в одном случае: если у нас в кармане есть заведомо настоящая монета.Утверждение 1: если у нас в кармане есть заведомо настоящая монета, то мы можем определить за n взвешиваний фальшивую среди
Доказательство проведём по индукции. База для n=1. За одно взвешивание мы можем определить фальшивую среди
Допустим, утверждение 1 справедливо для n. Докажем, что за n+1 взвешивание мы сможем определить фальшивую среди
Тогда разделим наши монеты на три равные кучки, две кучки положим на чаши весов, одну отложим в сторону. Также убедимся, что монета из кармана попала на правую чашу (а не осталась в стороне). Проведём взвешивание. Если оказалось, что весы в равновесии, то фальшивая монета среди отложенных, и за n взвешиваний мы умеем её находить. Если оказалось, что весы не в равновесии, то мы делаем следующий трюк: склеиваем монеты попарно с правой и левой чаш весов. У нас должно получиться
Когда мы определили, какая из «толстых» монет фальшивая, мы также определили легче она или тяжелее настоящей. Теперь можно вспомнить результат первого взвешивания: если в первом взвешивании перевесила правая чаша, а фальшивая монета легче, то из двух монет, входящих в «толстую» монету, фальшивая та, которая пришла с левой чаши весов (напомню, в каждой «толстой» монете одна монета с правой чаши, а другая — с левой). Лишь в одном случае мы не можем определить, легче фальшивая или тяжелее: когда во всех взвешиваниях весы были в равновесии. Но в этом случае мы знаем, что «внутри» всё время откладываемой «толстой» монеты, которая оказалось фальшивой, одна из монет — это монета из кармана, поэтому фальшивая вторая монета. Таким образом, мы доказали базу индукции и шаг индукции.
Утверждение 2: если у нас нет дополнительных монет, то за n взвешиваний мы можем определить фальшивую среди
монет (на одну меньше, чем в утверждении 1).Сначала надо пояснить, почему мы не можем достичь максимальной оценки как в утверждении 1. Если у нас нет дополнительной монеты, то мы не можем разделить
Если же количество монет на одну меньше, то на две чаши весов положим по
монет, а в сторону отложим Простите за простыню.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
1. Смотрите, допустим мы произвели взвешивание 4х4, и оказалось, что
Следующее взвешивание, которую нужно сделать (и которое следует из моего решения), это
Если происходит равенство, то все монеты, участвующие во взвешивании настоящие, следовательно фальшивой является толстая монета (4 8), которая не участвовала во взвешивании. Последним взвешиванием мы узнаём легче толстая фальшивая монета или тяжелее.
Если монета
Если вы внимательно прочитаете ещё раз моё решение, то вам не составит труда разобрать все остальные случаи.
2.
>>Здесь должен быть аргумент «нет, ты!» =)
Мы не сможем склеить все случаи, просто не сможем. Если какое-либо из взвешиваний закончится перевесом, то когда мы найдём фальшивую монету мы обязательно будем знать, тяжелее она или легче: для этого достаточно вспомнить на какой стороне весов она лежала (здесь можно придумать задачу про квантовые монеты, где эту несправедливость жизни можно обойти, но наши монеты классические, увы). Таким образом, в одном и ровно в одном случае мы не узнаем ничего про вес фальшивой монеты: когда все взвешивания закончатся равенством. Но это позволяет скостить нам только один вариант. Так что это точная нижняя оценка (и она достижима при наличии настоящей монетки в кармане).
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.
Во-вторых, вы не совсем верно используете «информационный подход»
>>Здесь должен быть аргумент «нет, ты!» =)
Мы не сможем склеить все случаи, просто не сможем. Если какое-либо из взвешиваний закончится перевесом, то когда мы найдём фальшивую монету мы обязательно будем знать, тяжелее она или легче: для этого достаточно вспомнить на какой стороне весов она лежала (здесь можно придумать задачу про квантовые монеты, где эту несправедливость жизни можно обойти, но наши монеты классические, увы). Таким образом, в одном и ровно в одном случае мы не узнаем ничего про вес фальшивой монеты: когда все взвешивания закончатся равенством. Но это позволяет скостить нам только один вариант. Так что
это точная нижняя оценка (и она достижима при наличии настоящей монетки в кармане).НЛО прилетело и опубликовало эту надпись здесь
Так мы и действуем по индукции. Только для индукции нужно пять монет и одна монета из кармана, одна монета у нас виртуальная — мы её будем всё время откладывать, а монету из кармана делаем из заведомо настоящих монет (12 13), например.
Попробуйте сначала по алгоритму 1 (с одной настоящей монетой в кармане) найти за одно взвешивание фальшивую среди двух, потом за два взвешивания — среди пяти, потом проследите как работает индукция для 13 и далее, и вы увидите, что наш алгоритм абсолютно детерменирован. Вы же математик всё-таки, у вас получится.
Попробуйте сначала по алгоритму 1 (с одной настоящей монетой в кармане) найти за одно взвешивание фальшивую среди двух, потом за два взвешивания — среди пяти, потом проследите как работает индукция для 13 и далее, и вы увидите, что наш алгоритм абсолютно детерменирован. Вы же математик всё-таки, у вас получится.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Можно поделить людей на три категории: те кто умеет решать задачи, те кто не умеют и те кто скрывает свое неумение решать задачи нытьем про гравитацию луны.
Вы небось еще когда решаете задачу про «из пункта а в пункт б выехал мотоциклист...» при расчетах учитываете радиус закругления Земли.
Вы небось еще когда решаете задачу про «из пункта а в пункт б выехал мотоциклист...» при расчетах учитываете радиус закругления Земли.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение задач на определение фальшивой монеты взвешиванием 2.0