Пятница - задача - снова монеты

← →
Sha © (2005-07-01 10:44) [0]

Купец сдает в банк выручку - мешок, в котором находится m=512 золотых монет.
Известно, что в нем не более f=16 фальщивых монет, каждая из которых на 10%
легче настоящей. У банкира есть весы (со стрелкой), при помощи которых он
может взвешивать не более n=64 монет одновременно. Задача банкира - сделав
минимальное количество взвешиваний, принять у купца только настоящие монеты,
а фальшивые вернуть купцу.

Сразу говорю, решения не знаю, нет даже стоящих идей :)

← →
KilkennyCat © (2005-07-01 11:00) [1]

Делить пополам.

← →
Ega23 © (2005-07-01 11:02) [2]

Сначала взвесить 17 раз. Тогда гарантированный эталон из 16 монет будет.

← →
Asteroid © (2005-07-01 11:03) [3]

А у банкира есть достаточное количество настоящих монет? :)

← →
KilkennyCat © (2005-07-01 11:07) [4]

Я думаю, если взвесить 4 кучки по 64 монеты, можно будет сказать сколько фальшивых в каждой кучке.

← →
Sha © (2005-07-01 11:09) [5]

> Делить пополам.
Угу, а дальше как?

> Сначала взвесить 17 раз. Тогда гарантированный эталон из 16 монет будет.
Забыл сказать. Вес настоящей монеты банкиру известен :)

> А у банкира есть достаточное количество настоящих монет? :)
Ему достаточно одной. Весы-то со стрелками (не рычажные).

← →
Sha © (2005-07-01 11:13) [6]

> Я думаю, если взвесить 4 кучки по 64 монеты, можно будет сказать сколько фальшивых в каждой кучке.
Проблема в том, как их выделить.

← →
KilkennyCat © (2005-07-01 11:16) [7]

> Вес настоящей монеты банкиру известен :)

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

← →
Sha © (2005-07-01 11:20) [8]

> KilkennyCat © (01.07.05 11:16) [7]
Можно показать, что это решение иногда не оптимально.

← →
KilkennyCat © (2005-07-01 11:56) [9]

> Sha © (01.07.05 11:20) [8]

Да, в худшем варианте оно приблизится к помонетному перебору.

← →
Sandman29 (2005-07-01 12:00) [10]

Sha © (01.07.05 11:20) [8]

Начинать взвешивать с 31 (Так как 512/16=32 и ожидается найти одну фальшивую в каждых 32). Если нашли, что среди этих 31 есть фальшивые, то дальше взвешиваем по 15 (затем по 7, по 3 и наконец, по одной). Оставшиеся 512-31*16=16 монет взвешиваем так: 8(4(2(1),1),3(1)) и 7 (3(1)).
Получается в худжем случае
16*(2+4+8+16)+(1+(1+1+1+1)+(1+2))+(1+2+4)=435 взвешиваний.
В лучшем
17 (если фальшивых монет 16 и ни одна из них не попала в пачки по 31 монете).

← →
Sandman29 (2005-07-01 12:06) [11]

Интересно, что из 31 монеты можно искать фальшивые разными способами:
1) 2*15,2*7,2*3,2*1
2) 3*10,3*3,2*1
3) 3*10, 2*5(4), 2, 1
но все равно получается 30 взвешиваний в каждом варианте.

← →
Sha © (2005-07-01 12:41) [12]

> Sandman29
Количество взвешиваний в худшем случае удручает, тем более, что задача имеет практическое значение :(
Вчера пробовал выиграть что-нибудь не только на изменении размера кучек, но и на перекладывании монет между кучками, но окончательно запутался.

1)
Делим 512 монеты на 32 кучки по 16 монет
Взвешиваем
Как минимум 256 монет мы определим как настоящие
2)
Делим 256 монеты на 32 кучки по 8 монет
Взвешиваем
Как минимум 128 монет мы определим как настоящие
3)
Делим 128 монеты на 32 кучки по 4 монеты
Взвешиваем
Как минимум 64 монеты мы определим как настоящие
4)
Делим 64 монеты на 32 кучки по 2 монеты
Взвешиваем
Как минимум 32 монеты мы определим как настоящие
5)
Взвешиваем 32 монеты по одной

итого 32*5 - 160 взвешиваний в худшем случае

> icWasya © (01.07.05 12:46) [13]
Отличный результат.
Хотя и нет полной уверенности, что это минимум, но уже почти приемлемо.
Если сделать динамическую реализацию в зависимости от результата предыдущего взвешивания, может и сойдет.

← →
Sandman29 (2005-07-01 13:42) [15]

Надо обычное деление пополам.
За 96 взвешиваний максимум получается.
16 раз по 32 + 16 раз по 16 + 16 раз по 8 + 16 раз по 4 + 16 раз по 2 + 16 раз по 1.
При последующих делениях надо запоминать предыдущий результат и делить кучку верхнего уровня.
То есть если 32 штуки весят 30, а 16 штук ИЗ НИХ весят 16, значит оставшиеся 16 весят 30-16=14.

> Sandman29 (01.07.05 13:42) [15]
> Надо обычное деление пополам.
> За 96 взвешиваний максимум получается

Класс. Мой личный рекорд = 153 :(

← →
Sandman29 (2005-07-01 14:17) [17]

Пятница - задача - снова монеты Найти похожие ветки