Страниц: [1] 2
  Печать  
Автор Тема: Ещё одна задача на монетки  (Прочитано 10608 раз)
0 Пользователей и 1 Гость смотрят эту тему.
buka
Гений
*****
Offline Offline

Сообщений: 960

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



Просмотр профиля
: Март 25, 2010, 02:43:53 �

Ещё одна задача на монетки.
Вспомним задачу о 24 монетках, среди которых одна более лёгкая.
Мы пришли к выводу, что её можно определить за 3 взвешивания.
Если взять общий случай, то можно доказать, что:
Среди любого количества Х монет (3К-1 < Х <= 3К) можно определить фальшивую монетку не более чем за К взвешиваний, если известно что фальшивая монетка более легкая (или известно что фальшивая монетка более тяжёлая).
Предлагаю доказать более сильное утверждение:
Если мы подозреваем фальшивую монетку среди Х монеток как более лёгкую или среди Y монеток как более тяжёлую, то:
Если 3К-1 < Х+Y<= 3К, мы можем определить фальшивую монетку не более чем за К взвешиваний.

Эти пользователи сказали вам СПАСИБО :

Илья

За это сообщение 1 пользователь сказал спасибо!
Записан
Хэлл
Новенький
*
Offline Offline

Сообщений: 7

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



Просмотр профиля
Ответ #1 : Март 25, 2010, 02:55:16 �

Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается  фальшивая монетка нам остаётся всего два взвешивания.
В итоге К=4
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

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


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #2 : Март 25, 2010, 03:01:59 �

Для всех задачек такого типа один и тот же алгоритм. Smiley
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Lkob
Умник
****
Offline Offline

Сообщений: 625

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


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #3 : Март 25, 2010, 03:17:23 �

А вот для мешков, где может быть 240 другого веса оказался другой. Smiley
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
buka
Гений
*****
Offline Offline

Сообщений: 960

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



Просмотр профиля
Ответ #4 : Март 25, 2010, 03:25:33 �

Взвешиваем аналогично прошлой задаче, но только первые две кучки, и для сравнения результата третью кучку с любой из первых... В итоге, мы определяем, более тяжелая она, или лёгкая. Ну а дальше, у нас остаётся кучка из 8 монеток, делим на 3-3-2, и так как знаем, чем отличается  фальшивая монетка нам остаётся всего два взвешивания.
В итоге К=4
Вы не поняли условие.
Я его сведу к конкретному случаю.
Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая.
Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных.
Надо определить эту фальшивую монету за 3 взвешивания.
Как это сделать?
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

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


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #5 : Март 25, 2010, 03:30:59 �

Показать скрытый текст

 Я просто имел в виду, что для таких задач первое, что надо сделать, это умножить число монет/изумрудов/шариков на 2/3. Иногда надо додуматься еще до чего-нибудь, но есть стандартный ход.... Wink
А это упрощает поиск решения.

P.S. Я эту задачку уже давно решал. Но они все похожи, а этим не так интересны. Smiley
Последнее редактирование: Март 25, 2010, 03:32:32 от lkob Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
buka
Гений
*****
Offline Offline

Сообщений: 960

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



Просмотр профиля
Ответ #6 : Март 25, 2010, 03:45:56 �

Показать скрытый текст

 Я просто имел в виду, что для таких задач первое, что надо сделать, это умножить число монет/изумрудов/шариков на 2/3. Иногда надо додуматься еще до чего-нибудь, но есть стандартный ход.... Wink
А это упрощает поиск решения.

P.S. Я эту задачку уже давно решал. Но они все похожи, а этим не так интересны. Smiley
lkob, Вы говорите о троичном поиске.
Да, если фальшивая монетка легче нормальных (или, что то же - тяжелее нормальных) - мы действительно можем использовать троичный поиск, т.е. с каждым шагом (взвешиванием) сужать круг подозреваемых в 3 раза.
Я предлагаю доказать, что и в случае, когда монетка находится либо среди Х лёгких, либо среди Y тяжёлых мы тоже можем с каждым шагом сужать круг подозреваемых в 3 раза.
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

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


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


Просмотр профиля
Ответ #7 : Апрель 15, 2010, 07:46:54 �

Цитировать
Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая.
Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных.
А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 16 и 11, в которых либо легкая, если среди 16, либо тяжелая, если среди 11?
Хотя, если поделенная, то слишком просто получается. Smiley
Последнее редактирование: Апрель 15, 2010, 08:59:45 от Илья Записан

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

Сообщений: 960

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



Просмотр профиля
Ответ #8 : Апрель 15, 2010, 15:25:38 �

Цитировать
Допустим, у нас есть 27 монет, одна из них (только одна!!!) - фальшивая.
Известно, что она либо среди 16 монет и может быть легче нормальных, либо среди 11 монет и может быть тяжелее нормальных.
А нам монеты даны как единая куча из 27 монет или уже поделенные на две кучи: 16 и 11, в которых либо легкая, если среди 16, либо тяжелая, если среди 11?
Хотя, если поделенная, то слишком просто получается. Smiley

Поделённая.
Но всего у Вас 3 взвешивания
Записан
Илья
Высший разум
*****
Offline 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 Offline

Сообщений: 960

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



Просмотр профиля
Ответ #10 : Апрель 15, 2010, 19:37:15 �

Так это легко.
Определяем кучку в 16 монет.
1) 8------8
какая-то легче.
2) 3 ------3, если равновесие, то взвешиваем 1 из двух оставшихся с эталоном
если же одна кучка из трех легче, то взвешиваем 2 из трех между собой и легко определяем фальшивку.
Если же в первом взвешивании у нас равновесие, то фальшивка в 11 и она тяжелее.
А как из 11 за два взвешивания определить фальшивку - надо подумать. Хотя возможно, что изначально алгоритм другой будет.
Из 11 определить более тяжёлую за 2 взвешивания невозможно...
Записан
Илья
Высший разум
*****
Offline 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 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 Offline

Сообщений: 7695

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


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


Просмотр профиля
Ответ #13 : Апрель 15, 2010, 19:56:58 �

Есть подозрение, что здесь примерно такое же решение как в 13 монетах - осталось додумать. Чтение
Записан

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

Сообщений: 960

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



Просмотр профиля
Ответ #14 : Апрель 15, 2010, 20:11:49 �

Вариант с 13-ю монетками более сложный.
Здесь стратегия проще Smiley
Вы хотели взять 18 монет: 16Т и 2Л - это можно.
Но распределите их по-другому Smiley
Записан
Страниц: [1] 2
  Печать  
 
Перейти в: