Классика - взвешиваем монетки

[A.Edem]

VAL в сообщении #1131175 писал(а):

Имеется 4 золотых и 4 серебряных монеты (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За три взвешивания на чашечных весах без гирь определить фальшивые монеты.

Может, мне просто повезло, но придумалось даже несколько решений. Одно из них распишу чуть позже.

[A.Edem]

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

[Iam]

Достаточно 3-х взвешиваний. Задача легко решается на основе подсчета диаметра разбиений (см. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=1310&option_lang=rus). В качестве примера в указанной статье решается задача нахождения до 2-х фальшивых монет из 11-ти тестируемых при условии, что веса фальшивых монет могут отличаться от настоящих в большую или меньшую сторону на одну и ту же величину. Построен алгоритм, который за 5 взвешиваний находит фальшивые монеты (если они есть) и определяет их относительные веса.
Попробуйте для интереса построить алгоритм, который за 5 или менее взвешиваний находит эти монеты без определения их относительных весов.
Общий подход и конструкции этой работы использованы в https://arxiv.org/pdf/1606.04170.pdf, однако здесь не показан принцип построения взвешиваний, который может быть использован для сформулированной VAL задачи.

[HungryLion]

Решение под спойлером, на случай если кто-то ещё сам хочет подумать.

(Ответ)

I. Взвешиваем две золотые монеты.
1. Если одна легче, то она фальшивая, а вторая настоящая. Остаётся 4 серебрянных и две золотых, из которых одна фальшивая.
2. Если монеты одинаковые, то либо они обе фальшивые, либо обе настоящие. Откладываем по одной монете из двух взвешенных золотых и двух невзвешенных, запоминая из какая где. Остаётся, как и в первом случае, 4 серебрянных и две золотых, из которых одна фальшивая.

II. Кладем в каждую чашку весов золотую и серебрянную монетки.
1. Если одна чашка легче, то в ней фальшивая золотая монета, а в другой чашке настоящая серебрянная. Остаётся три серебрянные монеты, из котрых легко находим фальшивую последним взвешиванием.
2. Если чашки одинаковые, то в одной из них фальшивая злотая монета, а в другой фальшивая серебрянная. Меняем серебрянные монеты чашками и взвешиваем. В более легкой обе фальшивые монеты.

Если в первом взвешивании золотые монеты обыли одинаковые, то фальшивая из них та, что была вместе с фальшивой золотой, полученной во втором или третьем взвешивании.

VAL в сообщении #1131175 писал(а):

Если нужно, могу предложить еще массу вариаций.

Спасибо за эту, и нужно ещё, конечно.
А вы их сами придумываете?

[A.Edem]

HungryLion в сообщении #1142545 писал(а):

II. Кладем в каждую чашку весов золотую и серебрянную монетки.
1. Если одна чашка легче, то в ней фальшивая золотая монета, а в другой чашке настоящая серебрянная.

А если две чашки весов покажут равновесие, откуда вы будете знать, две фальшивые ли на чашках монеты или настоящие?

[A.Edem]

Чувствуется, что здесь дедовским способом (методом проб и ошибок) решить будет практически невозможно. Скорее всего необходимо будет применить запутанную комбинаторику, которую в уме представить и сообразить окажется очень сложным занятием.

[HungryLion]

A.Edem в сообщении #1142553 писал(а):

HungryLion в сообщении #1142545 писал(а):

II. Кладем в каждую чашку весов золотую и серебрянную монетки.
1. Если одна чашка легче, то в ней фальшивая золотая монета, а в другой чашке настоящая серебрянная.

А если две чашки весов покажут равновесие, откуда вы будете знать, две фальшивые ли на чашках монеты или настоящие?

Так, вроде, пункт II.2. про это. К этому моменту одна золотая монета из взвешиваемых точно фальшивая, так что указанной вами ситуации возникнуть не может.

[A.Edem]

(Оффтоп)

HungryLion, к сожалению, мне всё равно многое непонятно, начиная со второго этапа Ваших объяснений
Начнём по порядку. "Кладем в каждую чашку весов золотую и серебряные монетки". Вопрос: откуда берем для этого действия золотую монету? И почему при равновесии весов впоследствии она должна оказаться именно фальшивой, а не настоящей, к примеру, - с настоящей серебряной в противовес? - "2. Если чашки одинаковые, то в одной из них фальшивая злотая монета, а в другой фальшивая серебрянная."

[VAL]

HungryLion в сообщении #1142545 писал(а):

VAL в сообщении #1131175 писал(а):

Если нужно, могу предложить еще массу вариаций.

Спасибо за эту, и нужно ещё, конечно.

Пожалуйста:
Имеется 6 золотых и 5 серебряных монет (отличаются от золотых внешне). Среди золотых две фальшивых, среди серебряных - одна. Все настоящие равны по весу. Все фальшивые - тоже, но легче настоящих. За четыре взвешивания на чашечных весах без гирь определить фальшивые монеты.

А еще одна задачка (ММ179) здесь уже пробегала.

Цитата:

А вы их сами придумываете?

Да.
Некоторые новые идеи почерпнул, общаясь с Константином Кнопом (он заглядывает на dxdy).

[HungryLion]

(Оффтоп)

A.Edem в сообщении #1142591 писал(а):

Кладем в каждую чашку весов золотую и серебряные монетки". Вопрос: откуда берем для этого действия золотую монету?

Согласен, не очень понятно написал.
В каждую чашку кладём две монеты: золотую и серебрянную. Откуда берём золотые, зависит от результата первого взвешивания: если одна была легче, то берём две, которые не взвешивали; если обе одинаковые, то берём одну из взвешенных и одну из оставшихся. Таким образом гарантированно во втором взвешивании одна злотая монета фальшивая а одна настоящая.

A.Edem в сообщении #1142591 писал(а):

И почему при равновесии весов впоследствии она должна оказаться именно фальшивой, а не настоящей, к примеру, - с настоящей серебряной в противовес?

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

-- Вс авг 07, 2016 18:51:44 --

VAL
Спасибо, буду размышлять.

[A.Edem]

(Оффтоп)

HungryLion, ах, вот теперь всё стало на свои места! Теперь я с радостью ясно вижу верность искомого решения. Благодарю за пояснения и за ответ к задаче.

[A.Edem]

Ответ на задачу про шесть золотых и пять серебряных монет:

(Оффтоп)

После приёма, показанного HungryLion, решать подобные задачи, кажется простым развлечением.
Сначала ставим на весы по две серебряные монеты. Так выявляем три настоящие и пару, в которой неизвестно где настоящая и где фальшивая. Ставим эту пару на разные чаши весов, к ним же ставим по одной золотой монете (6 золотых монет делим на три пары). Если показало равновесие, то запоминаем, как что стояло. Берём вторую пару золотых (убирая с весов первую), и ставим их к первоначальным серебряным. Если снова показало равновесие, то тогда меняем местами монеты в двух парах золотых, ставим к ним начальную пару серебряных, и взвешиваем, легко определяя, где настоящие, а где фальшивые.
Если после взвешивания второй пары золотых монет весы показали перевес, то мы узнаем таким образом, где была фальшивая и настоящая серебряные, где в первой паре золотых были фальшивая и настоящая, а также одну настоящую золотую. Останется для четвёртого взвешивания узнать, где находится фальшивая среди трёх оставшихся золотых, что сделать очень просто.
Если же после начального взвешивания первой пары золотых весы показали перевес, значит, мы узнали, где настоящая и фальшивая серебряные, а также настоящую золотую. Остались 4 золотые, среди которых одна фальшивая. Берём две настоящие серебряные на одну чашу весов, а на вторую любую пару золотых. Если покажет равновесие, значит, нам попались две золотые настоящие монеты. Если же перевесят серебряные, то это будет означать, что на весах одна фальшивая и одна настоящая золотые. Последним взвешиванием легко обнаружить, где из них какая.

[A.Edem]

Только что получилось решить немного другим способом. Потому теперь интересно: каковы авторские решения этих задач?

[Iam]

Решение задачи 4G+4S, которое выложил выше HungryLion, неверно: при равновесии в первых двух взвешиваниях ситуация не идентифицируется.

Также ошибочно решение задачи 6G+5S, которое привел A.Edem. Чтобы убедиться, нужно просто более детально проверить возможные ситуации (расположения нормальных и фальшивых монет) после второго взвешивания, если и в первом, и во втором случаях весы неуравновешены.

Вообще и HungryLion, и A.Edem нужно корректно расписать, куда кладутся какие монеты. Взвешивания удобно представлять набором $(h_1, \dots, h_8),$ где $h_i \in \{-1.0,1\}, $ причем при $h_i=-1$ $i$-я монета кладется на левую чашу, при $h_i=1$ – на правую и при $h_i=0$ не участвует во взвешивании (см. ссылки выше). В задаче можно положить номера золотых монет $1, \dots, 4$ и серебряных $5, \dots, 8$. Далее результат взвешивания: $-1, 0, 1$ – соответственно левая чашка легче, равновесие, тяжелее.
Без нормального представления решения будет много разговоров и мало толку.

[A.Edem]

Iam, я могу одно сказать по этому поводу: расписать всё красиво, научно у меня, скорее всего, не получится. HungryLion же, полагаю, выложил неполный вариант решения потому, как не старался придерживаться красоты стиля изложения ответа, а писал он его для тех, кто действительно пытался своими силами решить эту задачу, для тех, кто мог бы понять его лишь потому, что сам искал ответ, кому не нужно уже подробное расписывание. Лично я лишь в одном месте не сразу уловил его мысль, но когда он поправился и уточнил свою идею, мне сразу стало ясно, что это и есть правильное решение.
Если честно, то чтобы всё подробно расписать, особенно те моменты, которые он упустил по понятной причине ненужности и так понятных объяснений, то пришлось бы использовать ещё очень много ненужных слов, или не совсем много мало кому понятных условных обозначений или чисел. В последней задаче подробное решение будет и того длиннее.
Перепроверив, я не заметил ошибки в решении.

-- 09.08.2016, 01:26 --

Хорошо было бы, если бы уважаемый VAL нас рассудил.