Закл (финал) 9 класс

Докажем индукцией по

База. Для удобства занумеруем монеты числами от до и запишем их в троичной записи (таким образом, каждой монете сопоставлена пара цифр от до ). Первое взвешивание делаем первыми весами в соответствии с первой цифрой номера: на левую чашу кладем монеты, у номера которых первая цифра на правую — у которых она Второе взвешивание делаем аналогично вторыми весами в соответствии со второй цифрой номера. Знак указывает на то, что фальшивая монета среди чисел с на первом/втором месте, — что она среди чисел с на первом/втором месте, — что среди чисел с на первом/втором месте. После проведения взвешиваний можно перенумеровать числа так, чтобы результат первого взвешивания указывал на число с на первом месте, а второго — с на втором. Тогда монеты без нулей в номере точно не фальшивые (иначе соврали и первые, и вторые весы).

Теперь разобьем монеты на три группы следующим образом: в одну поместим в другую и в третью — и дополним все группы до трех монет точно не фальшивыми и взвесим третьими весами. Если весы сказали, что фальшивая в группе с то это и есть (иначе двое весов соврали), и четвертое взвешивание не понадобилось. Если взвешивание сказало, что фальшивая в группе с и то третьи весы противоречат вторым. Поэтому хотя бы одни из них соврали, а значит, первые точно исправны. Но тогда у фальшивой первая цифра действительно таким образом, остались лишь три кандидата на фальшивую монету и одни точно исправные весы, которыми мы находим фальшивую монету за ход. Аналогично поступаем, если третье взвешивание сказало, что фальшивая монета в группе с и

Переход. Разобьём монет на одну куч по в каждой. Будем считать каждую кучу за одну монету (куча с фальшивой монетой легче). Тогда по рассуждениям из базы мы либо находим за взвешивания кучу с фальшивой монетой и далее работаем с ней, пользуясь предположением, либо за взвешивания мы находим рабочие весы и три кучи, среди которых есть куча с фальшивой монетой. Во втором случае, нам хватит взвешиваний, если постоянно делить кучу на три кучи с одинаковым числом монет.