59049 монет

[Илья]

Если не осилите, то выложу и подробное. Вроде все кто хотел уже отметились.

[Smith]

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

[Smith]

Илья, я пересмотрел свое решение, начало которого я дал, и у меня даже 13 не получается, только 14 в худшем варианте.. завтра подумаю еще, но пока что я ближе к 15 нежели к 13..

[iPhonograph]

какая коварная задачка
моё второе решение, когда я подумал, что 13 получить легко, оказалось неправильным

я думал, что после 10 взвешиваний (по правилу 10-мерного трёхслойного кубика рубика), дающих координату главного подозреваемого, достаточно проделать аналогичные 3 взвешивания для оставшихся 21 подозреваемых, т.к. 21 <= 27
но я не учёл, что ошибка может случиться как раз во время последних 3 взвешиваний

получается. что размещать эти 21 в кубе 3*3*3 надо хитро - главного подозреваемого в ячейку (0,0,0), а ячейки с двумя нулями в координатах заполнить монетами, которые гарантированно не фальшивые по результатам первых 10 взвешиваний.

[Smith]

я вчера предложил вариант решения, но небыло времени пояснить.
имеется ввиду, что если, к примеру, весы показывают 9683т>19683л=19683л при первом взвешивании, то, вполне возможно, что на самом деле правильно 1<2>3. и так в кажом взвешивании.
тогда при взвешиваниях 3^8, 3^5, 3^3, 3^1 мы делаем контрольные взвешивания (КВ) таким образом, что взвешиваем только "балласт".
при этом, если весы сохраняют свое положение, то все было правильно, и на КВ мы тратим 1 дополнительный ход. если во время КВ весы меняют положение, значит либо ошибка была допущена выше, либо это сейчас и есть ошибка, тогда для определения понадобится 3 взвешивания.
например:       
1) 19683a>19683b=19683c - весы показывают, на самом деле 19683a<19683b>19683c
         /
2) 6561a  >  6561a = 6561a - весы показывают, на самом деле  6561a  =  6561a = 6561a
  19683b > 19683c - мы добавили "балласт" из первого взвешивания, он то и дает знак >
       
3) 2187a >  2187a=2187a - пок. весы, на самом деле 2187a =  2187a=2187a
    6561a = 6561a
  19683b > 19683c
       
4) 6561a  =  6561a
  19683c  < 19683b - взвешиваем "балласт" без 2187 и меняем местами 19683c  < 19683b против 3). если весы равны, то взвешивание 3) было правильным и мы продолжаем взвешивания, но если весы меняют положение, то делаем (КВ) - 5)
5) повторяем взвешивание 4 (КВ) и если весы остались в положении как при 4) взвешивании, значит ошибка была в самом начале в 19683 и теперь мы знаем правильную 19683 из трех и следующие 9 ходов - это от 3^9 до 1.

[Smith]

а чтобы получить за 13 ходов - прийдется определить за 2 взвешивания на обычных (не Y образных) чашечных весах 1 фальшивую монету из 9, либо пересмотреть точки КВ 

[buka]

Оцениваю число взвешиваний 3^К монет в К + [log₃K] + 1

[Smith]

Оцениваю число взвешиваний 3^К монет в К + [log₃K] + 1

buka, можете конкретно написать алгоритм для 59049 монет? ну или хотя бы просто скажите - сколько взвешиваний по-вашему понадобится для 59049 монет?

[Илья]

ну или хотя бы просто скажите - сколько взвешиваний по-вашему понадобится для 59049 монет?

По приведенной Букой оценке видно, что он уложится  за 13 взвешиваний с хвостиком.

[Smith]

так хочется видеть..   
зы: особенно - хвостик

[Илья]

Более подробное решение:
Показать скрытый текст

Итак
1. Нумеруем монеты i10...ik...i1, ik=0,1,2; k=1..10

2. В k-ом взвешивании на одну чашку кладем монеты с 0 в k-ом разряде, на другую с 1. Результат k-ого взвешивания Wk записываем как:
0 - перевесила чашка с "0"
1 - перевесила чашка с "1"
2 - равновесие (фальшивка в группе с 2 в k-ом разряде)

3. Результат взвешивания W10...Wk...W1 указывает на номер "главного" кандидата (не было ошибок в первых 10 взвешиваниях). Если ошибка произошла в k-ом взвешивании, то добавляются два дополнительных кандидата W10W9...Dk...W2W1, где Dk >< Wk не совпадающие с Wk две другие цифры. Итого имеем 20 дополнительных кандидатов.

4. 21 монету-кандидат дополняем 6 настоящими (любые из оставшихся) до 27 и организуем 3 дополнительных взвешивания по прежнему принципу. Занумеруем их j3j2j1.

4.1 Если в основных взвешиваниях ошибки не было - главный кандидат фальшивый - то ошибка произойдет в одном из доп. взвешиваний. Главного кандидата занумеруем 000 и результат дополнительных взвешиваний V3V2V1 должен быть 000. Но ошибка в любом из взвешиваний/разряде даст один из результатов 100, 200, 010, 020, 001, 002. На эти 6 мест мы помещаем настоящие монеты. На остальные 20 мест - дополнительных кандидатов.

4.2 Если ошибка случилась в основных взвешиваниях, то результат дополнительных взвешиваний V3V2V1 безошибочно укажет номер одного из 20 доп.кандидатов.

[Smith]

Более подробное решение:
Показать скрытый текст

Итак
1. Нумеруем монеты i10...ik...i1, ik=0,1,2; k=1..10

2. В k-ом взвешивании на одну чашку кладем монеты с 0 в k-ом разряде, на другую с 1. Результат k-ого взвешивания Wk записываем как:
0 - перевесила чашка с "0"
1 - перевесила чашка с "1"
2 - равновесие (фальшивка в группе с 2 в k-ом разряде)

3. Результат взвешивания W10...Wk...W1 указывает на номер "главного" кандидата (не было ошибок в первых 10 взвешиваниях). Если ошибка произошла в k-ом взвешивании, то добавляются два дополнительных кандидата W10W9...Dk...W2W1, где Dk >< Wk не совпадающие с Wk две другие цифры. Итого имеем 20 дополнительных кандидатов.

4. 21 монету-кандидат дополняем 6 настоящими (любые из оставшихся) до 27 и организуем 3 дополнительных взвешивания по прежнему принципу. Занумеруем их j3j2j1.

4.1 Если в основных взвешиваниях ошибки не было - главный кандидат фальшивый - то ошибка произойдет в одном из доп. взвешиваний. Главного кандидата занумеруем 000 и результат дополнительных взвешиваний V3V2V1 должен быть 000. Но ошибка в любом из взвешиваний/разряде даст один из результатов 100, 200, 010, 020, 001, 002. На эти 6 мест мы помещаем настоящие монеты. На остальные 20 мест - дополнительных кандидатов.

4.2 Если ошибка случилась в основных взвешиваниях, то результат дополнительных взвешиваний V3V2V1 безошибочно укажет номер одного из 20 доп.кандидатов.

Илья, я не понимаю, к сожалению, то, о чем там написано.  можно на пальцах для меня? 
я могу помочь, написать, например:
₃10 = 59049
₃9 =   19683
₃8 =     6561
₃7 =     2187
₃6 =       729
₃5 =       243
₃4 =         81
₃3 =         27
₃2 =           9
₃1 =           3
₃0 =           1

[Илья]

Для начала надо занумировать монеты:
1 -0
2 -2
3-10
4-11
....
59049 - 10000000000
Разряд считается справа налево.

[iPhonograph]

проще объяснить про кубик рубика

[Илья]

проще объяснить про кубик рубика

Это который 10-мерный трехслойный?