Ошибка.
Попробуйте повторить позже
Даны трое чашечных весов без гирь, из которых ровно одни сломаны: их показания произвольны, и мы не знаем, какие весы неисправны. Докажите, что из монет можно определить одну фальшивую (более легкую) не более, чем за взвешивание.
Докажем индукцией по
База. Для удобства занумеруем монеты числами от до и запишем их в троичной записи (таким образом, каждой монете сопоставлена пара цифр от до ). Первое взвешивание делаем первыми весами в соответствии с первой цифрой номера: на левую чашу кладем монеты, у номера которых первая цифра на правую — у которых она Второе взвешивание делаем аналогично вторыми весами в соответствии со второй цифрой номера. Знак указывает на то, что фальшивая монета среди чисел с на первом/втором месте, — что она среди чисел с на первом/втором месте, — что среди чисел с на первом/втором месте. После проведения взвешиваний можно перенумеровать числа так, чтобы результат первого взвешивания указывал на число с на первом месте, а второго — с на втором. Тогда монеты без нулей в номере точно не фальшивые (иначе соврали и первые, и вторые весы).
Теперь разобьем монеты на три группы следующим образом: в одну поместим в другую и в третью — и дополним все группы до трех монет точно не фальшивыми и взвесим третьими весами. Если весы сказали, что фальшивая в группе с то это и есть (иначе двое весов соврали), и четвертое взвешивание не понадобилось. Если взвешивание сказало, что фальшивая в группе с и то третьи весы противоречат вторым. Поэтому хотя бы одни из них соврали, а значит, первые точно исправны. Но тогда у фальшивой первая цифра действительно таким образом, остались лишь три кандидата на фальшивую монету и одни точно исправные весы, которыми мы находим фальшивую монету за ход. Аналогично поступаем, если третье взвешивание сказало, что фальшивая монета в группе с и
Переход. Разобьём монет на одну куч по в каждой. Будем считать каждую кучу за одну монету (куча с фальшивой монетой легче). Тогда по рассуждениям из базы мы либо находим за взвешивания кучу с фальшивой монетой и далее работаем с ней, пользуясь предположением, либо за взвешивания мы находим рабочие весы и три кучи, среди которых есть куча с фальшивой монетой. Во втором случае, нам хватит взвешиваний, если постоянно делить кучу на три кучи с одинаковым числом монет.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!