Пятничные задачки для brain разминки ;)

← →
SergP. (2006-06-19 21:52) [80]

6. Еще такой вариант есть:

После n-взвешиваний мы можем выделить 59049*(2*n+1)/(3^n) монет среди которых наверняка есть фальшивая.

Теперь решая уравнение 59049*(2*n+1)/(3^n)=1 находим что n=13

правда есть небольшие сомнения касающиеся методики взвешивания при количестве взыешиваний более 10

← →
SergP. (2006-06-19 21:56) [81]

2 default Вобщем насчет 12 взыешиваний я не прав, но почему-то у меня присутствует уверенность что кол-во взвешиваний не может быть 18, а в крайнем случае, если теоретическое решение [79] с ответом 13 не верно, то ИМХО максимум - это 14, но не более...

← →
SergP. (2006-06-19 21:57) [82]

> если теоретическое решение [79]

Имелось ввиду [80]

← →
SergP. (2006-06-19 22:08) [83]

> После n-взвешиваний мы можем выделить 59049*(2*n+1)/(3^n)
> монет среди которых наверняка есть фальшивая.

Вобщем я могу доказать правильность этой формулы для любого числа взвешиваний от 0 до 10, (а также могу показать что она действует на небольшом кол-ве монет ( например 9)), и склонен думать что она должна быть верной и для 11-13 взвешиваний. Но как-то пока не могу себе представить как это будет выглядеть практически. Видимо мозги хреново работают...

← →
default © (2006-06-19 23:04) [84]

SergP. (19.06.06 22:08) [83]
будет свободное время тоже буду думать, задача видится очень интересной
надо её доканать
насчёт 18 сильно не обращай внимания
единственное, может хоть на что-то такие соображения натолкнут(на них я раньше основывался):
допустим мы имеем число монет являющееся степенью двойки:
разбиваем число монет на две кучки(знаем что хотя бы в одной из кучек - фальшивка), действуем по существу всё по той же схеме из [4], но
если в случае деления на три кучки нужно каждый раз делать контрольное взвешивание(если идти по старой схеме взвешивания) до того как весы соврут(чтобы не уйти по ложному пути), то в случае двух кучек контрольное взвешивание делать после каждого взвешивания не нужно

допустим на каком-то из взешиваний весы обманули и мы перешли к работе с кучкой без фальшивых монет - тогда следующее взвешивание даст равенство весов
могла быть и другая ситуация: предыдущее взвешивание было верным, а текущее сорвало ввиде равенства весов
то есть при обнаружении равенства весов весы точно обманули-или на предыдущем взвешивании или на текущем, для определения этого нужно взвешивание ещё раз(и если весы обманули на предыдущем шаге придётся вдобавок делать ещё взвешивание для отброшенной кучки(деля её как обычно пополам)
если обмана не было до конца процесса взвешивания, нужно окончательный результат проверить на истинность(опять используя дополнительные взвешивания)
то есть накладные расходы возникают только в случае обмана или достижения конца процесса без обмана

но у нас число монет это степень тройки, но можно переходить и к двум кучкам
только вот нужно эти переходы выполнять оправдано
а то перейдёшь бывает к двум кучам, а они раза 2-3 поделятся на 2, а потом всё...тут надо соизмерять затраты с результатом

← →
SergP. (2006-06-19 23:53) [85]

> [84] default © (19.06.06 23:04)

6.
Все. Наконец-то понял!!!!
пОСЛЕ 10 ВЗВЕШИВАНИЙ мы можем выделить 21 монету среди которых наверняка есть фальшивая, причем одна из них может быть фальшивой только в том случае когда весы ни разу не соврали (надеюсь это не нужно доказывать). выкидываем нафиг эту монету. у нас остается 20. Берем 7 дополнительных (заведомо нефальшивых монет), либо просто 7 воображаемых монет (пофиг), лепим из них куб, так чтобы воображаемые монеты составляли ребра имеющие общую монету. Далее делаем 3 взвешивания, при каждом взвешивании взвешиваем паралельные слои монет, в которые не входят ни одно из ребер целиком. Получается что в каждом взвешивании участвуют по 8 монет на каждой чашке, (либо по 9 если берем не воображаемые монеты, а реальные). Получается что каждая из наших 20 монет участвует во взвешивании минимум 2 раза. И если мы получаем неравновесие в 2 или 3 взвешиваниях - то мы можем однозначно выявить эту монету, так как неправильное взвешивание было в первых 10 взвешиваниях. Если получаем только один факт неравновесия, значит он неверный, и в первых 10 взвешиваниях небыло неправильных взвешиваний. В таком случае фальшивая монета та, которую мы отбросили нафиг после 10 взвешиваний.

Вобщем все-таки 13 взвешиваний... Как и получилось ранее теоретически...

← →
SergP. (2006-06-20 00:23) [86]

ЕПРСТ... По сути это и есть применение кодов Хемминга (избыточные данные добавляемые к основным с целью выявления и исправления одиночных ошибок), только в данном случае мы имеем дело не с двоичными, а с "троичными битами"

В 6 задаче 13 - правильный ответ

SergP. (20.06.06 00:23) [86]
поздравляю! правда пока время на разбор твоего решения нет, с дипломом вожусь, позже, главно ветке не дать уйти в аут

Пятничные задачки для brain разминки ;) Найти похожие ветки