Подарок любителям логики-2

Я 8-монетную задачу с пол-пинка решил, а над этой бьюсь который день...
Пока могу только сказать, как найти решение с вероятностью 0.75

Кстати интересно было бы рассмотреть задачу "в целом":
Дано N внешне неразличимых монет. Одна из них "фальшивая" и отличается по весу от N-1 "настоящей" монеты(все "настоящие" монеты имеют одинаковый вес). Найти минимальное число взвешиваний, которые потребуется провести на рычажных весах без делений, если
1. "фальшивая" монета легче "настоящих"
2. неизвестно, легче или тяжелее "фальшивая" монета по сравнению с "настоящими"

Сообщение отредактировал(а) Krisania - 5.06.2005 - 11:49

Krisania

Я, наконец-то решил задачу 12/3 (12 монет за 3 взвешивания) (решение послал Денису)
Попутно пришлось решить задачи 2/1, 4/2 и 3/1
Задачи 2/1 и 3/1 решаются только при наличии "эталонных" монет (про которые достоверно известно, что они не фальшивые), а 3/1 еще и требует знания результата предыдущего взвешивания.

По моему мнению, каждое новое взвешивание добавляет к задаче 4 монеты. Т.е. N*4/N, при N>2

Попробую доказать:
Задачи 12/3 и 4/2 решаются. Это мы уже знаем. Для N>3 отделяем 4 монеты, а остальные разделяем на 2 части и взвешиваем. Если к-во монет нечетно, отделяем 3 монеты. Если взвешивание дало равенство, то остается решить задачу 4/2 или 3/2, а ее мы решать умеем.
Если нет, то решаем задачу M-4/N, где M<=4*N Понижая рекуррентно порядок задачи на 1 мы доходим до задач от 8/3 до 12/3, которые решаются.
Задачи 8/2 и 4/1 решения не имеют. Даже при наличии "эталонных" монет и известных результатах предыдущего взвешивания. Доказательство в решении задачи 3/1, которое исчерпывает возможности одного взвешивания.

Governor
Твое решение чересчур осторожное:
1. если есть информация о том, легче, или тяжелее "фальшивая" монета, то количество монет в задаче растет экспоненциально с увеличением числа взвешиваний: за K взвешиваний можно выделить фальшивую из 3^K монет. Получается, что эта информация превращает линейную зависимость в экспоненту. Многовато...
2. Пусть дана задача 4000/1000. Ты отделяешь 4 монеты. Но можно например разделить монеты пополам и после первого взвешивания получить задачу 500/999, которая очевидно решается

Кстати правильного решения я тоже не знаю

Сообщение отредактировал(а) Krisania - 15.06.2005 - 12:57

Krisania

Да, ты права, можно смелее:

M монет делим пополам, одну из половин делим еще пополам и взвешиваем. Сразу половина монет становится эталонными. Т.е. одно взвешивание эталонит половину монет. Ergo 2^N/N задача вполне решаемая.
При N=3,2,1 решения найдены. Все прочие находятся по индукции.
Если известно тяжелее или легче фальшивая, то, как ты говоришь, решаема задача 3^N/N*. Думаю, что ответ следует искать между 2^N/N и 3^N/N

Уж не e^N/N ли?

Хотя e^3=20 Многовато... Может это ассимптота?

---
* Действительно, каждый раз делим монеты на 3 части и 2 части кладем на весы. К-во подозрительных монет с каждым взвешиванием уменьшается втрое.

Сообщение отредактировал(а) Governor - 15.06.2005 - 16:00

Кстати! Вот кажется решение!!!

1. Делим все монеты на 3 части. Треть откладываем, треть взвешиваем (разделив пополам).
2. Если равенство (с вероятностью 1/3), то мы понизили порядок задачи втрое за 1 взвешивание. Если неравенство, то в полтора раза понизили.
3. Теперь с обеих чашек весов снимаем по 1/3 монет и откладываем (не перемешивая). Оставшиеся монеты делим пополам (на каждой чашке) и половины меняем с другой чашкой весов.
4. Если равенство, то мы опять понизили порядок задачи втрое.
Если неравенство осталось прежним, то можно отбросить отложенную треть и перенесенные монеты с одной чашки на другую, что в сумме дает еще треть!
Т.о. порядок задачи опять уменьшается втрое.
Если знак неравенства поменялся на противоположный, то остаются только перемещенные монеты, а их опять же 1/3 и опять порядок задачи уменьшается втрое!
Итак, начиная со второго взвешивания, порядок задачи с каждым разом уменьшается втрое!
Итак, для N монет нам надо log3 N взвешиваний! И нам плевать, знаем ли мы что фальшивка тяжелее или легче!
Однако, это справедливо только для больших N, т.к. при малых, мы стоклкнемся с тем, что число монет нацело не делится на 3 и придется округлять.

Governor
Жалко плюсик поставить не могу.

Кстати, по-моему правильный ответ больше похож на (log3 N) +1. Так как
log3 9 = 2, но за 2 взвешивания фальшивку из 9 монет не определишь.

Krisania, да я тоже об этом подумал, но:
log3N+1 - это достаточное число попыток, но не необходимое.
Например за 3 взвешивания можно определить фальшивку среди 13 монет...
(Разделяя задачу 13/3 на 9/3 и 4/2)

Кстати, а вот кажется и ответ на твой вопрос: за N взвешиваний можно определить фальшивку среди 3^(N-1)+2^(N-1) монет. Причем 2^(N-1) монет откладываются, а 3^(N-1) делятся на 2 и взвешиваются. Если равенство, то решаем задачу 2^(N-1)/N-1, если неравенство - 3^(N-1)/N-1 - обе этих задачи решаются.

Из формулы следует, что за 1 взвешивание можно определить фальшивку только из 2 монет,
за 2 - до 5 монет, за 3 - до 13 монет, за 4 - до 35 монет и т.д.

Сообщение отредактировал(а) Governor - 16.06.2005 - 14:18

Список решивших задачу:

MegaVolt
Борис
Мумук
Governor

Сообщение отредактировал(а) Денис Колокольчиков - 17.06.2005 - 03:44

Нет, из 13, если не известна относительная тяжесть фальшивой монеты, нельзя.

Сообщение отредактировал(а) Yura - 22.06.2005 - 02:15

Почему же нельзя? Можно! 9/3 решается, 4/2 тоже...

Потому что на первом действии у тебя получатся кучки 4 4 5. Значит надо решить 5\2. Не зная сравнительный вес фальшифки решить такую задачу нельзя: она эквивалентна задаче 3\1 без знания относительного веса.


Сообщение отредактировал(а) Yura - 19.07.2005 - 21:53

Пусть А-множество всех множеств.
Возможно ли это теоретически?

реалист

гм, вопрос: а множество А входит в это множество всех множеств?

Хм... Это что шутка такая про юмор???
Делим монеты на три кучки (по четыре монеты). Весь прикол в том, что следующие взвешивание будет уже с тремя монетами (из тех же кучек). В общем по полной используем логическое отрицание.
Дошло через двадцать секунд по прочтению (первой страницы, все время забываю что могут быть еще).
С уважением, Сергей.

Сообщение отредактировал(а) 222Avia - 17.08.2005 - 20:02