Олимпиада имени Леонарда Эйлера2008-2009 учебный год, I тур регионального этапа

Имеются чашечные весы и 100 монет, среди которых несколько (больше 0, но меньше 99) фальшивых монет. Все фальшивые монеты весят одинаково, все настоящие тоже весят одинаково, при этом фальшивая монета легче настоящей. Можно делать взвешивание на весах, заплатив перед взвешиванием одну из монет (неважно, фальшивую или настоящую). Докажите, что можно с гарантией обнаружить настоящую монету.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Отложим одну монету. Поскольку из условия следует, что настоящих монет не меньше двух, среди оставшихся 99 монет есть хотя бы одна настоящая. Занумеруем эти монеты и взвесим первую со второй, заплатив за взвешивание отложенной монетой. Если одна из монет перевесила, то она — настоящая, и задача решена. Если веса первой и второй монет равны, сравним вторую монету с третьей, заплатив за взвешивание первой монетой. Если одна из монет перевесила, задача решена. Иначе взвесим третью монету с четвёртой, заплатив за это второй монетой и т.д. Если в какой-то момент одна из монет перевесит — задача решена. Если же все 98 взвешиваний дали равновесие, то все 99 пронумерованных монет весили одинаково, и, поскольку среди них была настоящая, все они, в том числе и две оставшихся после 98-го взвешивания — настоящие.