Смит, я попытаюсь объяснить так, чтобы решение не вызывало бы недоумения и не выглядело бы как фокус-покус. Но надо набраться терпения и дочитать всё
1. Рассмотрим традиционный подход, т.е. без допущения возможной ошибки весов.
Такой подход базируется на дереве решений, причём решение на следующее взвешивание (измерение) принимается по результату предыдущего.
Напр. раскладываем на 3 кучки, 2 взвешиваем -> по рез-ту выбираем кучку, содержащую кандидата и проделываем с ней аналогичное.
Каждое взвешивание уменьшает число кандидатов в 3 раза. Здесь всё ясно.
2. Данный подход ясен и прозрачен, но, увы, не подходит для нашего случая.
Почему?
Показать скрытый текст
Если мы вынуждены допускать что весы могут один раз ошибиться, мы вынуждены принимать решение по результату нескольких независимых измерений, а не одного, - чтобы мы могли судить по кандидату ТОЛЬКО по результату такого ПАКЕТА взвешиваний, будучи уверенным что сама последовательность взвешиваний в таком пакете НЕ ЗАВИСИТ от результатов самих одиночных взвешиваний. Именно такой подход даёт НЕЗАВИСИМОСТЬ одного взвешивания от другого. Иначе ошибка весов при предыдущем взвешивание ломала бы все рез-ты последующих.
Если с этим моментом понятно, пойдём дальше.
Показать скрытый текст
3. Вернёмся опять к "безошибочным" весам и обратим внимание на следующий момент.
Когда мы разделили монеты на 3 кучки и по результату одного взвешивания получили кучку в которой должна быть фальшивая монета, чтобы проделать с этой кучкой то же самое, то есть разделить эту кучку на 3 части и положить 2 из них на весы, НИЧТО нам не мешает дополнить две эти кучки любым (но равным, естественно) кол-вом монет из отвергнутых в предыдущем взвешивании куч - это не повлияет на результат!!!
Это - основной момент подхода. На этом базируется вся идея.
Если мы, например, ЗАРАНЕЕ разделим все монеты на 3 кучи и напишем на каждой монете первой кучи "Левая", второй - "Правая", а 3-й - "Резерв", затем разделим каждую кучку на 3 и допишем на каждой монете под первым словом "Левая", "Правая" или "Резерв" и так далее, то каждая монета в конце концов приобретёт К слов, в которых будут чередоваться эти слова.
Что это нам даёт?
Показать скрытый текст
4. Первым взвешиванием мы взвешиваем, как и планировали, кучи, в которых самые верхние слова - "Левая" и "Правая" - левые на левую чашку, правые - на правую.
Теперь, допустим, перевесила бы правая чашка. Что бы мы сделали при традиционном подходе? разделили бы её на 3 части и продолжили. Правильно?
Но ничто нам не мешает дополнить наши маленькие кучки ещё двумя кучками из отвергнутых куч? Ничего, верно?
А если бы было бы равновесие при первом взвешивании?
Мы бы выбрали 3-ю кучку, разделили бы её на 3 части и дополнили бы маленькими кучками из отвергнутых куч.
И чем бы отличались бы выбранные монеты в случае перевеса правой чашки от случая равновесия? Да ничем.
В обоих случаях было бы:
1-е взвешивание: на левой чашке - куча монет с верхним словом "Левая", на правой - "Правая".
2-е взвешивание: на левой часке - куча монет со словом "Левая" вторым сверху, а на правой - со словом "Правая" вторым сверху. При этом 1/3 монет в левой чашке будет иметь первым словом "Правая", 1/3 - "Левая" и 1/3 - "Резерв".
То же будет и на правой чашке.
5. Другими словами, мы можем разделить монеты ЗАРАНЕЕ и тупо взвешивать НЕЗАВИСИМО от результатов предыдущих взвешиваний.
И при этом мы получим АБСОЛЮТНО тот же результат, который бы получили на "безошибочных" весах, действуя традиционным (по дереву) способом.
6. Таким образом я продемонстрировал подход ЭКВИВАЛЕНТНЫЙ традиционному подходу, дающий СТОЛЬКО же взвешиваний, НО обеспечивающий НЕЗАВИСИМОСТЬ ввешиваний.
Очевидно, что вместо "Левая"/"Правая"/"Резерв" можно писать 0/1/2 и не сверху вниз, а слева направо, что и предлагал Илья.
7. Если мы результаты взвешиваний тоже будем записывать как 0/1/2, то получим К-разрядное слово полностью идентифицирующее фальшивую монету - это слово будет ПОЛНОСТЬЮ СОВПАДАТЬ с номером одной и ТОЛЬКО одной монеты.
8. Что бы мы делали с этим рез-том, если бы не надо было допускать одиночной ошибки весов? Да ничего. Это было бы нашим решением.
А что мы будем делать сейчас?
Показать скрытый текст
9. Да всё - просто. Что значит возможность одиночной ошибки?
Это значит, что полученный К-разрядный результат взвешивания может отличаться от истинного ТОЛЬКО ОДНИМ разрядом.
Что это значит?
Допустим мы получили результат 102 при развешивании наших 3^3 = 27 монет.
Каждый разряд (но только ОДИН!!!) может врать. Это нам даст монету с номером 102 (основной кандидат) и ещё 2*3 монет с номерами: 101, 100, 112, 122, 002, 202.
Вместе с нашей монетой - всего 7. (Для 3^10 монет было бы 2*10 + 1 монета).
10. С этими монетами мы проделываем следующее - выбираем 1 из 6 для 27 монет или 1 из 20 для 3^10 монет. Основных кандидатов мы не взвешиваем!!!
11. Полученного при дополнительных взвешиваниях кандидата взвешиваем с основным и выбираем "достойного"
Итого: для 3^10 монет имеем: 10 + 3 + 1 = 14.
12. А теперь я покажу трюк, когда одно взвешивание можно сэкономить.
Показать скрытый текст 13. Дело в том, что 2-й пакет взвешиваний (дополнительный) несколько отличается от первого. По идее, он не должен давать неравенств, если 1-й пакет был без ошибки. Поэтому, если на каком-то этапе оказалось неравенство, то:
а) либо ошибка в 1-м пакете,
б) либо ошибка в ДАННОМ конкретном взвешивании.
В любом случае после 1-го неравенства мы можем утверждать, что ПОСЛЕ ЭТОГО МОМЕНТА ошибок взвешивания быть НЕ МОЖЕТ, ошибка УЖЕ произошла.
А это значит, что после этого момента мы можем "работать" традиционно.
Поэтому мы УЖЕ можем добавить к "плохой" кучке нашего основного кандидата и продолжить работать с такой обновлённой кучкой, ЗНАЯ, что результат будет ОКОНЧАТЕЛЬНЫЙ.
Поэтому мы заинтересованы зафиксировать неравенство (если оно случится) тогда, когда на "плохой" чашке - НЕ степень 3-ки.
В этом случае мы можем добавить нашего основного кандидата к монетам в "плохой" чашке, он нам не увеличит общее число взвешиваний (степень 3-ки не была перейдена)
Для этого мы заинтересованы зафиксировать неравенство КАК МОЖНО РАНЬШЕ - больше свободы манёвра.
14. Поэтому в 1-м из дополнительных взвешиваний мы берём 8 и 8, а оставляем 4.
Если произошло неравенство, то мы продолжаем работу с 9 монетами, добавив к "плохим" нашего основного кандидата из первого пакета.
При этом результат дальнейших взвешиваний - ОКОНЧАТЕЛЬНЫЙ:
- если ошибка в первом пакете, то добавленный основной кандидат не изменит рез-та
- если ошибка в этом нашем взвешивании, то больше ошибок не произойдёт и мы опять получим нашего основного кандидата, т.е. С ЭТОГО МОМЕНТА результат дополнительного пакета будет окончательным и нам НЕ НАДО будет сравнивать одного кандидата с другим.
15. В случае равенства при 1-м доп. взвешивании мы делим оставшиеся 4 монеты ПОПОЛАМ - 2 и 2 и делаем 2-е взвешивание.
При равенстве во 2-м взвешивании - всё, мы закончили, основной кандидат 1-го пакета и есть фальшивая монета.
В случае нерав-ва - добавляем к плохой куче нашего кандидата и определяем одного из 3-х последним взвешиванием.
Итого: для 3^10 монет требуется 10 + 3 = 13 взвешиваний.
16. Но при другом кол-ве монет это не всегда возможно.
Например при 3^4 монетах после 1-го пакета из 4-взвешиваний мы имеем 1-го основного кандидата и 2*4 = 8 потенциальных. 8 монет мы можем поделить лишь как 3-3-2 и в случае неравенства не сможем добавить основного кандидата без увеличения кол-ва взвешиваний. Поэтому нам потребуется: 4 + 2 + 1.
Поэтому общая формула для М монет: число взвешиваний Х для М монет:
Х = ([log3M]+([1- {log3M}] + [log3(2log3M+1)] +[1-{log3(2log3M)}]
