12 монеток

From

Evgenij Masherov (2:5020/175.2)

To

Evgeniy Jirnov

Date

2002-08-24T12:17:44Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Thu Aug 22 2002 22:58, Evgeniy Jirnov wrote to All:

 
 EJ> Есть сабж, среди них одна фальшивая(отличается от настоящих весом). С
 EJ> помощью трех взвешиваний найти фальшивую монету.

 EJ> Мне кажется это нерешимо. А вам, уважаемые подписчики?

0. Интересно, почему эта задача периодически подбрасывается именно в эту эху?
1. Кажется, понял! Это пример на использование теории информации в разработке
алгоритма!
2. Из нее следует, что:
а. задача разрешима
б. на каждом шаге решения следует выбирать сравнения так, чтобы альтернативы
были бы в наибольшей степени равновероятны.
3. И интересная "ловушка симметричности".

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)