Re: 12 монеток

From

Andrew Ezhguroff ()

To

Mike Girkin

Date

2002-08-25T04:28:45Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Mike Girkin" <Mike.Girkin@p22.f177.n5055.z2.fidonet.org>
сообщил(а):

 AE>> Пpекpасно pешаемо.
 MG> ИМХО таки нет.

Ошибаешься.

 AE>> Пpедставь pезyльтат взвешивания как значения pазpядов числа в
 AE>> тpоично-симметpичной системе счисления. Модyль этого числа
 AE>> (пpинимающий значения от 0 до 13) не зависит от того, легче
 AE>> фальшивая монета, или тяжелее.
 MG> А тепеpь поподpобнее.

Пожалуйста.

Обозначим результат взвешивания в виде числа N: если весы отклонились влево,
то N равно -1, если вправо, что +1, если равновесие, то равно нулю.

По результатам трех взвешиваний получаем числа N1, N2, N3.

Представим итог трех взвешиваний в виде числа
Q=(3^0)*N1+(3^1)*N2+(3^2)*N3=N1+3*N2+9*N3 (это и есть троично-симметричная
система счисления). Очевидно, что Q может принимать любое из 27 значений
от -13 до 13.

Предположим, что по результатам трех взвешиваний мы получили число Q1.
Теперь меняем фальшивую монету на фальшивую же монету другого веса (если она
была "легкой", то меняем на "тяжелую" и наоборот) и повторяем взвешивания.
Получаем число Q2. Очевидно, что Q1=-Q2, т.е. Q1 и Q2 отличаются ТОЛЬКО
знаком. Следовательно, abs(Q) не зависит от того, легче, или тяжелее
фальшивая монета. Но abs(Q) может принимать 14 значений - от 0 до 13.

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

A. весы не отклонялись (фальшивая монета на весы не клалась) - 1 вариант.

B. весы отклонились один раз (фальшивая монета клалась на весы один раз) - 3
варианта.

C. весы отклонились два раза в одну сторону (фальшивая монета клалась на
весы два раза в одну и ту же чашку) - 3 варианта.

D. весы отклонились два раза в разные стороны (фальшивая монета клалась на
весы два раза, но в разные чашки) - 3 варианта.

E. весы отклонились два раза в одну сторону и один раз в другую (фальшивая
монета клалась на весы три раза: два раза в одну чашку и один раз в
другую) - 3 варианта.

F. весы отклонились три раза в одну сторону (фальшивая монета клалась три
раза в одну чашку) - 1 вариант.

Итого имеем те же самые 14 вариантов.

Попытаемся распределить монеты по чашкам весов так, чтобы получить
вышеприведенные варианты. И получается, что вариант с 14 монетами не
проходит - в этом случае на одной чашке весов будет 4 монеты, а в другой
пять. Так что вариант F отбрасываем.

Пронумеруем монеты от 00 до 12 и разместим их по чашкам весов так, чтобы
abs(Q) сразу давало номер искомой монеты:

Взвешивание N1: (01 05 07 08) | (02 04 10 11)
Взвешивание N2: (02 03 05 11) | (04 06 07 12)
Взвешивание N3: (06 07 09 11) | (05 08 10 12)

При этом монета 00 ни разу не взвешивается и сказать ее относительный вес не
представляется возможным.

 AE>> Для 12 монет можно сказать, легче фальшивая монета, или тяжелее.
 MG> Это можно сделать и 2-мя взвешиваниями.

Имеется в виду, что неизвестно, какая именно монета фальшивая.

 AE>> Если относительный вес не важен, то можно найти однy из 13
 AE>> (тpинадцатая монета не взвешивается).
 MG> Че-то я не понял. Насколько я понял yсловие, неизвестно легче фальшивая
 MG> монета или тяжелее.Пpи таких yсловиях иммем следyющее. Насколько я
 MG> помню аналогичная задача для 2-х взвешиваний pазpешима пpи максимyм 4-х
 MG> монетах. Откyда можно сделать вывод, что для нашей задачи, yже после
 MG> пеpвого взвешивания необходимо опpеделить "кyчкy" из 4-ех монет, в
 MG> котоpой есть фальшивая.

Ты делаешь неверный вывод из ошибочных предпосылок. Если точно известно, что
фальшивая монета легче (или тяжелее), то за M взвешиваний можно найти ее
среди 3^M монет. Если же вес фальшивой монеты неизвестен, то ее можно
отыскать среди (3^M)/2 монет. Соответственно, для двух взвешиваний имеем
9/2 - те самые 4 монеты.

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

С уважением, Андрей.


-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)