|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 25 Aug 2002 04:28:45
To : Mike Girkin
Subject : Re: 12 монеток
--------------------------------------------------------------------------------
Привет! "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) не зависит от того, легче, или тяжелее
фальшивая монета. Hо 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> Че-то я не понял. Hасколько я понял yсловие, неизвестно легче фальшивая
MG> монета или тяжелее.Пpи таких yсловиях иммем следyющее. Hасколько я
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 монеты.
Hо при этом монеты не делятся на кучки, а искомая монета вычисляется по
результатам всех взвешиваний.
С уважением, Андрей.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
