Задача 65249

Темы:    [ Взвешивания ] [ Примеры и контрпримеры. Конструкции ] [ Оценка + пример ]

Сложность: 5- Классы: 9,10,11

Условие

Авторы: Берлов С.Л., Богданов И.И.

У нумизмата есть 100 одинаковых по внешнему виду монет. Он знает, что среди них 30 настоящих и 70 фальшивых монет. Кроме того, он знает, что массы всех настоящих монет одинаковы, а массы всех фальшивых – разные, причём каждая фальшивая монета тяжелее настоящей; однако точные массы монет неизвестны. Имеются двухчашечные весы без гирь, на которых можно за одно взвешивание сравнить массы двух групп, состоящих из одинакового числа монет. За какое наименьшее количество взвешиваний на этих весах нумизмат сможет гарантированно найти хотя бы одну настоящую монету?

Решение

  Пример. Сложим все 100 монет в кучу. Каждым взвешиванием нумизмат будет выбирать две монеты из кучи и сравнивать их. Если их массы равны, то обе монеты настоящие, и требуемая монета найдена. Если же нет, то более тяжёлая монета – фальшивая, и её можно выбросить из кучи.
  Через 70 таких взвешиваний, если равенства никогда не будет, то в куче останется 30 монет, причём все настоящие останутся в куче. Значит, в этом случае нумизмат даже найдёт все 30 настоящих монет. Таким образом, 70 взвешиваний достаточно.

  Оценка. Предположим, что у нумизмата есть алгоритм, позволяющий гарантированно найти настоящую монету не более, чем за 69 взвешиваний. Мы покажем, что это невозможно – даже в предположении, что массы монет таковы: масса настоящей равна 2¹⁰⁰, а масса m_i  i-й фальшивой равна  2¹⁰⁰ + 2ⁱ.
  При таком предположении результат любого взвешивания можно определить так. Пусть при некотором взвешивании на чашках по k монет, среди которых  d > 0  фальшивых, имеющих номера  i₁ < i₂ < ... < i_d.  Тогда на чашке, на которой лежит самая тяжёлая монета, суммарная масса не меньше   k·2¹⁰⁰ + 2^i_d,  а суммарная масса на другой чашке не больше  k·2¹⁰⁰ + (2¹ + ... + 2^i_d–1) = k·2¹⁰⁰ + 2^i_d – 2.  Значит, если на чашках есть хотя бы одна фальшивая монета, то перевесит чашка, на которой лежит фальшивая с наибольшим номером.
  Итак, пусть нумизмат действует по своему алгоритму. Мы будем сообщать ему результаты взвешиваний и присваивать некоторым монетам массы m_i. При этом после каждого взвешивания присвоенными окажутся веса m₇₀, m₆₉, ..., m_70–i при некотором i. Если соответствующие монеты действительно имеют такие массы (а остальные массы распределены как угодно), то результаты взвешиваний будут такими, как мы сообщили.
  При первом взвешивании выберем любую монету на чашках, присвоим ей массу m₇₀ и сообщим, что чашка с ней тяжелее. При каждом следующем взвешивании, если на весах уже присутствует монета с присвоенной массой, то мы выберем из таких масс наибольшую и сообщим, что чашка с соответствующей монетой перевесила. Если же никакой монете на весах масса ещё не присвоена, то мы опять выберем любую монету на чашках, присвоим ей наибольшую ещё не присвоенную массу и сообщим, что чашка с ней тяжелее. Нетрудно видеть, что при этом требуемые условия соблюдаются.

  Если нумизмат совершил не более 69 взвешиваний, то не более 69 масс окажутся присвоенными. В частности, m₁ присвоенной не будет. Значит, массу m₁ может иметь любая монета, которой масса ещё не присвоена, и при этом все результаты взвешиваний останутся такими, как мы сообщили. Поэтому нумизмат не сможет указать на заведомо настоящую монету.

Ответ

За 70 взвешиваний.

Замечания

Ответ не изменится, если убрать условие равенства количеств монет на чашках.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Вариант	2014/2015
этап
Вариант	5
класс
Класс	10
задача
Номер	10.8