Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет ringill ([info]ringill)
@ 2007-04-22 02:04:00

Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Задача с монетами.
Задача есть в двух вариантах:

A. Среди 12-ти монет может быть одна фальшивая, отличающаяся от остальных по весу. Требуется найти её за три взвешивания на чашечных весах и сказать, легче она или тяжелее; либо определить её отсутствие.

B. Среди 13-ти монет есть одна фальшивая, отличающаяся от остальных по весу. Требуется найти её за три взвешивания на чашечных весах.

Самое популярное решение имеет удобную мнемонику: обозначив 12 монет буквами FAKE MIND CLOT, провести три взвешивания по такой схеме: MA DO — LIKE, ME TO — FIND, FAKE — COIN.

Таким образом можно определить, есть ли подделка среди 12-ти монет, и в какую сторону она отличается по весу. Если среди 12-ти подделки нет, то о массе 13-й уже ничего не сказать.

Указанное решение интересно тем, что взвешивания в нём однозначны и независимы; их можно проводить в любом порядке. Однако, составляя «программу» взвешиваний поэтапно, с учётом промежуточных результатов, лучшего результата всё равно не добиться.

За k взвешиваний можно решить задачу A не более чем для (3^k — 3) / 2 монет. То есть, 12 за три взвешивания. Соответственно, 13 в задаче B.

Имея лишнюю заведомо нефальшивую монету, можно снизить оценку до (3^k-1) / 2, и решить задачу B для 14 монет за те же три взвешивания.

Оба неравенства доказаны по индукции.


(Читать комментарии)

Добавить комментарий:

Как:
(комментарий будет скрыт)
Identity URL: 
имя пользователя:    
Вы должны предварительно войти в LiveJournal.com
 
E-mail для ответов: 
Вы сможете оставлять комментарии, даже если не введете e-mail.
Но вы не сможете получать уведомления об ответах на ваши комментарии!
Внимание: на указанный адрес будет выслано подтверждение.
Имя пользователя:
Пароль:
Тема:
HTML нельзя использовать в теме сообщения
Сообщение: