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

[bot]

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

P.S. Пререработка задачи с Олимпиады.

[maxal]

Ну что-то типа 4/9 n можно унесть.

Сначала кладем по n/2 монет на каждую чашку весов, берем ту часть, что нетяжелее другой. Тогда в ней не более одной фальшивки.
Разбиваем на три части по n/6 монет и кладем две из них на весы. В случае равновесия забираем эти две части себе, или же забираем ту часть, что легче, и оставшуюся. Невзятую часть опять разбиваем на три и за одно взвешивание определяем две части без фальшивок - забираем их себе.
В итоге мы поимем около n/2 * (2/3 + 1/3 * 2/3) = 4/9 n. Возможно, это не максимум.

[bot]

На олимпиаде предлагалось из 40 взять 16 с условием, что фальшивых ровно 3. Пока сидел надзирателем, скуки ради решил попробовать усилить. Сначала взял 16 из 36, потом сообразил (идеи в общем то те же, вся хитрость в их комбинации) как взять 17 из 39.
Общая формула у меня есть, подозреваю, что это максимум.

[Capella]

Есть такое предложение...

У Вас всего 39 монеток. Выбираем любые 3 и оставляем их в стороне, далее разбиваем оставшиися 36 на две группы по 18. Заметим, что в отложенных 3 могут быть фальшивых от 0 до 3 монет.
Теперь сравниваем две кучки по 18 (1 взвешивание), они могут быть равны или "больше меньше".
Если равны: вариант, что есть 0 фальшивых или по 1 фальшивой. Это перепроверяется, взвешивая две подгруппы по 9 монет (если они равны - фальшивых нет). Тоже делаем со второй кучкой. Отбирая по 9 монет, получаем 18 чистых монет (если есть по одной фальшивой).
Если "больше меньше": имеем вариант 1 фальшивая к 2 в другой кучке (это худший вариант). Берём группу с 1 фальшивой и получаем две по 9, та которая легче - все чистые (2 взвешивание). Берём вторую 9-монетную группу, откладываем из неё одну монетку и взвешиваем по 4 монетки - если равны, фальшивой будет отложеная, если неравенство, берём более лёгкую группу из 4 монеток, добавляем отложенную, добавляем другую чистую группу из 9 монеток и ещё 3 отложенные в начале. Это даёт всего 17 монеток.

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

Capella писал(а):

Берём вторую 9-монетную группу, откладываем из неё одну монетку и взвешиваем по 4 монетки

Откладываем 3 монетки и взвешиваем остальные 6 в 2 группах по 3. Это даст нам лишнюю монетку и общее количество будет 18.

[bot]

Верно и даже можно упростить:

Первое взвешивание по 18 монет.
В случае равновесия имеем две группы монет по 18 штук и не более 1 фальшивой в каждой группе. За одно взвешивание из каждой группы забираем 12 монет, разделив на три равные кучки и взвесив две из них. Итого 24.

В случае неравновесия берём более лёгкую. В ней не более одной фальшивой. Делим её пополам и в случае равновесия имеем 18 настоящих. В противном случае имеем 9 настоящих и 9 с одной фальшивой. Делим её на три части и одним взвешиванием забираем 6 настоящих. Но тогда отставленные 3 монеты все настоящие. Итого 9+6+3=18.

Выходит зря я игнорировал деление пополам и моё подозрение, что $[\frac{4}{9}\cdot n]$ это максимум возможного, с треском провалилось.

[maxal]

bot писал(а):

Таким образом, моё подозрение, что $[\frac{4}{9}\cdot n]$ это максимум возможного, с треском провалилось.

Окуглять тут скорее надо в большую сторону: $\left\lceil \frac{4}{9}\cdot n\right\rceil.$
А свежеописанного способа дележа асимптотически худшая прибыль: 5/12 n.

[bot]

maxal писал(а):

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

Дельное замечание.

bot писал(а):

Выходит зря я игнорировал деление пополам.

Следовало добавить: при малых n.

[heap]

maxal писал(а):

bot писал(а):

Таким образом, моё подозрение, что $[\frac{4}{9}\cdot n]$ это максимум возможного, с треском провалилось.

Окуглять тут скорее надо в большую сторону: $\left\lceil \frac{4}{9}\cdot n\right\rceil.$
А свежеописанного способа дележа асимптотически худшая прибыль: 5/12 n.

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

[maxal]

heap писал(а):

maxal писал(а):

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

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

Как? Напомню способ, который предложил bot для $n=39$:

bot писал(а):

Первое взвешивание по 18 монет.
В случае равновесия имеем две группы монет по 18 штук и не более 1 фальшивой в каждой группе. За одно взвешивание из каждой группы забираем 12 монет, разделив на три равные кучки и взвесив две из них. Итого 24.

В случае неравновесия берём более лёгкую. В ней не более одной фальшивой. Делим её пополам и в случае равновесия имеем 18 настоящих. В противном случае имеем 9 настоящих и 9 с одной фальшивой. Делим её на три части и одним взвешиванием забираем 6 настоящих. Но тогда отставленные 3 монеты все настоящие. Итого 9+6+3=18.

Остановимся на последнем случае. Здесь $9 = \frac{n-3}{4}$, $6=\frac{n-3}{6}$, ну а 3 - это константа. Тогда $9 + 6 + 3 = \frac{n-3}{4} + \frac{n-3}{6} + 3 = \frac{5n + 21}{12} \sim \frac{5}{12} n.$

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

Ага, кажется понял, что имел в виду heap.

Если $3=\frac{n}{13}$, то получается действительно 6/13 n.

То есть перефразируя метод bot'а, имеем:

Первое взвешивание по 6/13 n монет.
В случае равновесия имеем две группы монет по 6/13 n штук и не более 1 фальшивой в каждой группе. За одно взвешивание из каждой группы забираем 4/13 n монет, разделив на три равные кучки и взвесив две из них. Итого 8/13 n.

В случае неравновесия берём более лёгкую. В ней не более одной фальшивой. Делим её пополам и в случае равновесия имеем 6/13 n настоящих. В противном случае имеем 3/13 n настоящих и 3/13 n с одной фальшивой. Делим её на три части и одним взвешиванием забираем 2/13 n настоящих. Но тогда отставленные 1/13 n монеты все настоящие. Итого (3/13 + 2/13 + 1/13)n = 6/13 n.

[heap]

Интересно рассмотреть такое развитие темы:

Если p0 + p1 + p2 + p3 =1 - заданные вероятности того, что фальшивых монет соответственно 0, 1, 2 или 3 , то какова стратегия получения наибольшего матожиданя добычи.

[bot]

maxal писал(а):

покоцано

Классно! Мой алгоритм с асимтотикой 4/9 n был сложнее и до $\lfloor \ \ \rfloor $ дотягивал на пределе возможностей, особенно при индивидуальном разборе малых $n\ge 4$, где общий алгоритм не работал.
Ай да capella, возмутительница спокойствия!

[Руст]

При предположении, что на глаз можно отличить перевес на одну фальшивую монету от перевеса на два фальшивых (например по скорости отклонения весов) можно довести до 8n/15 (уже больше половины).

[bot]

А не 5/9 ?

[Руст]

У меня получилось 8n/15. Конечно при развешивании на весах и зная разницу можно ещё увеличить.

[bot]

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