Название: Ещё одна задача на монетки Отправлено: buka от Март 25, 2010, 02:43:53 Ещё одна задача на монетки.
Вспомним задачу о 24 монетках, среди которых одна более лёгкая. Мы пришли к выводу, что её можно определить за 3 взвешивания. Если взять общий случай, то можно доказать, что: Среди любого количества Х монет (3К-1 < Х <= 3К) можно определить фальшивую монетку не более чем за К взвешиваний, если известно что фальшивая монетка более легкая (или известно что фальшивая монетка более тяжёлая). Предлагаю доказать более сильное утверждение: Если мы подозреваем фальшивую монетку среди Х монеток как более лёгкую или среди Y монеток как более тяжёлую, то: Если 3К-1 < Х+Y<= 3К, мы можем определить фальшивую монетку не более чем за К взвешиваний. Название: Re: Ещё одна задача на монетки Отправлено: Хэлл от Март 25, 2010, 02:55:16 Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается фальшивая монетка нам остаётся всего два взвешивания.
В итоге К=4 Название: Re: Ещё одна задача на монетки Отправлено: Lkob от Март 25, 2010, 03:01:59 Для всех задачек такого типа один и тот же алгоритм. :)
Название: Re: Ещё одна задача на монетки Отправлено: Lkob от Март 25, 2010, 03:17:23 А вот для мешков, где может быть 240 другого веса оказался другой. :)
Название: Re: Ещё одна задача на монетки Отправлено: buka от Март 25, 2010, 03:25:33 Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается фальшивая монетка нам остаётся всего два взвешивания. Вы не поняли условие.В итоге К=4 Я его сведу к конкретному случаю. Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. Надо определить эту фальшивую монету за 3 взвешивания. Как это сделать? Название: Re: Ещё одна задача на монетки Отправлено: Lkob от Март 25, 2010, 03:30:59 Я просто имел в виду, что для таких задач первое, что надо сделать, это умножить число монет/изумрудов/шариков на 2/3. Иногда надо додуматься еще до чего-нибудь, но есть стандартный ход.... ;) А это упрощает поиск решения. P.S. Я эту задачку уже давно решал. Но они все похожи, а этим не так интересны. :) Название: Re: Ещё одна задача на монетки Отправлено: buka от Март 25, 2010, 03:45:56 Я просто имел в виду, что для таких задач первое, что надо сделать, это умножить число монет/изумрудов/шариков на 2/3. Иногда надо додуматься еще до чего-нибудь, но есть стандартный ход.... ;) А это упрощает поиск решения. P.S. Я эту задачку уже давно решал. Но они все похожи, а этим не так интересны. :) Да, если фальшивая монетка легче нормальных (или, что то же - тяжелее нормальных) - мы действительно можем использовать троичный поиск, т.е. с каждым шагом (взвешиванием) сужать круг подозреваемых в 3 раза. Я предлагаю доказать, что и в случае, когда монетка находится либо среди Х лёгких, либо среди Y тяжёлых мы тоже можем с каждым шагом сужать круг подозреваемых в 3 раза. Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 07:46:54 Цитировать Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 16 и 11, в которых либо легкая, если среди 16, либо тяжелая, если среди 11?Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. Хотя, если поделенная, то слишком просто получается. :) Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 15:25:38 Цитировать Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая. А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 16 и 11, в которых либо легкая, если среди 16, либо тяжелая, если среди 11?Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных. Хотя, если поделенная, то слишком просто получается. :) Но всего у Вас 3 взвешивания Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 15:35:41 Так это легко.
Определяем кучку в 16 монет. 1) 8------8 какая-то легче. 2) 3 ------3, если равновесие, то взвешиваем 1 из двух оставшихся с эталоном если же одна кучка из трех легче, то взвешиваем 2 из трех между собой и легко определяем фальшивку. Если же в первом взвешивании у нас равновесие, то фальшивка в 11 и она тяжелее. А как из 11 за два взвешивания определить фальшивку - надо подумать. Хотя возможно, что изначально алгоритм другой будет. Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 19:37:15 Так это легко. Из 11 определить более тяжёлую за 2 взвешивания невозможно...Определяем кучку в 16 монет. 1) 8------8 какая-то легче. 2) 3 ------3, если равновесие, то взвешиваем 1 из двух оставшихся с эталоном если же одна кучка из трех легче, то взвешиваем 2 из трех между собой и легко определяем фальшивку. Если же в первом взвешивании у нас равновесие, то фальшивка в 11 и она тяжелее. А как из 11 за два взвешивания определить фальшивку - надо подумать. Хотя возможно, что изначально алгоритм другой будет. Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 19:41:44 Я это уже понял пока ехал домой.
Первой взвешивание 1) 9----9 9- все монеты из кучи в 16 монет вторая 9-ка 7+2 монеты из кучи в 11 монет если равновесие, то за оставшиеся два взвешивания легко определить тяжелую монету из оставшихся 9 монет из 11. А вот если равновесия не будет, то следущие операции надо продумать. :think: Хотя нет - остаются еще две монеты из кучки в 16 и опять 11 монет. Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 19:55:02 Я это уже понял пока ехал домой. Вы правильно решили, что сначала надо взять 2/3 всех монет, т.е. 18.Первой взвешивание 1) 9----9 9- все монеты из кучи в 16 монет вторая 9-ка 7+2 монеты из кучи в 11 монет если равновесие, то за оставшиеся два взвешивания легко определить тяжелую монету из оставшихся 9 монет из 11. А вот если равновесия не будет, то следущие операции надо продумать. :think: Хотя нет - остаются еще две монеты из кучки в 16 и опять 11 монет. Но 9т против 7т+2л уже неверно - в случае когда 9т перевешивают у нас под подозрением 11 монет - 9т и 2л, а это в 2 взвешивания не определить... Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 19:56:58 Есть подозрение, что здесь примерно такое же решение как в 13 монетах - осталось додумать. :read:
Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 20:11:49 Вариант с 13-ю монетками более сложный.
Здесь стратегия проще :) Вы хотели взять 18 монет: 16Т и 2Л - это можно. Но распределите их по-другому :) Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 20:52:11 Есть!
16т/2 - 8 1)8т+1л---8т+1л - если равновесие, то все просто с оставшимися 9-ю легкими. Если равновесия нет, то проверяем 8т монет из кучки, которая перевесела и 1 монету л. из кучки, которая оказалась легче - понятно почему так. 2) 3т---3т - если равновесие, то остаются 2т и 1л, взвешиваем 1т----1т и однозначно определяем если равновесие нет, то берем две монеты из перевесившей кучки и взвешиваем их между собой. 3) 1т---1т, если равновесие, то оставшееся монета фальшивка, если нет, то фальшивка перевесившая. Если же в 16 л, а в 11 т, как и было изначально по условию, то первое взвешивание аналогичное, а в остальном наоборот, то есть берем 8 монет из "легкой" кучки и 1 "тяжелую" из перевесившей и проверяем. Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 21:10:29 Правильно! :) :bravo2: :good3:
В общем случае стратегия такая: с каждым взвешиванием мы должны уменьшать количество подозреваемых в 3 раза. Я могу показать, что это можно всегда сделать - при любом соотношении "легких" и "тяжёлых" монет. Мы должны выбрать 2/3 всех монет, набрав их из чётного кол-ва монет обоих классов (в предельном случае, если монет одного класса >= 2/3, можно взять 2/3 монет только одного класса, т.е. 0 - тоже чётное число :)). Затем выбранные 2/3 монет делим на две кучки, в каждой из которых половина монет одного и другого классов. В случае неравенства под подозрением остаётся половина из выбранных "тяжёлых" монет из перевесившей чашки и половина из выбранных "лёгких" из противоположной чашки - итого - половина от 2/3, т.е. 1/3 монет. В случае равновесия - оставшаяся 1/3 монет. Итак, в любом случае одно взвешивание уменьшает кол-во подозреваемых втрое. Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 21:12:22 Цитировать Итак, в любом случае одно взвешивание уменьшает кол-во подозреваемых втрое. Так не про это говорил Ikob в самом начале?Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 21:37:30 Ikob говорил приблизительно об этом, т.е. о троичном поиске.
Когда фальшивая монета определённо легче (или тяжелее) - это типичный троичный поиск - делим всё на 3 равные кучи, две из которых сравниваем на весах. Всё, что я хотел показать, это то, что даже в случае, когда фальшивая монета либо среди Л монет и она более лёгкая, либо среди Т монет и она более тяжёлая - то для Л+Т монет тоже можно применить троичный поиск. В этом - вся фишка. Можно считать это леммой. Леммой очень важной для решения задач, в которых фальшивая монета отличается по весу, но неизвестно в какую сторону. В этом случае троичный поиск не проходит. Но проходит нечто, опирающееся на троичный поиск. Я уже писал об этом, рассматривая общий случай задачи о 13 монетах. Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 21:44:21 Понятно. Хорошая получилась задача и доказательство. :good:
А при количестве монет 28-81 уже фальшивку менее чем за 4 взвешивания не определить при любом соотношении Х и Y. Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 21:59:13 Понятно. Хорошая получилась задача и доказательство. :good: Да, конечно.А при количестве монет 28-81 уже фальшивку менее чем за 4 взвешивания не определить при любом соотношении Х и Y. Вообще, если число монет М находится в границах: 3К-1 < М <= 3К, то требуется К взвешиваний. Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 22:01:12 Занятно. То есть теперь можно решить абсолютно любую задачу с монетами, где есть фальшивка одна или несколько, если конечно она имеет решение.
Название: Re: Ещё одна задача на монетки Отправлено: buka от Апрель 15, 2010, 22:33:53 Занятно. То есть теперь можно решить абсолютно любую задачу с монетами, где есть фальшивка одна или несколько, если конечно она имеет решение. Пока речь шла об одной фальшивке, причём известно что она либо среди Л монет и легче настоящей, либо среди Т монет и тяжелее настоящей.Тогда для 3К-1 < Л+Т <= 3К монет требуется К взвешиваний. Если имеется больше, чем одна фальшивка, то сложность задачи возрастает драматически, на несколько порядков. Если имеется одна фальшивка, но неизвестно, легче она или тяжелее, то, если число монет М находится в границах: 1+3+32+33+...+3К-1 < М <= 1+3+32+33+...+3К-1 + 3К, то требуется К+1 взвешивание. Название: Re: Ещё одна задача на монетки Отправлено: Илья от Апрель 15, 2010, 22:35:38 Точно - сплошная драма. :)
|