lightbringer, Таки решил попробовать свои силы в выходной.
lightbringer @ 28.10.2019
Ну, джентльмены, раз вам про монеты зашло, то вот предельный случай
Есть 13 монет, одна фальшивая, все настоящие весят одинаково, фальшивка по весу отличается, легче или тяжелее - неизвестно
За три взвешивания на двухчашечных весах без стрелок (невозможно узнать перевес чаши в граммах, только какая тяжелее/легче) установить фальшивую. Выяснять, легче она или тяжелее - не обязательно
И задача со звёздочкой - доказать, что для 14 монет с аналогичным условием трёх взвешиваний не хватает
13 монет.
Также, как и в случае с 12-ю монетами взвесим {1,2,3,4}, {5,6,7,8}. Если веса не равны, то задача сводится к решению с 12-ти монетами. Следующие взвешивания там описаны. Иначе нужно определить фальш среди 9-13.
Взвешиваем {8,9} vs {10,11}.
Если веса равны, то это либо 12, либо 13. Проверить, например, можно взвесом 11vs12. If 11==12 then 13, else 12.
Если не равны, то без ограничения общности положим {8,9} легче {10,11} => либо 9 легче, либо 10 or 11 тяжелее. if (10 == 11) then 9 else if (10 легче 11) => 11 else 10.
Для 14-ти монет ситуация такова. Если использовать разбиение в первом взвешивании по 4 монеты в группе, то нужно определить фальш среди 6-ти монет, что не представляется возможным(можно попробовать разное разбиение с 6-ю монетами и понять, что на конечное взвешивание всегда будет >3 кандидатов на фальш, а за одно взвешивание можно выбрать максимум из 3). Если же сделать начальное разбиение по 5, то также не представляется возможным сделать разбиение таким образом, чтобы осталось <= 3 кандидатов на фальш к 3-му конечному взвешиванию. Грязно, но условно ч.т.д.
1. Взвешиваем 1 и 2 стопки - если они разные:
- допустим первая стопка весит больше, чем вторая, тогда отбрасываем из первой стопки 3 монеты, заменяем их на 3 монеты из второй стопки, а ко второй стопке добавляем 3 монеты из третей стопки (которые точно настоящие). Взвешиваем получившиеся две стопки:
- если вес не изменился, то под вопросом всего 2 монеты, которые не менялись в стопках, просто заменяем одну монету настоящей, взвешиваем и находим фальшивую
- если стопки стали равны, то под вопросом 3 отброшенные монеты из первой стопки, тогда исходя из первого взвешивания фальшивая монета та, которая больше весит. Взвешиваем любые две монеты из тех трех, та, которая больше весит, та и фальшивая. Если монеты равны, то фальшивая третья.
2. Если 1 и 2 стопки равны. Берем третью стопку и делим на два, добавляем к двум монетам 13ую монету. Взвешиваем 3 монеты с любыми 3 настоящими (из 1 и 2 стопок).
- Если вес разный, узнаем вес фальшивой монеты (легче или тяжелее), находим фальшивую монету путем взвешивая двух неизвестных.
- Если вес равен, значит неизвестны оставшиеся две. Меняем одну монету на настоящую и взвешиваем. Находим фальшивую.
Решали вместе с парнем, но большую часть решил он. Если есть ошибка или непонятно написано, пишите.