Форум умных людей

Задачи и головоломки => Логические задачи и головоломки => Тема начата: buka от Март 25, 2010, 02:43:53



Название: Ещё одна задача на монетки
Отправлено: 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. Я эту задачку уже давно решал. Но они все похожи, а этим не так интересны. :)
lkob, Вы говорите о троичном поиске.
Да, если фальшивая монетка легче нормальных (или, что то же - тяжелее нормальных) - мы действительно можем использовать троичный поиск, т.е. с каждым шагом (взвешиванием) сужать круг подозреваемых в 3 раза.
Я предлагаю доказать, что и в случае, когда монетка находится либо среди Х лёгких, либо среди Y тяжёлых мы тоже можем с каждым шагом сужать круг подозреваемых в 3 раза.


Название: Re: Ещё одна задача на монетки
Отправлено: Илья от Апрель 15, 2010, 07:46:54
Цитировать
Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая.
Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных.
А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 16 и 11, в которых либо легкая, если среди 16, либо тяжелая, если среди 11?
Хотя, если поделенная, то слишком просто получается. :)


Название: Re: Ещё одна задача на монетки
Отправлено: buka от Апрель 15, 2010, 15:25:38
Цитировать
Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая.
Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных.
А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 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
Так это легко.
Определяем кучку в 16 монет.
1) 8------8
какая-то легче.
2) 3 ------3, если равновесие, то взвешиваем 1 из двух оставшихся с эталоном
если же одна кучка из трех легче, то взвешиваем 2 из трех между собой и легко определяем фальшивку.
Если же в первом взвешивании у нас равновесие, то фальшивка в 11 и она тяжелее.
А как из 11 за два взвешивания определить фальшивку - надо подумать. Хотя возможно, что изначально алгоритм другой будет.
Из 11 определить более тяжёлую за 2 взвешивания невозможно...


Название: 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
Я это уже понял пока ехал домой.
Первой взвешивание
1) 9----9
9- все монеты из кучи в 16 монет
вторая 9-ка 7+2 монеты из кучи в 11 монет
если равновесие, то за оставшиеся два взвешивания легко определить тяжелую монету из оставшихся 9 монет из 11. А вот если равновесия не будет, то следущие операции надо продумать. :think: Хотя нет  - остаются еще две монеты из кучки в 16 и опять 11 монет.
Вы правильно решили, что сначала надо взять 2/3 всех монет, т.е. 18.
Но 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
Точно - сплошная драма. :)