Задача на взвешивание монет

[12d3]

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

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

Ответ: 5.
Первые три взвешивания такие:

1,2,3 vs 4,5,6
1,2,4 vs 3,7,8
1,3,4 vs 2,9,10

Из 27 исходов рассмотрим только 6 принципиально различных: ровно три равенства, ровно два равенства, одно равенство и два неравенства в одну сторону, одно равенство и два неравенства в разные стороны, три неравенства в одну сторону, три неравенства в разные стороны. Остальные получаются либо циклической перестановкой, либо заменой всех фальшивых легких на фальшивые тяжелые и наоборот.
Случай 1.

1,2,3 = 4,5,6
1,2,4 = 3,7,8
1,3,4 = 2,9,10

В этом случае 1,2,3,4 настоящие, и либо в одной из пар (5,6),(7,8),(9,10) две фальшивых разного веса, либо 11 какая угодно. Четвертым взвешиванием сравниваем 5,7,9 и 6,8,10. Если равенство, то сравним 11 с настоящей, иначе сравним 6,7 с двумя настоящими.
Случай 2.

1,2,3 = 4,5,6
1,2,4 = 3,7,8
1,3,4 > 2,9,10

Тут 5,6,7,8 настоящие. Сравним 9 и 10. Если равенство, то либо они обе легкие фальшивые, либо 1 тяжелая и 2 легкая, либо 2 и 3 тяжелые, и тогда сравнив 2 с настоящие, определим один исход из трех возможных. Если же 9, например, тяжелее 10, то 10 фальшивая легкая, и последним взвешиванием сравним 11 с настоящей.
Случай 3.

1,2,3 = 4,5,6
1,2,4 > 3,7,8
1,3,4 < 2,9,10

Тут 1,4,11 настоящие. Либо в паре (7,8) одна легкая и в паре (9,10) одна тяжелая, либо 2 тяжелая и 3 легкая, либо 2 тяжелая и в паре (5,6) одна тяжелая, либо 3 легкая и в паре (5,6) одна легкая. Четвертым взвешиванием сравним 1,7 и 3,5.
Если равенство, то либо 2 и 6 тяжелые, либо 8 легкая и одна в паре (9,10) легкая. Тогда последним взвешиванием сравним (2,9) и две настоящих.
Если в четвертом взвешивании 1,7 тяжелее, чем 3,5, то 3 фальшивая легкая, и последним взвешиванием сравним (2,5) с двумя настоящими.
Если в четвертом взвешивании 1,7 легче, чем 3,5, то либо 2 и 5 тяжелые, либо 7 легкая и одна в паре (9,10) легкая. Последним взвешиванием сравним (2,9) и две настоящих.
Случай 4.

1,2,3 = 4,5,6
1,2,4 > 3,7,8
1,3,4 > 2,9,10

Тут 2,3,11 настоящие. Либо в паре (7,8) одна легкая и в паре (9,10) одна легкая, либо 1 тяжелая и кто-то в тройке (4,5,6) тяжелый, либо 4 тяжелая и одна монета в паре (5,6) легкая.
Четвертым взвешиванием сравним 1,7 и 4,9.
Если равенство, то либо 1 и 4 тяжелые, либо 7 и 9 легкие, либо 8 и 10 легкие. Последним взвешиванием сравним (1,7) и две настоящих.
Если в четвертом взвешивании 1,7 тяжелее, чем 4,9, то либо 7 и 8 легкие, либо 1 тяжелая и в паре (5,6) одна тяжелая. Последним взвешиванием сравним (5,7) и две настоящих.
Если в четвертом взвешивании 1,7 легче, чем 4,9, то либо 7 и 10 легкие, либо 4 тяжелая и одна в паре (5,6) легкая. Последним взвешиванием сравним 5 и 7.
Случай 5.

1,2,3 > 4,5,6
1,2,4 > 3,7,8
1,3,4 < 2,9,10

Тут 2 фальшивая тяжелая, 1,3,4 настоящие, и либо одна в четверке (5,6,7,8) легкая, либо одна в паре (9,10) тяжелая, либо 11 какая угодно. Четвертым взвешиванием сравним 5,6,9 и 7,8,10.
Если равенство, то сравним 11 с настоящей. Иначе если, например, 5,6,9 легче, чем 7,8,10, то сравним 5,10 с двумя настоящими.
Случай 6.

1,2,3 > 4,5,6
1,2,4 > 3,7,8
1,3,4 > 2,9,10

Тут 1 фальшивая тяжелая, 2,3,4 настоящие, и либо одна в шестерке (5,6,7,8,9,10) легкая, либо 11 какая угодно. Четвертым взвешиванием сравним 5,6,9 и 7,8,10.
Если равенство, то сравним 11 с настоящей. Иначе если, например, 5,6,9 легче, чем 7,8,10, то сравним 5 с 6.

Всего у нас имеется 243 исхода, и после трех взвешиваний перечислено по 9 возможных вариантов. Значит, ни один исход не упущен. Конец.

P.S. У меня вызвал немалое удивление тот факт, что первые три взвешивания можно произвести совершенно не глядя, и только потом разбираться, что там навзвешивалось. Жалко, последние два не выстраивались ни в какую симметричную схему.

-- Вс авг 13, 2017 00:37:49 --

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

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

Пусть мы первым взвешиванием кладем по $k$ монет на чаши и у нас равенство. Возможные варианты: на чашах по одной фальшивой, на одной из чаш две фальшивых, на чашах настоящие, а среди остальных не более двух фальшивых. Если посчитать суммарное количество исходов (один исход - это один набор фальшивых монет, без уточнения их веса), получится величина $4(k-3)^2+31$. Так что меньше 31 исхода после одного взвешивания не выйдет. Значит, четырех взвешиваний не хватит. А как сделать за 5, см. выше.

[Iam]

12d3,
я восхищен таким быстрым и точным решением!
Общая постановка и некоторые детали по задаче можно найти в Википедии (раздел «Обобщения») .
В общем плане задача ставится как задача выделения (идентификации) элемента дискретного шара в метрике Хэмминга путем последовательного его разбиения гиперплоскостями в $ R^n $ на три части.
Уникальность параметров состоит в том, что объем шара равен $ 3^5=243 $ и каждая гиперплоскость, соответствующая взвешиванию, должна делить область неопределенности ровно на 3 части.
Можно построить, как минимум, двухкаскадный алгоритм. На первом этапе всего возможно 7 проверочных матриц, из которых лишь 2 матрицы содержат четное число элементов в строках. Остальные 5 матриц содержат строки с 9-ю элементами т. е. предполагают использование при взвешивании дополнительной эталонной монеты.
Некоторую информацию добавлю позже (сейчас длительный переезд).

[Iam]

Поправка к предыдущему

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

На первом этапе всего возможно 7 проверочных матриц, из которых лишь 2 матрицы содержат четное число элементов в строках.

Должно быть «четное число ненулевых элементов».

Здесь приводятся две возможные матрицы, определяющие первые три взвешивания.

Все другие варианты первых трех взвешиваний могут быть лишь эквивалентны одному из указанных.
Точки области неопределенности в данной задаче определяются почти также, как подсчитываются варианты исправляемых ошибок для совершенного троичного кода Голея, однако матрица кода Голея для нахождения двух фальшивых монет в данном случае не работает по причине различия метрик в задаче исправления ошибок и задаче отыскания фальшивых монет.
Надо заметить, что все алгоритмы отыскания одной фальшивой монеты могут быть построены на основе проверочной матрицы соответствующего совершенного троичного кода Хэмминга. Однако для обеспечения четности ненулевых элементов в строках матрицы удаляется один столбец, что приводит к нарушению указанной выше уникальности, т. е. объем области неопределенности оказывается не равным степени числа 3.
По задаче 1

12d3 в сообщении #1240329 писал(а):

Пусть мы первым взвешиванием кладем по $k$ монет на чаши и у нас равенство. Возможные варианты: на чашах по одной фальшивой, на одной из чаш две фальшивых, на чашах настоящие, а среди остальных не более двух фальшивых. Если посчитать суммарное количество исходов (один исход - это один набор фальшивых монет, без уточнения их веса), получится величина $4(k-3)^2+31$. Так что меньше 31 исхода после одного взвешивания не выйдет. Значит, четырех взвешиваний не хватит. А как сделать за 5, см. выше.

12d3, есть неясности с обоснованием. Всего область неопределенности в задаче 1 содержит $ V=1+C_{11}^1+C_{11}^2=67 <81=3^4 $ ситуаций. Каждое взвешивание в принципе может разбить область, имеющуюся после предыдущего взвешивания, на 3 части. По-видимому, просто на основе недостаточности 4-x взвешиваний для данной области неопределенности доказательство по первой задаче проходить не должно. Можете пояснить ваше обоснование более детально?

[12d3]

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

Всего область неопределенности в задаче 1 содержит $ V=1+C_{11}^1+C_{11}^2=67 <81=3^4 $ ситуаций. Каждое взвешивание в принципе может разбить область, имеющуюся после предыдущего взвешивания, на 3 части.

Ага, и надо, чтобы в каждой части было не более 27 исходов. Я доказываю, что всегда будет одна часть, в которой не меньше 31 исхода, каким бы первое взвешивание ни было.

[Iam]

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