Фальшивые монеты.

[heap]

bot писал(а):

А 8/15 проверил, раскладка для первого взвешивания 2:2:1 и она хорошо сбалансирована, отступления караются потерями.
Возможностей для улучшения не нашёл.

9:9:4 дало бы 6/11 ( что больше, чем 8/15 ) , но , к сожалению, ни 6/11, ни 8/15 недостижимо даже если уметь различать между разновесом в одну и две фальшивые монеты. Нужно еще условие, что фальшивых монет ровно 3.

[bot]

По поводу 6/11 глубоко не задумывался, однако не очень понимаю, как может помочь знание точного числа фальшивых.
В случае равновесия 6/11 легко получается без знания числа фальшивых при равновесии, а при сильном неравновесии даже больше, а вот если будет слабое неравновесие, то возможны два случая по числу фальшивых в группах 0,1,2 и 1,2,0 с раскладом общего количества монет 9:9:4. Что-то не вижу 6/11 в этой ситуации.

Ну а для 2:2:1 у Руста всё в порядке было без лишней информации о числе фальшивых монет. Возможны некоторые отклонения от им задуманного, но вряд ли значительные.
1) Первое взвешивание даёт равновесие. Тогда за два взвешивания получаем 2/3 (2/5 + 2/5)=8/15
2) Первое взвешивание дало сильное неравновесие. Тогда забираем 2/5 и из маленькой группы за одно взвешивание забираем 2/3 * 1/5=2/15. Итого 2/5 + 2/15 = 8/15 и имеем возможность за третье взвешивание забрать ещё 2/3 остатка этой группы.
3) Первое взвешивание дало слабое неравновесие. Расклад по числу фальшивых тогда либо 1,2,0 либо 0,1, не более 2.
За второе взвешивание, разделив первую группу пополам, находим 1/5 настоящих при первом раскладе и 2/5 при втором.
Таким образом, перед третьим взвешиванием мы знаем расклад.
При первом раскладе мы уже взяли 1/5 из первой группы, забираем 1/5 - третья группа и из половины первой группы, содержащей одну фальшивую монету, забираем 2/3 * 1/5. Итого 2/5 + 2/3 * 1/5 = 8/15.
При втором раскладе 2/5 у нас уже есть и ещё можем взять 2/3 * 2/5, то есть в совокупности больше 8/15.

[Руст]

Моё решение несколько другое, когда первый раз неравновесие. При этом достаточно только различать два вида неравновесия, если они встречаются. При втором взвешивании кладём половину из меньшего веса A и остаток С (который не взвешивали). При равновесии они чистые и получаем 1/5+1/5+(2/3)*1/5)=8/15. Если перевесил A, так же, только берём 2/3 от дополнения А. В этих случаях не требуется знание, когда был перевес больше.
Если перевесил С, то необходимо знание, когда весы отклонялись быстрее при первом взвешивании или при втором. Так как в этом случае перевесы (2,1) или (1,2).
Интересно было бы узнать, как получилось 6/11. Я не смог до этого додуматься.

[heap]

Руст писал(а):

Интересно было бы узнать, как получилось 6/11. Я не смог до этого додуматься.

Виноват, ошибся.

[kknop]

maxal в сообщении #51180 писал(а):

heap писал(а):

maxal писал(а):

А свежеописанного способа дележа асимптотически худшая прибыль: 5/12 n.

Если не врать в арифметике , то получаем $\left\lceil \frac{6}{13}\cdot n\right\rceil.$

Прикольно, что вы без меня обошлись в этой теме. Ладно, тогда подкину дровишек. $\frac{6}{13}$ не является максимально возможным (асимптотически) значением. При условии "не более трёх фальшивых" можно найти, например, 7 настоящих монет из 15.