2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Фальшивые монеты.
Сообщение30.01.2007, 15:13 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение30.01.2007, 15:46 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение30.01.2007, 16:04 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение30.01.2007, 21:34 
Заслуженный участник
Аватара пользователя


09/10/05
1142
Есть такое предложение...

У Вас всего 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.

 Профиль  
                  
 
 
Сообщение31.01.2007, 13:09 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Верно и даже можно упростить:

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

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

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

 Профиль  
                  
 
 
Сообщение31.01.2007, 13:24 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение31.01.2007, 14:50 
Заслуженный участник
Аватара пользователя


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

Дельное замечание.
bot писал(а):
Выходит зря я игнорировал деление пополам.

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

 Профиль  
                  
 
 
Сообщение01.02.2007, 03:17 


05/03/06
16
матмех
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.$

 Профиль  
                  
 
 
Сообщение01.02.2007, 03:44 
Модератор
Аватара пользователя


11/01/06
5660
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.

 Профиль  
                  
 
 
Сообщение01.02.2007, 04:59 


05/03/06
16
матмех
Интересно рассмотреть такое развитие темы:

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

 Профиль  
                  
 
 
Сообщение01.02.2007, 08:25 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
maxal писал(а):
покоцано

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

 Профиль  
                  
 
 
Сообщение01.02.2007, 18:33 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение01.02.2007, 19:05 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
А не 5/9 ?

 Профиль  
                  
 
 
Сообщение01.02.2007, 19:17 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение02.02.2007, 09:00 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group