ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73747
Тема:    [ Взвешивания ]
Сложность: 4+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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

Решение

На рис.4, а), б), в) показано, какими тремя взвешиваниями эксперт может убедить суд, что монеты ϕ1 , ϕ2 , ... , ϕ7 – фальшивые, a H1 , H2 , ... , H7 – настоящие. Каждый раз правая чашка перевешивает, а это возможно лишь в том случае, если фальшивых монет больше на левой чашке, чем на правой (а настоящих– на правой больше, чем на левой).

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .