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

[Iam]

A.Edem, какое здесь может быть судейство! Прежде всего нужно, чтобы Вы сами детально разобрались с вопросом, который излагаете. Ваше первое взвешивание делит множество ситуаций (их общее число 75) на три подмножества, содержащих соответственно 30 (левая тяжелее), 15 (равновесие), 30 (правая тяжелее). Ясно, что в случае неравновесия невозможно из 30 ситуаций за 3 взвешивания идентифицировать одну. Пусть хоть все хором будут говорить, что Ваш алгоритм работает, он все равно останется дефектным.

[A.Edem]

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

Перепроверив, я не заметил ошибки в решении.

На тот момент я проверил лишь решение, предоставленное HungryLion.
А только что сделал проверку за собой, и тут действительно увидел одну ошибку. Это я признаЮ. Необходима доработка. Но вот в первой задаче, хоть стреляй, не вижу ошибки.

[A.Edem]

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

Только что получилось решить немного другим способом.

Придётся описать этот второй способ, которым я решил вторую задачу, так как первый способ, по всей видимости, доработке не подлежит.
Сначала подумаю, как его представить всеобщему вниманию, чтобы было понятней..

[A.Edem]

(Оффтоп)

Теперь объяснения. На первом этапе делим золотые монеты на три равные кучи по две в каждой. Берём две любые пары и ставим их на разные чаши весов. Если покажет равновесие, то, как видно из картинки, равновесие возможно лишь в двух случаях: когда на обоих чашах либо по две настоящих золотых, либо по настоящей с фальшивой. В этом случае из каждой чаши вынимаем по одной золотой монете наугад и меняем их местами (но запоминаем, откуда какая была пара). А также в каждую чашку докладываем по одной любой серебряной. И снова взвешиваем. Если опять весы показали равновесие, то, как видно из картинки (пункт 2 первого этапа), снова возможны два варианта: это когда на чашах окажется по две настоящих золотых и одной настоящей серебряной, либо по настоящей и фальшивой золотой и настоящей серебряной. В этом случае третьим действием мы взвешиваем между собой две золотые монеты из левой или правой чаши (не важно). Если они окажутся одинаковыми по весу, то это будет означать, что перед нами две настоящие золотые, что в соседней чашке тоже две настоящие, и что в оставшейся паре золотых две фальшивые. Если перевесит одна чашка, то в ней будет настоящая золотая, а фальшивая в соседней паре, которую запоминали вначале. Соответственно, в более лёгкой чаше будет фальшивая, а её первоначальная пара окажется настоящей монетой.
После всего этого останется определить фальшивую монету среди двух оставшихся настоящих серебряных и и одной фальшивой. Это сделать нетрудно всего одним взвешиванием.

[VAL]

Предъявлю свое (одно из) решение задачи с 4-я золотыми и четырьмя серебряными монетами.
Надеюсь, на этом примере будет ясен и способ оформления, и способ решения подобных задач.
Пронумеруем золотые монеты, а серебряные снабдим метками a, b, c, d.
Результаты первых двух взвешиваний представлены в таблице.
\begin{tabular}{|l|с|с|с|} \hline № & Фальшивки & 1a - 2b & 2a - 3c & \\ \hline 1.& 12a & < & < &\\ \hline 2.& 12b & > & < &\\ \hline 3.& 12c & = & = &\\ \hline 4.& 12d & = & < &\\ \hline 5.& 13a & < & = &\\ \hline 6.& 13b & = & > &\\ \hline 7.& 13с & < & > &\\ \hline 8.& 13d & < & > &\\ \hline 9.& 14a & < & < &\\ \hline 10.& 14b & = & = &\\ \hline 11.& 14c & < & > &\\ \hline 12.& 14d & < & = &\\ \hline 13.& 23a & = & < &\\ \hline 14.& 23b & > & = &\\ \hline 15.& 23c & > & > &\\ \hline 16.& 23d & > & = &\\ \hline 17.& 24a & = & < &\\ \hline 18.& 24b & > & < &\\ \hline 19.& 24c & > & = &\\ \hline 20.& 24d & > & < &\\ \hline 21.& 34a & < & = &\\ \hline 22.& 34b & > & > &\\ \hline 23.& 34c & = & > &\\ \hline 24.& 34d & = & > &\\ \hline \end{tabular}
Видно, что ни одна из комбинаций исходов не встречается более трех раз. Соответственно, для каждой легко побирается третье взвешивание, определяющее комбинацию фальшивых монет.

[HungryLion]

Разобрался с шестью золотыми и пятью серебряными. Как применить метод решения VAL не понял, так что пришлось по старинке. С оформлением тоже не всё гладко, как у VAL не получилось, зато теперь и перед Iam не стыдно будет.

(Оффтоп)

1..6 золотые монеты, a..e - серебряные.
Первое взвешивание $12 - 34$, дальше в таблицах (запись $= 1ab - 2cd$ читается как "Если в предыдущем взвешивании было равенство, то сравниваем $1ab$ и $2cd$"):
\begin{tabular}{|l|l|l|l|c|} \hline N & II & III & IV & Результат \\ \hline 1 & = 1ab - 2cd & = 1ac - 3bd & = 1 - 2 & = 56e \\ \hline 2 & & & & < 14d \\ \hline 3 & & & & > 23a \\ \hline 4 & & & < 1 - 4 & = 14c \\ \hline 5 & & & & < 13c \\ \hline 6 & & & & > 24a \\ \hline 7 & & & > 2 - 3 & = 23b \\ \hline 8 & & & & < 24b \\ \hline 9 & & & & > 13d \\ \hline 10 & & < a - b & = 3 - 4 & < 13e \\ \hline 11 & & & & > 14e \\ \hline 12 & & & < 3 - 4 & = 56a \\ \hline 13 & & & & < 13a \\ \hline 14 & & & & > 14a \\ \hline 15 & & & > 3 - 4 & = 56b \\ \hline 16 & & & & < 13b \\ \hline 17 & & & & > 14b \\ \hline 18 & & > c - d & = 3 - 4 & < 23e \\ \hline 19 & & & & > 24e \\ \hline 20 & & & < 3 - 4 & = 56c \\ \hline 21 & & & & < 23c \\ \hline 22 & & & & > 24c \\ \hline 23 & & & > 3 - 4 & = 56d \\ \hline 24 & & & & < 23d \\ \hline 25 & & & & > 24d \\ \hline \end{tabular}

\begin{tabular}{|l|l|l|l|c|} \hline N & II & III & IV & Результат \\ \hline 26 & < 5ab - 6cd & = 1a - 2b & = a - b & = 12e \\ \hline 27 & & & & < 26a \\ \hline 28 & & & & > 16b \\ \hline 29 & & & < c - d & = 16a \\ \hline 30 & & & & < 15c \\ \hline 31 & & & & > 15d \\ \hline 32 & & & > c - d & = 26b \\ \hline 33 & & & & < 25c \\ \hline 34 & & & & > 25d \\ \hline 35 & & < a - b & = 1 - 2 & < 15e \\ \hline 36 & & & & > 25e \\ \hline 37 & & & < 1 - 5 & = 15a \\ \hline 38 & & & & < 12a \\ \hline 39 & & & & > 25a \\ \hline 40 & & & > 1 - 5 & = 15b \\ \hline 41 & & & & < 12b \\ \hline 42 & & & & > 25b \\ \hline 43 & & > c - d & = 1 - 2 & < 16e \\ \hline 44 & & & & > 26e \\ \hline 45 & & & < 1 - 6 & = 16c \\ \hline 46 & & & & < 12c \\ \hline 47 & & & & > 26c \\ \hline 48 & & & > 1 - 6 & = 16d \\ \hline 49 & & & & < 12d \\ \hline 50 & & & & > 26d \\ \hline \end{tabular}

\begin{tabular}{|l|l|l|l|c|} \hline N & II & III & IV & Результат \\ \hline 51 & > 5ab - 6cd & = 3a - 4b & = a - b & = 34e \\ \hline 52 & & & & < 46a \\ \hline 53 & & & & > 36b \\ \hline 54 & & & < c - d & = 36a \\ \hline 55 & & & & < 35c \\ \hline 56 & & & & > 35d \\ \hline 57 & & & > c - d & = 46b \\ \hline 58 & & & & < 45c \\ \hline 59 & & & & > 45d \\ \hline 60 & & < a - b & = 3 - 4 & < 35e \\ \hline 61 & & & & > 45e \\ \hline 62 & & & < 3 - 5 & = 35a \\ \hline 63 & & & & < 34a \\ \hline 64 & & & & > 45a \\ \hline 65 & & & > 3 - 5 & = 35b \\ \hline 66 & & & & < 34b \\ \hline 67 & & & & > 45b \\ \hline 68 & & > c - d & = 3 - 4 & < 36e \\ \hline 69 & & & & > 46e \\ \hline 70 & & & < 3 - 6 & = 36c \\ \hline 71 & & & & < 34c \\ \hline 72 & & & & > 46c \\ \hline 73 & & & > 3 - 6 & = 36d \\ \hline 74 & & & & < 34d \\ \hline 75 & & & & > 46d \\ \hline \end{tabular}

[A.Edem]

Продолжаю описание (не взирая на лаконичность оппонентов!)

(Оффтоп)

2 этап.
Если после первого взвешивания на первом этапе был перевес, то, как видим из второго рисунка, возможны два варианта (расписывать уж не буду, так как и так хорошо видно, где какие будут монеты, и что перевесит). В случае подобного перевеса мы берём две золотые монеты из более лёгкой пары и ставим их на разные чаши весов. К ним ставим по одной любой монете из остаточной пары золотых ("остаток" на рисунке), запоминая, естественно, откуда какая была пара, а также по одной любой монете наугад из серебряных.
Если весы покажут перевес, то тут возможны четыре варианта (а,б,в,г на рис.). После этого третьим взвешиванием мы кладём на противоположные чаши весов (только что взвешенные) одну серебряную и одну любую золотую монету - все они из более лёгкой чаши. Если перевесит серебряная, значит, она настоящая, а две золотые из этой же чаши соответственно фальшивые; если весы уравновесятся или покажут, что серебряная фальшивая, а золотая настоящая, то четвёртым действием мы взвешиваем между собой две золотые монеты из тяжелой чаши (на рисунке немного неправильно изобразил). Если покажет на весах равновесие, то значит в противоположной чаше осталась одна фальшивая; если одна фальшивая и одна настоящая, то (что было и так ясно) в противоположной осталась золотая настоящая.
Также на рисунке не изобразил цепь событий, когда на втором этапе после второго действия весы показали бы равновесие. Равновесие там возможно было бы лишь в двух случаях: когда бы на одной чаше весов оказались бы две настоящие золотые и одна настоящая серебряная, а на второй чаше соответственно также, и когда на обоих чашах были бы настоящая с фальшивой золотые и настоящая серебряная. Взвесив бы после этого третьим действием между собой две золотые монеты из любой чаши весов, мы бы узнали, где находятся фальшивые и настоящие золотые, а четвёртым действием провели бы заключительную операцию над тремя оставшимися серебряными, среди которых бы осталась одна фальшивая.

-- 09.08.2016, 22:31 --

(Оффтоп)

3 этап.
Как видно из третьего рисунка, в первом этапе после второго взвешивания естественно возможен перевес. Я изобразил все пять возможных вариантов. То есть к четырём нам уже знакомым из второго этапа добавился ещё один (д). Вспомнив, как я проводил выявление монет с подобными вероятными вариантами, можно заметить, что появилась лишь одна новая вероятность. То есть, если мы обнаружили, что серебряная - фальшивая, а одна из золотых (с которой мы её взвешиваем в более лёгкой паре) настоящая, то рядом будет: 1. Фальшивая золотая - если измерение противоположных золотых покажет нам, что среди них были фальшивая и настоящая монеты; 2. Настоящая золотая - если среди противоположных будут две настоящие.
Четвёртое взвешивание здесь снова-таки может пригодиться, если выявится, что среди серебряных были две настоящие.
Вот и весь ответ!

-- 09.08.2016, 23:03 --

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

зато теперь и перед Iam не стыдно будет.

А мне главное, что перед собой не стыдно - ведь старался, как мог! Только вот немного любопытно: хоть кому-нибудь понятен ход моих рассуждений и описаний?

[Iam]

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

Если перевесит серебряная, значит, она настоящая, а две золотые из этой же чаши соответственно фальшивые;
Вот и весь ответ!
..............
Только вот немного любопытно: хоть кому-нибудь понятен ход моих рассуждений и описаний?

Алгоритм чуть-чуть дефективен. В случае перевес-перевес и третьем перевесе серебряной среди серебряных будет четыре кандидатуры на ущербность.

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

Разобрался с шестью золотыми и пятью серебряными. Как применить метод решения VAL не понял, так что пришлось по старинке. С оформлением тоже не всё гладко, как у VAL не получилось, зато теперь и перед Iam не стыдно будет.

HungryLion, Ваше решение увидел только-что. Попробую разобраться.
Кстати, по поводу ошибок не стоит комплексовать, хотя сам имею такой недостаток. Ваш и A.Edem’а энтузиазм и любознательность радуют и притягивают внимание к теме.

-- 09.08.2016, 21:05 --

HungryLion, Ваш алгоритм для задачи 6G+5S прекрасно работает. Расписывать последнее взвешивание в данном случае не обязательно, т. к. 2 или 3 ситуации над {0,1} всегда разделимы одним взвешиванием.
В задаче 4G+4S у меня получился статический алгоритм (все 3 взвешивания спланированы заранее и не меняются от результатов предыдущих взвешиваний). Для 6G+5S такого не получилось. Как будто выходило (вчера) что-то типа двухкаскадного, но ... другие дела.

[chh]

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

А мне главное, что перед собой не стыдно - ведь старался, как мог! Только вот немного любопытно: хоть кому-нибудь понятен ход моих рассуждений и описаний?

Для меня лично только ваш ход мыслей нагляден и понятен!

[HungryLion]

chh в сообщении #1143071 писал(а):

HungryLion, Ваш алгоритм для задачи 6G+5S прекрасно работает. Расписывать последнее взвешивание в данном случае не обязательно, т. к. 2 или 3 ситуации над {0,1} всегда разделимы одним взвешиванием.

Спасибо за проверку. Последнее взвешивание я, скорее, для себя расписывал, чтобы по результатам легко было проверить, что в цифрах/буквах не описался.

chh в сообщении #1143071 писал(а):

В задаче 4G+4S у меня получился статический алгоритм (все 3 взвешивания спланированы заранее и не меняются от результатов предыдущих взвешиваний). Для 6G+5S такого не получилось. Как будто выходило (вчера) что-то типа двухкаскадного, но ... другие дела.

Мне такие алгоритмы тоже больше нравятся, только искать их мне сложнее.

Чтобы развеять вопрос с 4G+4S задачей опишу первые два взвешивания более формально:
1..4 золотые
a..d серебряные

I. 1 - 2
II. = 1a - 4b, <> 3a - 4b

Соответственно, при равновесии в первых двух взвешиваниях возможны только комбинации 12b и 34a.

[A.Edem]

chh в сообщении #1143071 писал(а):

Для меня лично только ваш ход мыслей нагляден и понятен!

Видимо, только мы с вами тут не математики, а так.. лирики!

-- 10.08.2016, 12:44 --

Iam в сообщении #1143031 писал(а):

Алгоритм чуть-чуть дефективен. В случае перевес-перевес и третьем перевесе серебряной среди серебряных будет четыре кандидатуры на ущербность.

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

-- 10.08.2016, 13:07 --

Ах, да - к критике я отношусь нормально! Мне главное уяснить, в чём заключалась моя ошибка. И в конечном итоге не важно: верно или неверно было моё решение. Если неверно - пусть - позже решу, или кто-нибудь другой решит. И отчего тут комплексовать?! Главное это интерес в процессе разгадывания, сам процесс.

[Iam]

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

Мне такие алгоритмы тоже больше нравятся, только искать их мне сложнее.

Такие (статические) алгоритмы не всегда приводят к лучшему результату. Например, в задаче с $n=11 $(число монет), $t \le 2$ (число фальшивых), $q=3$ (число градаций весов), о которой я говорил ранее, статический алгоритм содержит не менее 6 взвешиваний, в то время у оптимального алгоритма их всего 5. Интересно отметить, что параметры этого алгоритма лежат на верхней границе Хемминга для $q=3$ и при данном значении q уравнение, соответствующее этой границе, по-видимому, в целых числах не имеет других нетривиальных решений. Вообще-то этот факт установлен лишь для $t=2$.

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

Чтобы развеять вопрос с 4G+4S задачей опишу первые два взвешивания более формально ...

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

A.Edem, Ваш подремонтированный алгоритм кондиционен, к тому же он украшен лирическим изложением.
Вообще-то для лирика задачи нетривиальные. Бывало, что физики годами не могли продвинуться в простенькой задачке, ответ на которую лирик выдал в течение 3 мин, прикинув в уме и глядя в потолок. Эту задачку я, пожалуй, выложу в отдельной теме.

На всякий случай выкладываю вариант представления двух взвешиваний на примере алгоритма для задачи 4G+4S с проверочной матрицей $H$ (строки соответствуют взвешиваниям):
1 -1 0 0 0 0 0 0
0 0 1 0 1 -1 -1 0

Таблица синдромов для ситуаций $x \in X: s(x) = [ x H^T ] $, где символом [] обозначено выполнение операции sign() над компонентами синдрома.

\begin{tabular}{|l|l|l|} \hline № & Ситуация, x & Синдром, s(x) \\ \hline 1 & 0 0 1 1 0 0 0 1 & 0 1 \\ \hline 2 & 0 0 1 1 0 0 1 0 & 0 0 \\ \hline 3 & 0 0 1 1 0 1 0 0 & 0 0 \\ \hline 4 & 0 0 1 1 1 0 0 0 & 0 1 \\ \hline 5 & 0 1 0 1 0 0 0 1 & -1 0 \\ \hline 6 & 0 1 0 1 0 0 1 0 & -1 -1 \\ \hline 7 & 0 1 0 1 0 1 0 0 & -1 -1 \\ \hline 8 & 0 1 0 1 1 0 0 0 & -1 1 \\ \hline 9 & 1 0 0 1 0 0 0 1 & 1 0 \\ \hline 10 & 1 0 0 1 0 0 1 0 & 1 -1 \\ \hline 11 & 1 0 0 1 0 1 0 0 & 1 -1 \\ \hline 12 & 1 0 0 1 1 0 0 0 & 1 1 \\ \hline 13 & 0 1 1 0 0 0 0 1 & -1 1 \\ \hline 14 & 0 1 1 0 0 0 1 0 & -1 0 \\ \hline 15 & 0 1 1 0 0 1 0 0 & -1 0 \\ \hline 16 & 0 1 1 0 1 0 0 0 & -1 1 \\ \hline 17 & 1 0 1 0 0 0 0 1 & 1 1 \\ \hline 18 & 1 0 1 0 0 0 1 0 & 1 0 \\ \hline 19 & 1 0 1 0 0 1 0 0 & 1 0 \\ \hline 20 & 1 0 1 0 1 0 0 0 & 1 1 \\ \hline 21 & 1 1 0 0 0 0 0 1 & 0 0 \\ \hline 22 & 1 1 0 0 0 0 1 0 & 0 -1 \\ \hline 23 & 1 1 0 0 0 1 0 0 & 0 -1 \\ \hline 24 & 1 1 0 0 1 0 0 0 & 0 1 \\ \hline \end{tabular}

Такое представление позволяет рассматривать алгоритм взвешивания как последовательность разбиений некоторого дискретного множества из $R^n$ гиперплоскостью $[h,x]=0$, где $h$ - вектор в $R^n$ (в данном сл. определяемый строкой проверочной матрицы).

Кстати, как выяснилось, третья проверка (0 0 0 1 0 1 -1 -1 ) (которая предполагалась для статического алгоритма) в одном (единственном) случае повторила синдром (0 1 0), поэтому вопрос о существовании статического алгоритма для этой задачи остался открытым. При возможности потом подумаю.

[A.Edem]

Iam в сообщении #1143094 писал(а):

A.Edem, Ваш подремонтированный алгоритм кондиционен

Спасибо! Наконец-то я дошёл до кондиции
Каскады я тоже предполагал, но понимал, что решение подобным путём будет совсем непростым занятием.

[YAlbert]

вот мой вариант действий_ кладем на каждую чащу весов все монеты в одну золотые ,во вторую все серебряные ,т.е. 2к2 золотые и 3к1 серебряные, при этом чащи весов перевешивают в сторону серебра ,а далее так одновременно за раз вынимаем с каждых чащ по одной монеты и смотрим наперевес каждых сторон (записывая-определяя тем самым фальшивые и настоящие монеты),ну и далее ,в таком темпе ,вот и все ,можно решить математическим путем -весовым соотношением.смысл если после комбинации с 1 и 1 ,будет 1 и 0,то будет перевес по любому ,а если с комбинации с 1 и 0 .будет 1 и 1 ,то чаща весов выравниваться ,вот и есть результат той монеты которую уже достали с чащи ,,а если будет подряд одинаковая комбинация например 1 и 1 или 0 и 0 ,то все равно за три действия будет результат ,ведь в серебре и золоте всего три не настоящих ,кстати четвертый вариант остается на чаще весов ,который уже не требует действий . для этого и есть регистрация момента перевесов или выравнивания ,например был вариант 1 и 0 в пользу серебра в начале взяли серебро настоящие,т.е. -1 ,а с золота 0-фальщивка ,то получается после этого ,что весы выравниваются ,т.к. ,в тех и др. чащах ,будет комбинация поровну ,там две настоящие и в др.,т.е. по 1и 1 там и там 1и 1, значит получается если был перевес серебра ,то там три настоящих ,против двух зол. настоящих ,а если возьмем настоящую с серебра по условию одну с каждых сторон,то будет поровну тех и тех 2 к2 настоящих ,значит получается взяли серебряную настоящую.а если бы взяли одинаковых поделки ничего не поменялось ,то ведь есть еще три варианта не считая четвертого в конце в чащах ,вот и заключается регистрация в моментах перевесов или выравнивания или ничего ,но кол-во вариантов это не меняет.в принципе для этого здесь варианта не может быть ,более трех вариантов с тремя монетами,т.к. монеты фальш. три ,поставьте все комбинации с ними (с фаль.) на моем рис в двоичном варианте_ 0 l 0
0 l 1
1 l 1
1 l 1 слева золотые монеты ,а справа серебренные ,посередине перегородка
U_U -чащи весов

[A.Edem]

Признаюсь, это я поспорил с пользователем YAlbert, что его решение неверно. Только не смог это доказать словами. Возможно, что я был не прав. Поэтому предложил ему выставить свою версию публично, дабы нашу дискуссию разрешили.