Илья
Высший разум
 Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
 |
� : Май 20, 2010, 08:04:44 � |
|
Есть 59049 монет (310). Среди монет имеется одна фальшивая. Известно, что фальшивая монета немного тяжелее настоящей. Сколько нужно минимум взвешиваний на чашечных весах без гирь, чтобы определить фальшивую монету, если известно, что во время одного из взвешиваний весы могут показать неверный результат?
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #1 : Май 20, 2010, 08:26:51 � |
|
за 20 взвешиваний справлюсь  |
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #2 : Май 20, 2010, 08:29:56 � |
|
за 20 взвешиваний справлюсь Многовато будет. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #3 : Май 20, 2010, 08:39:19 � |
|
то есть, я хотел сказать, за 21  |
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #4 : Май 20, 2010, 08:43:35 � |
|
то есть, я хотел сказать, за 21 Это верхняя оценка. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #5 : Май 20, 2010, 08:46:58 � |
|
как ты недооцениваешь верхнюю оценку верхняя оценка - это 3*59049*59048/2 |
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #6 : Май 20, 2010, 08:49:11 � |
|
Ну за 11 точно нельзя - это понятно.
Но 21 взвешивание - это слишком просто. Можно уменьшить число взвешиваний, гораздо уменьшить.
|
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
Валерий
Гений-Говорун
Offline
Сообщений: 1395
СПАСИБО
-вы поблагодарили: 157
-вас поблагодарили: 235
|
|
� Ответ #7 : Май 20, 2010, 09:02:14 � |
|
17 получается
|
|
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #8 : Май 20, 2010, 09:06:22 � |
|
17 получается
Уже хорошо. Но можно еще меньше. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #9 : Май 20, 2010, 09:47:35 � |
|
чепырнацать!
|
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #10 : Май 20, 2010, 09:49:15 � |
|
а как можно доказать, что за 11 нельзя?
|
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #11 : Май 20, 2010, 09:56:21 � |
|
а как можно доказать, что за 11 нельзя?
Одного взвешивания недостаточно для определения ошибочного взвешивания: 3 1<10+1 чепырнацать! Теоритически можно и за 13. 3 3>10+3 |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
SieC65
Новенький
Offline
Сообщений: 6
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #12 : Май 20, 2010, 12:16:48 � |
|
Необходимо 11+k взвешиваний, где k - порядковый номер взвешивания, на котором произошла ошибка - в случае если ошибка будет. И 20 взвешиваний, если ее не будет.
Решение: Естественно, что для обычного определения тяжелой монеты надо 10 взвешиваний. Так как одно взвешивание может быть неправильным, нам надо каждый раз взвешивать по 2 раза до тех пор, пока второе, контрольное взвешивание однажды не разойдется с первым. Тогда нам надо будет произвести еще одно взвешивание, чтобы узнать истину. И далее, мы можем смело взвешивать по одному разу, т.к. лимит на неправильные показания закончился. В итоге, нам надо: 2*(k-1) взвешиваний - до ошибочного результата на k-ом шаге, +3 взвешивания на k-м шаге, +(10-k) взвешиваний после того как весы ошиблись, и мы провели три измерения. 2*(k-1)+3+(10-k)=k+11.
Если же ни на одном шаге взвешивание не разойдется с контрольным, то нам надо будет всего: 2*10 = 20 взвешиваний.
|
|
|
|
� Последнее редактирование: Май 20, 2010, 12:22:00 от SieC65 �
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #13 : Май 20, 2010, 12:22:33 � |
|
2*10 = 20 взвешиваний. Уже выяснили что можно и за 14 уложиться. Но можно и за 13.  |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
SieC65
Новенький
Offline
Сообщений: 6
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #14 : Май 20, 2010, 12:25:03 � |
|
Расскажи, как точно уложиться за 13 измерений. Пожалуйста, поподробнее.
|
|
|
|
|
Записан
|
|
|
|
|
