Китайские весы

[arqady]

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

[Capella]

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

Условие: каждая монета пронумерованна (от 1 до 5) и место в уравнении обуславливает чашу.

Сначала 2 взвешивания:
1. 1 vs 2
2. 2 vs 3

Теперь, если иероглифы одинаковые, то фальшивая монета либо 4 либо 5. Тогда третье взвешивание:

3. 1 vs 4

А вот если иероглифы разные, то тогда 4 и 5 монеты точно хорошии.
Тогда третье взвешивание такое:

3. 4 vs 5

Сравнивая иероглифы находим три случая - все иероглифы разные - 2 монета фальшивая.
Или третий иероглиф совпал с каким-то из двух первых. Тогда фальшивая монета из другого равенства, не 2 (т.е. 1 или 3).

[arqady]

Всё правильно! А из двенадцати монет за четыре взвешивания как?

[juna]

Первое взвешивание:
1 2 3 и 4 5 6 (иероглиф А)
Второе взвешивание:
4 5 6 и 7 8 9
если иероглиф А, то фальшивка среди 10 11 12 - за два взвешивания легко определить, зная, что А - равенство
если иероглиф В, то
Третье взвешивание:
7 8 9 и 4 5 6
если иероглиф В, то фальшивка среди 1 2 3, тогда четвертое взвешивание 1 2 и если В, то фальшивка 3, если А, то фальшивка 1, если С, то фальшивка 2
если иероглиф С, то фальшивка среди 7 8 9, тогда четвертое взвешивание 7 8 и если А, то фальшивка 9, если В, то фальшивка 8, если С, то фальшивка 7
если иероглиф А, то фальшивка среди 4 5 6, тогда четвертое взвешивание 4 5 и если А, то фальшивка 5, если В, то фальшивка 4, если С, то фальшивка 6.

[Профессор Снэйп]

А если в общем виде?

Имеется $n$ монет, среди них ровно одна фальшивая. Чему равно минимальное $k$, такое что за $k$ взвешиваний на китайских весах можно найти фальшивую монету?

Полагаю, что при больших $n$ оптимальным будет сначала "расшифровать" иероглифы. Кстати, за какое минимальное количество взвешиваний это можно сделать? За 4 точно можно. (Сначала кладём одну монету на левую чашу и две монеты на вторую. Потом меняем монету на левой чаше. Потом повторяем эти 2 испытания, меняя чаши. После этого значения двух иероглифов точно известны и, следовательно, известно значение третьего.) Ну а за 3 можно?

[Capella]

Профессор Снэйп писал(а):

А если в общем виде?

Полагаю, что при больших $n$ оптимальным будет сначала "расшифровать" иероглифы. Кстати, за какое минимальное количество взвешиваний это можно сделать? За 4 точно можно. (Сначала кладём одну монету на левую чашу и две монеты на вторую. Потом меняем монету на левой чаше. Потом повторяем эти 2 испытания, меняя чаши. После этого значения двух иероглифов точно известны и, следовательно, известно значение третьего.) Ну а за 3 можно?

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

Добавлено спустя 3 минуты 35 секунд:

а три операции будут такими:
1. $a_1$ vs $a_2$
2. $a_1$ vs $a_2 + a_3$
3. $a_4$ vs $a_5$

В худшем случае все монеты правильные (ну или $a_2$ тяжёлая или $a_1$ лёгкая).

[juna]

Пусть
1. $a_1$ vs $a_2$ - иероглиф А
2. $a_1$ vs $a_2+a_3$ - иероглиф А
Предположим, $a_1$ самая тяжелая (не уравновешивается даже двумя монетами), тогда А - перевес слева;
Предположим, $a_2$ - самая тяжелая, тогда А - перевес справа.
Таким образом, мы не можем знать, что означает А.

[Capella]

juna

Конечно погрешность в весе монеты не превышает веса правильной монеты (в моём решении). Но в Вашем случае там считается быстро, поскольку известно, что имеем дело с фальшивой монетой в первом взвешивании. Трудный вариант, когда все монеты правильные.

[arqady]

Julia доказала, что из 14 монет можно определить фальшивую за 4 взвешивания на китайских весах и 14 - это максимальное число монет для 4 взвешиваний.

[juna]

Удалил.

[Capella]

Гипотеза - для достаточно больших $k$ использовать моё самое первое решение для нахождения фальшивой монеты из 5 подмножеств, (т.е. задача 1 с 5 монетами, вместо них множества). Теперь выбор между распределениями будет зависеть от остаточного члена, где естественно интересует $k\;\bmod\;\ 5 = 0$. Если остаток равен 1, то эту самую монету думаю вообще можно не использовать (поскольку если она фальшивая, то все взвешивания дадут один и тот же иероглиф, а если нет, то это не повлияет на результат...)
Вообще с остатками дело интересное, если иметь $k\;\bmod\;\ 5 = 3$, $k\;\bmod\;\ 5 = 2$ или $k\;\bmod\;\ 5 = 4$ , то остаток лучше оставить на $a_4$ и $a_5$ и если понадобиться $a_4$ vs $a_5$ то его можно не использовать, а если $a_1$ vs $a_4$, то полностью оставить его в $a_5$
При нахождении множества с фальшивой монетой повторить разложение, только уже сократив выборку до 3 подмножеств (поскольку знаки вычислены). Зная отклонение фальшивой монеты можно проводить каждый раз лишь одно взвешивание.
Отсюда получается, что первый раз надо делить $k$ на 5, а затем на 3. Выходит $5 \cdot 3^n = k$ (Правда в первый раз может так случится, что фальшивая монета была в $a_5$ и при 3 подмножествах придётся провести дополнительное взвешивание для определения отклонения).

[Профессор Снэйп]

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

Я вижу, как это сделать за 4 взвешивания. Первые два таковы:

$a_1$ vs $a_2$
$a_3$ vs $a_4$

Если оба иероглифа одинаковы, то все четыре монеты настоящие и иероглиф обозначает равенство. После этого достаточно произвести взвешивание

$a_1$ vs $a_2 + a_3$

и все три иероглифа известны. Если же иероглифы различны, то можно произвести взвешивание

$a_5$ vs $a_6$

после чего опять станут известны четыре настоящие монеты и следующим взвешиванием иероглифы опять будут расшифрованы.

Ну а можно ли управиться за 3 взвешивания?

P. S. Мы считаем, что отношение веса фальшивой монеты к весу настоящей может быть любым положительным действительным числом, отличным от единицы.

[Capella]

Профессор Снэйп

Честно говоря я не совсем понимаю где Вы взвешиваете в 4-ый раз. По моему важно ещё так - не взвешивать монеты по одиночке, а разбить их изначально на группы, Таким образом после первых трёх взвешиваний можно отсеять какое-то количество монет.

[juna]

to Профессор Снэйп
Можно за два взвешивания.
Первое:
все монеты vs пусто - иероглиф А - перевес слева
Второе:
пусто vs все монеты - иероглиф В - перевес справа
иероглиф С - равенство.

[Профессор Снэйп]

juna писал(а):

to Профессор Снэйп
Можно за два взвешивания.
Первое:
все монеты vs пусто - иероглиф А - перевес слева
Второе:
пусто vs все монеты - иероглиф В - перевес справа
иероглиф С - равенство.

Да, вот оно: тривиальное неучтённое решение!

Ну а если запретить взвешивания, при которых одна из чаш пустая (дескать, софт для китайских весов микрософт писал и они в этом случае вместо результатов взвештвания выдают ошибку деления на $0$ )?

Можно даже было бы задать ещё более жёсткое ограничение, потребовав, чтобы количество монет на каждой из чаш при каждом взвешивании было одинаково. Однако в этом случае задача окажется неразрешимой. Действительно, при перестановке иероглифов "меньше" $\leftrightarrow$ "больше" и перестановке весов монет весы будут при любых взвешиваниях показывать одинаковые результаты.

Добавлено спустя 5 минут 8 секунд:

Capella писал(а):

Профессор Снэйп

Честно говоря я не совсем понимаю где Вы взвешиваете в 4-ый раз. По моему важно ещё так - не взвешивать монеты по одиночке, а разбить их изначально на группы, Таким образом после первых трёх взвешиваний можно отсеять какое-то количество монет.

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