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

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

Сообщений: 960

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



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

Правильно! Smiley  Браво Гуд
В общем случае стратегия такая: с каждым взвешиванием мы должны уменьшать количество подозреваемых в 3 раза.
Я могу показать, что это можно всегда сделать - при любом соотношении "легких" и "тяжёлых" монет.
Мы должны выбрать 2/3 всех монет, набрав их из чётного кол-ва монет обоих классов (в предельном случае, если монет одного класса >= 2/3, можно взять 2/3 монет только одного класса, т.е. 0 - тоже чётное число Smiley).
Затем выбранные 2/3 монет делим на две кучки, в каждой из которых половина монет одного и другого классов.
В случае неравенства под подозрением остаётся половина из выбранных "тяжёлых" монет из перевесившей чашки и половина из выбранных "лёгких" из противоположной чашки - итого - половина от 2/3, т.е. 1/3 монет.
В случае равновесия - оставшаяся 1/3 монет.
Итак, в любом случае одно взвешивание уменьшает кол-во подозреваемых втрое.
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

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


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


Просмотр профиля
Ответ #17 : Апрель 15, 2010, 21:12:22 �

Цитировать
Итак, в любом случае одно взвешивание уменьшает кол-во подозреваемых втрое.
Так не про это говорил Ikob в самом начале?
Записан

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

Сообщений: 960

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



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

Ikob говорил приблизительно об этом, т.е. о троичном поиске.
Когда фальшивая монета определённо легче (или тяжелее) - это типичный троичный поиск - делим всё на 3 равные кучи, две из которых сравниваем на весах.
Всё, что я хотел показать, это то, что даже в случае, когда фальшивая монета либо среди Л монет и она более лёгкая, либо среди Т монет и она более тяжёлая - то для Л+Т монет тоже можно применить троичный поиск.
В этом - вся фишка.
Можно считать это леммой. Леммой очень важной для решения задач, в которых фальшивая монета отличается по весу, но неизвестно в какую сторону.
В этом случае троичный поиск не проходит.
Но проходит нечто, опирающееся на троичный поиск.
Я уже писал об этом, рассматривая общий случай задачи о 13 монетах.
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

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


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


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

Понятно. Хорошая получилась задача и доказательство. Гуд
А при количестве монет 28-81 уже фальшивку менее чем за 4 взвешивания не определить при любом соотношении Х и Y.
Записан

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

Сообщений: 960

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



Просмотр профиля
Ответ #20 : Апрель 15, 2010, 21:59:13 �

Понятно. Хорошая получилась задача и доказательство. Гуд
А при количестве монет 28-81 уже фальшивку менее чем за 4 взвешивания не определить при любом соотношении Х и Y.
Да, конечно.
Вообще, если число монет М находится в границах: 3К-1 < М <= 3К, то требуется К взвешиваний.
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

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


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


Просмотр профиля
Ответ #21 : Апрель 15, 2010, 22:01:12 �

Занятно. То есть теперь можно решить абсолютно любую задачу с монетами, где есть фальшивка одна или несколько, если конечно она имеет решение.
Записан

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

Сообщений: 960

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



Просмотр профиля
Ответ #22 : Апрель 15, 2010, 22:33:53 �

Занятно. То есть теперь можно решить абсолютно любую задачу с монетами, где есть фальшивка одна или несколько, если конечно она имеет решение.
Пока речь шла об одной фальшивке, причём известно что она либо среди Л монет и легче настоящей, либо среди Т монет и тяжелее настоящей.
Тогда для 3К-1 < Л+Т <= 3К монет требуется К взвешиваний.
Если имеется больше, чем одна фальшивка, то сложность задачи возрастает драматически, на несколько порядков.
Если имеется одна фальшивка, но неизвестно, легче она или тяжелее, то, если число монет М находится в границах:
1+3+32+33+...+3К-1 < М <= 1+3+32+33+...+3К-1 + 3К, то требуется К+1 взвешивание.
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

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


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


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

Точно - сплошная драма. Smiley
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Страниц: 1 [2]
  Печать  
 
Перейти в: