ММО до 2010
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Банкир узнал, что среди одинаковых на вид монет одна — фальшивая (более легкая). Он попросил эксперта определить эту монету с
помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух
раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую за 
взвешиваний?
Источники:
Подсказка 1
Давайте для начала решим более простую задачу: пусть банкир запретил использовать каждую монету более 1 раза. Из какого наибольшего числа монет можно выделить более легкую за k взвешиваний?
Подсказка 2
Что, если на одной из чаш будет более одной монеты?
Подсказка 3
Тогда выделить среди них фальшивую монету не удастся, поэтому при каждом взвешивании на чаши кладется по одной монете.
Подсказка 4
Если весы не в равновесии, то фальшивая монета очевидна. А если в равновесии, то количество подозрительных монет уменьшится на 2. Из скольких монет тогда можно выделить фальшивую при k взвешиваниях?
Подсказка 5
Из 2k+1. Вернемся к исходной задаче, обозначим ответ в ней за f(n). Пусть при первом взвешивании на чашах лежало по s монет. Что, если весы окажутся не в равновесии?
Подсказка 6
Тогда фальшивую монету надо будет искать среди s монет, причем каждую из них можно использовать лишь по одному разу, и осталось n-1 взвешивание. Что тогда следует из ранее доказанного?
Подсказка 7
s ≤ (2n - 1) + 1 = 2n - 1. Что, если весы окажутся в равновесии?
Подсказка 8
Мы получим исходную задачу для монет, не попавших на весы. Сколько будет их и взвешиваний?
Подсказка 9
Монет, не попавших на весы, (f(n) - 2s), взвешиваний (n-1). Какое неравенство тогда получим?
Подсказка 10
f(n) - 2s ≤ f(n-1). Преобразуйте неравенство, воспользовавшись доказанным ранее.
Подсказка 11
Можно убедиться, что f(1) = 3, какая оценка накладывается на f(n) исходя из суммы арифметической прогрессии?
Решим сначала более простую задачу. Пусть банкир разрешает класть на весы монеты не более 
раза. Из какого наибольшего числа монет
можно выделить более легкую за 
взвешиваний?
Если при каком-то взвешивании на чаше весов будет больше одной монеты, то из них выделить фальшивую монету не удастся (второй раз взвешивать монету нельзя!). Поэтому при каждом взвешивании на чаши кладется по одной монете.
Если весы не в равновесии, то фальшивая монета очевидна. А если в равновесии, то количество подозрительных монет уменьшится на 
Следовательно, при 
взвешиваниях можно выделить фальшивую из 
монет.
Возвращаясь к исходной задаче, обозначим ответ в ней через 
Пусть при первом взвешивании на чашах лежат по 
монет. Если
весы окажутся не в равновесии, то придется искать фальшивую монету среди 
монет, причем каждую из них можно использовать лишь по
одному разу, и осталось 
взвешивание. По доказанному 
Если весы в равновесии, то получаем исходную задачу для монет, не попавших на весы (их 
), и 
взвешивания,
значит,
Отсюда
Следовательно,
Поскольку, как легко проверить, 
имеем 
по формуле для суммы арифметической прогрессии.
С другой стороны, если имеется 
монет и каждый раз брать 
максимальным, то есть на первом шаге 
на втором —
и т. д., то эксперт сможет выделить фальшивую монету. Значит, 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
