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

Есть 12 монет. Среди них одна фальшивая (она весит больше или меньше, неизвестно).
Как за 3 взвешивания с помощью рычажных весов выявить фальшивую?
Ответы (кто действительно решил, а не узнал как-то по другому - здесь я надеюсь на вашу честность), присылайте мне или любому человеку из списка решивших на майл. В этой теме я буду вести список, решивших эту задачу. (Меня в этом списке не будет - я задачу не решил)
P.S. Увеличивать этот список за счёт числа решивших эту задачу людей, зарегистрированных на Синтоновском форуме имеют право все, кто попал в этот список.

Вопрос: а считается ли взвешиванием определение какая монета легче, а какая тяжелее не весами, а самостоятельно (в смысле если держать монеты в руках)?

QUOTE

Вопрос: а считается ли взвешиванием определение какая монета легче, а какая тяжелее не весами, а самостоятельно (в смысле если держать монеты в руках)?

Конечно нет!!! ( Кстати тут кроется секретный уровень, задачу можно решить вообще без взвешиваний :-D )

Решение этой задачи абсолютно верное и безукоризненное нашёл молодой талантливый синтоновец Борис. Наши поздравления Борису и дальнейших творческих успехов!
P.S. Надеюсь, что вы составите компанию Борису в списке решивших эту задачу.

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

Борис

А рычажные весы - это как? Они показывают, кто весит больше, а кто меньше? А деления есть?

Рычажные весы, это весы которые показывают что больше, а что меньше. Может и одинаково оказаться. На один рычаг можно положить одну или несколько монет и на другой одну или несколько монет. Никаких делений там нет.

МегаВольт решил задачу , причём поместил её на форуме раньше меня. (Я к сожалению не заметил) Поэтому MegaVolt будет в списке первым.

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

MegaVolt
Борис

В наших рядах пополнение!
Поздравляем с решением Мумук!

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

MegaVolt
Борис
Мумук

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

А по-моему наоборот
Из 8 монет за три взвешивания фальшивая определяется элементарно(на решение ушло ~5мин).
А вот из 12... Меня терзает смутное сомнение, что решения вообще нет

Есть. И, кажется, не одно.

Есть даже очень красивое когда каждая монета подписывается буквой и взвешиваются осмысленные слова

Денис,

мне показалось или вы в самом деле забыли указать - особенно это важно для всех тех, кто никогда не нвстречался с задачами такого типа - что монеты не только одинаковы с виду, но одинакового достоинства, и поэтому вес монет (за исключением той, что фальшива) - одинаков? Либо это другая постановка задачи?
Потому что это разные задачи, в самом деле.

Уточните, пожалуйста.

Сообщение отредактировал(а) Woman - 31.05.2005 - 18:52

Если они все разные, то задача имеет ОЧЕНЬ большое решение. При условии, что задано соотношение масс и достоинства.

Все монеты одинаковые с виду (все 12) и вес 11 монет одинаков, а вот 12 монета отличается по весу неизвестно в какую сторону.

Я 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

Да, множество А является собственным, т.е. содержить самого себя. Тем не менее, можно ли указать множество
В, которое не принадлежит множеству всех множеств А и тем самим доказать,что множество А не равно самому себе.

Сообщение отредактировал(а) реалист - 18.08.2005 - 14:22

Задачку с 12 монетками, кажется, решила.

Время не засекала - думаю, что минут 15 - полчаса.

Осталось в комп нормальным языком записать.

Хорошая задачка!

*прикинула*. Хорошая задачка. Но с решением я поторопилась.

Сообщение отредактировал(а) Запятая - 24.08.2005 - 13:07

Похоже наши умники в ледяных пустынях разгадали загадку. На всё ушло менее чем пол дня.
Жду рецензии Дениса.