Задача 73747

Тема:    [ Взвешивания ]

Сложность: 4+ Классы: 7,8,9

Условие

Автор: Фрейвальд Р.В.

На суде в качестве вещественного доказательства предъявлено 14 монет. Эксперт обнаружил, что семь из них — фальшивые, остальные — настоящие, причём узнал, какие именно фальшивые, а какие — настоящие. Суд же знает только, что фальшивые монеты весят одинаково, настоящие монеты весят одинаково, а фальшивые легче настоящих. Эксперт хочет тремя взвешиваниями на чашечных весах без гирь доказать суду, что все обнаруженные им фальшивые монеты действительно фальшивые, а остальные — настоящие. Сможет ли он это сделать?

Решение

На рис.4, а), б), в) показано, какими тремя взвешиваниями эксперт может убедить суд, что монеты ϕ₁ , ϕ₂ , ... , ϕ₇ – фальшивые, a H₁ , H₂ , ... , H₇ – настоящие. Каждый раз правая чашка перевешивает, а это возможно лишь в том случае, если фальшивых монет больше на левой чашке, чем на правой (а настоящих– на правой больше, чем на левой).

Этот способ легко обобщить, и тогда тот факт, что данные n монет– фальшивые, а другие n – настоящие, удается доказать, произведя [log _{_}a n]+1 взвешиваний. Несмотря на то, что такая система взвешиваний очень экономна (при n=1000 достаточно 10 взвешиваний), мы не можем доказать, что она оптимальна. Интересно было бы доказать, что минимальное число взвешиваний вес же растет неограниченно при n (или опровергнуть это).

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1973
выпуск
Номер	7
Задача
Номер	М212