Декомпозиция и понижение энтропии для программиста на примере головоломки «12 монет, 3 взвешивания найти фальшивую»

[@Sirion]

О, универсальная методика решения задач, ну наконец-то. Решите, пожалуйста, P = NP.

[@ksbes]

Хотя я согласен с вашим общим настроем, но отмечу, что конкретно для этой задачки зависли на 2-й стадии (декомпозиции). Пока доказывают что-то для частных случаев, но «глобальной декомпозиции» пока провести не удалось.

P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)

[@Sirion]

Ну, я просто не люблю неоправданно громкие заголовки. «Полезная эвристика» звучало бы гораздо лучше.

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

[@herodream]

Спасибо за название.

[@Sirion]

Вы упустили случай P=0, N — любое)

[@Vantela]

Мне учительница математики помню рассказывала.
Она подрядилась быть репетитором для старшекласника. Подготовка к поступлению в ВУЗ.
И вот на первом занятии она дает задает ему вопрос:
как можно преобразовать
six^2 x/cos^2 x

Получает ответ:
six^2 x/cos^2 x =
six x/cos x =
sin/cos
in/co

На этом месте она поняла, что работы… предстоит много.

[@Vantela]

Блин. Действительно опечатался.
Но к концу сумел исправиться))

Настолько не знать, что такое тригонометрические функции — это надо было постараться.:)

Сокращать дроби тоже не умеет, кстати. «Квадраты» так не сокращают.

[@FGV]

За 3 взвешивания необходимо найти фальшивую монетку и определить легче она или тяжелее.

Решение не до конца.

[@basilio]

Хм, я уверен, что я тоже это видел, но похоже автор уже изменил условия чтобы они соответствовали его решению…
В любом случае, оригинальная задача показалась мне интереснее и я ее, кажется, решил:

Решение

Как найти фальшивую монетку и определить легче она или тяжелее.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.

image upload

[@JC_IIB]

del

[@CrzyDocTI]

В любом случае из условий

Неизвестно легче или тяжелее

— соответственно и относительный вес монеты будет найден.

[@basilio]

К сожалению, нет. Я не буду проверять все варианты, но очевидно, что алгоритм не работает на примере 12 монеты. В посте решение о том, что она фальшивая принимается в результате цепочки, в которой 12 монета вообще ни разу не оказывается на весах — 1234 = 5678, 9 = 10, 10 = 11. В данном случае она может быть легче, тяжелее, и даже точно такого же веса.

[@JC_IIB]

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

[@Vantela]

А если фальшивая монета легче чем оригинал?
UPD: О! Исправились:) Но не до конца.
И я тогда дополню.
Не известно же легче фальшивка или тяжелее)

[@Sirion]

Стоило потратить ещё минуту на внимательное чтение условия) вы решили не ту задачу.

[@Loki3000]

А почему из более тяжелой кучи? Может фальшивая монета легче?

[@JC_IIB]

Да, это я косякнул — не учел, что неизвестно, легче монетка или тяжелее.

[@RigelNM]

Извините, в вашем решении так и не понял, как вы за одно взвешивание выделили целевую кучку из трех?

[@RigelNM]

Я может «не догоняю», но во втором случае почему вы разбили все группы на разные веса? Должно ведь быть >,0,0 или <,0,0.

[@boxvk257]

Раньше думал, эта задача имеет единственное решение. Теперь появилась новая задача — сколько решений имеет эта задача?

[@alexs0ff]

DEL

[@basilio]

На самом деле выше я пропустил две ветви в самом конце решения. Вот тут полное дерево:

Решение

Как найти фальшивую монетку и определить легче она или тяжелее.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.

[@ksbes]

Ну допустим я злоумышленник и подложил «облегчённую» монету №7 где для неё вариант?
И тут вообще только 16 вариантов из 24 (12* L-H) возможных.

Или я что-то упустил?

[@basilio]

Похоже что упустили. Если 7 (или 5, 6 или 8) монета легче сработает блок "… swap 1234 with 5678". Алгоритм то один и тот же на самом деле, я решил сэкономить место и не расписывать оба варианта. Просто поменяйте кучки 1234 и 5678 местами и продолжайте, теперь легкая монета будет иметь индекс 3. Прошу прощения за неочевидность.

[@ksbes]

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

[@basilio]

Я пока знаю только одно решение, мое. Решение автора я не считаю решением первоначальной задачи, так как оно не отвечает на вопрос легче или тяжелее?
Вы знаете другие решения? Поделитесь?

[@p_fox]

Решение автора отвечает на вопрос "легче или тяжелее" на втором-третьем взвешивании, в зависимости от результатов взвешивания. Единственное исключение — когда после первого взвешивания, фальшивая монета оказывается в третьей группе, и в последующие 2 взвешивания она не попадает. Тогда да, ее вес неизвестен.

[@Habra_nik]

Три, как минимум -> mathforum.org/library/drmath/view/55618.html. Мне второе больше всех нравится, хотя (во всех) коряво то, что монеты по условию выглядят одинаково, а если их пронумеровать, то выглядеть одинаково они перестанут.

[@AmartelRU]

Вместо сравнения 1 2 5 6 vs 4 8 11 12 достаточно сравнить 5 6 12 vs 4 7 8. И «тройки» сравнивать чуть легче, чем «четвёрки», и «лёгкость» фальшивой монеты более однородно по случаям распределится. У Вас в каждом из трёх случаев она может быть как легче, так и тяжелее нормальной. А в данном варианте в случае "=" монета всегда H, при сохранении неравенства ">" монета всегда L, и только при смене неравенства на "<" будут смешанные варианты.

[@side2k]

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

[@kvaks]

А почему нельзя так?
1 взвешивание 6vs6
2 взвешивание 3vs3
3 взвешивание 1vs1 и если равны то оставшаяся?

[@AmartelRU]

Потому что неизвестно, является ли фальшивая монета легче или тяжелее настоящей. Вы взвешиваете 6 vs 6 и одна группа монет тяжелее другой. Но что это значит? В тяжёлой группе есть тяжёлая фальшивая монета или же в лёгкой группе — лёгкая фальшивая монета? Ноль полезной информации.

[@mikeus]

2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».



Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:

• Равны. Фальшивая монета находится среди чисел: 6 7 8.

А двенадцатая монета куда подевалась?

[@p_fox]

Лежит в кармане. Она не фальшивая, в решении не участвует.

[@herodream]

Посмотрите внимательно 1-ый случай

1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.

[@mikeus]

Ой, в данном случае с 9 по 12 — монеты настоящие.

[@herodream]

Верно

[@alf88]

Поставило в тупик «3 взвешивания» а в решении приводится далеко не 3!

[@p_fox]

Да ну? А сколько?

[@nronnie]

Хм. А решение-то разве верное?

Неизвестно легче или тяжелее.

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

UPD. А, впрочем, понял, да.