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

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

Условие

В наборе из 17 внешне одинаковых монет две фальшивых, отличающихся от остальных по весу. Известно, что суммарный вес двух фальшивых монет вдвое больше веса настоящей. Всегда ли можно ли определить пару фальшивых монет, совершив пять взвешиваний на чашечных весах без гирь? (Определять, какая из фальшивых монет тяжелее, не требуется.)


Решение

  Пусть разность весов фальшивых монет меньше чем вес настоящей. Тогда во взвешиваниях имеет смысл сравнивать лишь равные количества монет.
  Предположим, что требуемый алгоритм существует. Выпишем для каждой последовательности результатов взвешиваний, которая может получиться в нашем алгоритме, единственную пару фальшивых монет, при которой эта последовательность получается. Заметим, что если в последовательности есть хотя бы одно взвешивание, при котором нет равновесия, то мы можем определить, какая из фальшивых монет тяжелее настоящей. Действительно, если во взвешивании участвует одна фальшивая монета, то это определяется очевидным образом. Если же участвуют обе, то они находятся на разных чашах весов (иначе весы в равновесии), и монета на перевесившей чаше тяжелее.
  В таком случае, если в нашей паре монет поменять две фальшивые местами, то получится другая последовательность взвешиваний. Поэтому всем парам, кроме, быть может, одной (при которой весы все время в равновесии) соответствует по две последовательности.
  Всего может быть  17·16 : 2 = 136  пар, поэтому число последовательностей не меньше  2·136 – 1 = 271,  но их не больше  35 = 243 < 271.   Противоречие.


Ответ

Не всегда.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2003
Этап
Вариант 4
Класс
Класс 10
задача
Номер 03.4.10.8
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2003
Этап
Вариант 4
Класс
Класс 11
задача
Номер 03.4.11.8

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

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