Страниц: 1 2 [3] 4 5 ... 9
  Печать  
Автор Тема: 59049 монет  (Прочитано 40181 раз)
0 Пользователей и 1 Гость смотрят эту тему.

Есть 59049 монет (310). Среди монет имеется одна фальшивая. Известно, что фальшивая монета немного тяжелее настоящей. Сколько нужно минимум взвешиваний на чашечных весах без гирь, чтобы определить фальшивую монету, если известно, что во время одного из взвешиваний весы могут показать неверный результат?
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #30 : Май 21, 2010, 22:16:26 �

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

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307


PeAcE


Просмотр профиля
Ответ #31 : Май 21, 2010, 22:30:57 �

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

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307


PeAcE


Просмотр профиля
Ответ #32 : Май 21, 2010, 22:57:17 �

Илья, я пересмотрел свое решение, начало которого я дал, и у меня даже 13 не получается, только 14 в худшем варианте.. завтра подумаю еще, но пока что я ближе к 15 нежели к 13.. Roll Eyes
Записан
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #33 : Май 22, 2010, 00:28:32 �

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

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

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

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307


PeAcE


Просмотр профиля
Ответ #34 : Май 22, 2010, 08:31:37 �

я вчера предложил вариант решения, но небыло времени пояснить.
имеется ввиду, что если, к примеру, весы показывают 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
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307


PeAcE


Просмотр профиля
Ответ #35 : Май 22, 2010, 08:44:09 �

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

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #36 : Май 22, 2010, 13:52:24 �

Оцениваю число взвешиваний 3К монет в К + [log3K] + 1
Последнее редактирование: Май 22, 2010, 13:54:13 от buka Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307


PeAcE


Просмотр профиля
Ответ #37 : Май 22, 2010, 14:42:29 �

Оцениваю число взвешиваний 3К монет в К + [log3K] + 1
buka, можете конкретно написать алгоритм для 59049 монет? ну или хотя бы просто скажите - сколько взвешиваний по-вашему понадобится для 59049 монет?
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #38 : Май 22, 2010, 14:45:19 �

Цитировать
ну или хотя бы просто скажите - сколько взвешиваний по-вашему понадобится для 59049 монет?
По приведенной Букой оценке видно, что он уложится  за 13 взвешиваний с хвостиком. Smiley
Последнее редактирование: Май 22, 2010, 16:06:38 от Илья Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307


PeAcE


Просмотр профиля
Ответ #39 : Май 22, 2010, 14:47:58 �

так хочется видеть..   Думаю
зы: особенно - хвостик Laugh
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #40 : Май 22, 2010, 14:50:40 �

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

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307


PeAcE


Просмотр профиля
Ответ #41 : Май 22, 2010, 15:14:54 �

Более подробное решение:
Показать скрытый текст
Илья, я не понимаю, к сожалению, то, о чем там написано.  Тормоз можно на пальцах для меня?  Embarrassed
я могу помочь, написать, например:
310 = 59049
39 =   19683
38 =     6561
37 =     2187
36 =       729
35 =       243
34 =         81
33 =         27
32 =           9
31 =           3
30 =           1
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #42 : Май 22, 2010, 16:04:02 �

Для начала надо занумировать монеты:
1 -0
2 -2
3-10
4-11
....
59049 - 10000000000
Разряд считается справа налево.
Последнее редактирование: Май 22, 2010, 16:51:10 от Илья Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #43 : Май 22, 2010, 16:08:28 �

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

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #44 : Май 22, 2010, 16:20:06 �

проще объяснить про кубик рубика
Это который 10-мерный трехслойный? Roll Eyes
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Страниц: 1 2 [3] 4 5 ... 9
  Печать  
 
Перейти в: