Ещё одна задача на монетки.
Вспомним задачу о 24 монетках, среди которых одна более лёгкая.
Мы пришли к выводу, что её можно определить за 3 взвешивания.
Если взять общий случай, то можно доказать, что:
Среди любого количества Х монет (3К-1 < Х <= 3К) можно определить фальшивую монетку не более чем за К взвешиваний, если известно что фальшивая монетка более легкая (или известно что фальшивая монетка более тяжёлая).
Предлагаю доказать более сильное утверждение:
Если мы подозреваем фальшивую монетку среди Х монеток как более лёгкую или среди Y монеток как более тяжёлую, то:
Если 3К-1 < Х+Y<= 3К, мы можем определить фальшивую монетку не более чем за К взвешиваний.
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #15 : Апрель 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 "тяжелую" из перевесившей и проверяем.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #16 : Апрель 15, 2010, 21:10:29 � |
|
Правильно! В общем случае стратегия такая: с каждым взвешиванием мы должны уменьшать количество подозреваемых в 3 раза. Я могу показать, что это можно всегда сделать - при любом соотношении "легких" и "тяжёлых" монет. Мы должны выбрать 2/3 всех монет, набрав их из чётного кол-ва монет обоих классов (в предельном случае, если монет одного класса >= 2/3, можно взять 2/3 монет только одного класса, т.е. 0 - тоже чётное число ). Затем выбранные 2/3 монет делим на две кучки, в каждой из которых половина монет одного и другого классов. В случае неравенства под подозрением остаётся половина из выбранных "тяжёлых" монет из перевесившей чашки и половина из выбранных "лёгких" из противоположной чашки - итого - половина от 2/3, т.е. 1/3 монет. В случае равновесия - оставшаяся 1/3 монет. Итак, в любом случае одно взвешивание уменьшает кол-во подозреваемых втрое.
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #17 : Апрель 15, 2010, 21:12:22 � |
|
Итак, в любом случае одно взвешивание уменьшает кол-во подозреваемых втрое. Так не про это говорил Ikob в самом начале?
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #18 : Апрель 15, 2010, 21:37:30 � |
|
Ikob говорил приблизительно об этом, т.е. о троичном поиске. Когда фальшивая монета определённо легче (или тяжелее) - это типичный троичный поиск - делим всё на 3 равные кучи, две из которых сравниваем на весах. Всё, что я хотел показать, это то, что даже в случае, когда фальшивая монета либо среди Л монет и она более лёгкая, либо среди Т монет и она более тяжёлая - то для Л+Т монет тоже можно применить троичный поиск. В этом - вся фишка. Можно считать это леммой. Леммой очень важной для решения задач, в которых фальшивая монета отличается по весу, но неизвестно в какую сторону. В этом случае троичный поиск не проходит. Но проходит нечто, опирающееся на троичный поиск. Я уже писал об этом, рассматривая общий случай задачи о 13 монетах.
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #19 : Апрель 15, 2010, 21:44:21 � |
|
Понятно. Хорошая получилась задача и доказательство. А при количестве монет 28-81 уже фальшивку менее чем за 4 взвешивания не определить при любом соотношении Х и Y.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #20 : Апрель 15, 2010, 21:59:13 � |
|
Понятно. Хорошая получилась задача и доказательство. А при количестве монет 28-81 уже фальшивку менее чем за 4 взвешивания не определить при любом соотношении Х и Y. Да, конечно. Вообще, если число монет М находится в границах: 3 К-1 < М <= 3 К, то требуется К взвешиваний.
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #21 : Апрель 15, 2010, 22:01:12 � |
|
Занятно. То есть теперь можно решить абсолютно любую задачу с монетами, где есть фальшивка одна или несколько, если конечно она имеет решение.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #22 : Апрель 15, 2010, 22:33:53 � |
|
Занятно. То есть теперь можно решить абсолютно любую задачу с монетами, где есть фальшивка одна или несколько, если конечно она имеет решение.
Пока речь шла об одной фальшивке, причём известно что она либо среди Л монет и легче настоящей, либо среди Т монет и тяжелее настоящей. Тогда для 3 К-1 < Л+Т <= 3 К монет требуется К взвешиваний. Если имеется больше, чем одна фальшивка, то сложность задачи возрастает драматически, на несколько порядков. Если имеется одна фальшивка, но неизвестно, легче она или тяжелее, то, если число монет М находится в границах: 1+3+3 2+3 3+...+3 К-1 < М <= 1+3+3 2+3 3+...+3 К-1 + 3 К, то требуется К+1 взвешивание.
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #23 : Апрель 15, 2010, 22:35:38 � |
|
Точно - сплошная драма.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
|