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)}]
Записан