59049 монет

[Илья]

Расскажи, как точно уложиться за 13 измерений. Пожалуйста, поподробнее.

Очень интересное кино. Я задал задачку и меня просят дать ответ, когда не прошло и дня с первого поста. Есть же еще желающие.

[SieC65]

ладно, подождем=)

[iPhonograph]

ай!  моё решение про 14 оказалось неверным
илья простак, верит на слово

[iPhonograph]

а, дошло...
и правда, совсем несложно

[Smith]

Илья, можно для прояснения условия задачи спросить, за сколько взвешиваний можно определить одну фальшивую монету из двух при твоем условии? это многое объяснит (для меня в частности)
варианты ответов:
1) за 1 взвешивание
2) за 2 взвешивания
3) за 3 взвешивания
4) за 4 взвешивания
5) невозможно определить
6) Смит, ты 
7) Ваш вариант

[Илья]

Так легко же.

[Smith]

Так легко же.

на ответ 6) намекаете? 

[Илья]

Так легко же.

на ответ 6) намекаете? 

Нет, просто не хочу подсказывать.

[Smith]

так вот если ваш ответ 2), то мой ответ 13..
а вот если нет, то - нет. и тогда хотелось бы посмотреть, хотя бы, на 14, в Вашем исполнении, или  CD_Eater, например..

[Илья]

В моем исполнении?

[Smith]

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

[Илья]

Сначала интересно посмотреть на 13 взвешиваний, когда определяем 1 из двух.

[Smith]

ну, тогда чисто гипотетически...

1) 19683т>19683л=19683л
         /
2) 6561  >  6561л = 6561л
  19683л | 19683л
        /
3) 2187 >  2187=2187
    6561л |  6561л
  19683л | 19683л
        /
4) 6561  |  6561
  19683  | 19683 - меняем местами против 3). если все = то гуд. а если нет, то ..
а, вот, "то" зависит от ответа на мой вопрос в постах выше 

[Илья]

Решение есть - в троичной системе исчисления.
Могу дать не подробное решение для 13 монет:
Показать скрытый текст

За 13 взвешиваний:
Первые 10 взвешиваний как обычно:
Нумеруем монеты и за k-ое взвешивание сравниваем монеты с k-ой цифорой в троичной системе 1 и монеты с k-ой цифорой в троичной системе 2.
В итоге получаем одного Главного Кандидата --- монету, которая будет фальшивой при условии, что все взвешивания были правильны.
И еще 20 дополнительных кандидатов, которые могут быть фальшывыми при одном неправильном взвешивании (по 2 кандидата на одно неправильное взвешивание).
11-ое взвешивание: 8 и 8 из числа дополнительны кандидатов.
Если одна из чаш перевесит, то мы знаем, что хотя бы одно неправильное взвешиние уже было, и фальшифая монета либо Главный Кандидат, либо одна из 8 перевесевших. Из 9 монет находим фальшивую стандартным способом за 2 взвешивания.
Иначе фальшивой может быть только одна из четырех оставшихся.
Делаем 12-ое взвешивание: 2 и 2 из этих четырех.
Если равеновесие, то фальшивая - Главный кандидат. Иначе опять уже было неправильное взвешивание и фальшивая одна из трех, которую находим за одно 13-е взвешивание.

Есть более подробный разбор этого решения.

[Smith]

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