buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� : Март 25, 2010, 02:43:53 � |
|
Ещё одна задача на монетки. Вспомним задачу о 24 монетках, среди которых одна более лёгкая. Мы пришли к выводу, что её можно определить за 3 взвешивания. Если взять общий случай, то можно доказать, что: Среди любого количества Х монет (3К-1 < Х <= 3К) можно определить фальшивую монетку не более чем за К взвешиваний, если известно что фальшивая монетка более легкая (или известно что фальшивая монетка более тяжёлая). Предлагаю доказать более сильное утверждение: Если мы подозреваем фальшивую монетку среди Х монеток как более лёгкую или среди Y монеток как более тяжёлую, то: Если 3К-1 < Х+Y<= 3К, мы можем определить фальшивую монетку не более чем за К взвешиваний.
|
|
|
|
Хэлл
Новенький
Offline
Сообщений: 7
СПАСИБО
-вы поблагодарили: 2
-вас поблагодарили: 1
|
|
� Ответ #1 : Март 25, 2010, 02:55:16 � |
|
Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается фальшивая монетка нам остаётся всего два взвешивания. В итоге К=4
|
|
|
Записан
|
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #2 : Март 25, 2010, 03:01:59 � |
|
Для всех задачек такого типа один и тот же алгоритм.
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #3 : Март 25, 2010, 03:17:23 � |
|
А вот для мешков, где может быть 240 другого веса оказался другой.
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #4 : Март 25, 2010, 03:25:33 � |
|
Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается фальшивая монетка нам остаётся всего два взвешивания. В итоге К=4
Вы не поняли условие. Я его сведу к конкретному случаю. Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. Надо определить эту фальшивую монету за 3 взвешивания. Как это сделать?
|
|
|
Записан
|
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #5 : Март 25, 2010, 03:30:59 � |
|
Показать скрытый текст Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается фальшивая монетка нам остаётся всего два взвешивания. В итоге К=4
Вы не поняли условие. Я его сведу к конкретному случаю. Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. Надо определить эту фальшивую монету за 3 взвешивания. Как это сделать? Я просто имел в виду, что для таких задач первое, что надо сделать, это умножить число монет/изумрудов/шариков на 2/3. Иногда надо додуматься еще до чего-нибудь, но есть стандартный ход.... А это упрощает поиск решения. P.S. Я эту задачку уже давно решал. Но они все похожи, а этим не так интересны.
|
|
� Последнее редактирование: Март 25, 2010, 03:32:32 от lkob �
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #6 : Март 25, 2010, 03:45:56 � |
|
Показать скрытый текст Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается фальшивая монетка нам остаётся всего два взвешивания. В итоге К=4
Вы не поняли условие. Я его сведу к конкретному случаю. Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. Надо определить эту фальшивую монету за 3 взвешивания. Как это сделать? Я просто имел в виду, что для таких задач первое, что надо сделать, это умножить число монет/изумрудов/шариков на 2/3. Иногда надо додуматься еще до чего-нибудь, но есть стандартный ход.... А это упрощает поиск решения. P.S. Я эту задачку уже давно решал. Но они все похожи, а этим не так интересны. lkob, Вы говорите о троичном поиске. Да, если фальшивая монетка легче нормальных (или, что то же - тяжелее нормальных) - мы действительно можем использовать троичный поиск, т.е. с каждым шагом (взвешиванием) сужать круг подозреваемых в 3 раза. Я предлагаю доказать, что и в случае, когда монетка находится либо среди Х лёгких, либо среди Y тяжёлых мы тоже можем с каждым шагом сужать круг подозреваемых в 3 раза.
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #7 : Апрель 15, 2010, 07:46:54 � |
|
Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 16 и 11, в которых либо легкая, если среди 16, либо тяжелая, если среди 11? Хотя, если поделенная, то слишком просто получается.
|
|
� Последнее редактирование: Апрель 15, 2010, 08:59:45 от Илья �
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #8 : Апрель 15, 2010, 15:25:38 � |
|
Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 16 и 11, в которых либо легкая, если среди 16, либо тяжелая, если среди 11? Хотя, если поделенная, то слишком просто получается. Поделённая. Но всего у Вас 3 взвешивания
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #9 : Апрель 15, 2010, 15:35:41 � |
|
Так это легко. Определяем кучку в 16 монет. 1) 8------8 какая-то легче. 2) 3 ------3, если равновесие, то взвешиваем 1 из двух оставшихся с эталоном если же одна кучка из трех легче, то взвешиваем 2 из трех между собой и легко определяем фальшивку. Если же в первом взвешивании у нас равновесие, то фальшивка в 11 и она тяжелее. А как из 11 за два взвешивания определить фальшивку - надо подумать. Хотя возможно, что изначально алгоритм другой будет.
|
|
� Последнее редактирование: Апрель 15, 2010, 15:38:23 от Илья �
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #10 : Апрель 15, 2010, 19:37:15 � |
|
Так это легко. Определяем кучку в 16 монет. 1) 8------8 какая-то легче. 2) 3 ------3, если равновесие, то взвешиваем 1 из двух оставшихся с эталоном если же одна кучка из трех легче, то взвешиваем 2 из трех между собой и легко определяем фальшивку. Если же в первом взвешивании у нас равновесие, то фальшивка в 11 и она тяжелее. А как из 11 за два взвешивания определить фальшивку - надо подумать. Хотя возможно, что изначально алгоритм другой будет.
Из 11 определить более тяжёлую за 2 взвешивания невозможно...
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #11 : Апрель 15, 2010, 19:41:44 � |
|
Я это уже понял пока ехал домой. Первой взвешивание 1) 9----9 9- все монеты из кучи в 16 монет вторая 9-ка 7+2 монеты из кучи в 11 монет если равновесие, то за оставшиеся два взвешивания легко определить тяжелую монету из оставшихся 9 монет из 11. А вот если равновесия не будет, то следущие операции надо продумать. Хотя нет - остаются еще две монеты из кучки в 16 и опять 11 монет.
|
|
� Последнее редактирование: Апрель 15, 2010, 19:43:55 от Илья �
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #12 : Апрель 15, 2010, 19:55:02 � |
|
Я это уже понял пока ехал домой. Первой взвешивание 1) 9----9 9- все монеты из кучи в 16 монет вторая 9-ка 7+2 монеты из кучи в 11 монет если равновесие, то за оставшиеся два взвешивания легко определить тяжелую монету из оставшихся 9 монет из 11. А вот если равновесия не будет, то следущие операции надо продумать. Хотя нет - остаются еще две монеты из кучки в 16 и опять 11 монет. Вы правильно решили, что сначала надо взять 2/3 всех монет, т.е. 18. Но 9т против 7т+2л уже неверно - в случае когда 9т перевешивают у нас под подозрением 11 монет - 9т и 2л, а это в 2 взвешивания не определить...
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #13 : Апрель 15, 2010, 19:56:58 � |
|
Есть подозрение, что здесь примерно такое же решение как в 13 монетах - осталось додумать.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #14 : Апрель 15, 2010, 20:11:49 � |
|
Вариант с 13-ю монетками более сложный. Здесь стратегия проще Вы хотели взять 18 монет: 16Т и 2Л - это можно. Но распределите их по-другому
|
|
|
Записан
|
|
|
|
|