Эйлер атындағы олимпиада, 2008-2009 оқу жылы, аймақтық кезеңнің 1 туры

100 тиын мен екі ыдысты таразы бар. Тиындар ішінде бірнеше жалған тиындар бар (0-ден үлкен, бірақ 99-дан кіші). Барлық жалған тиындар салмағы бірдей және нағыз тиындардың салмағы да бірдей, бірақ жалған тиын нағыз тиыннаң жеңілірек. Өлшер алдында бір тиынды беріп (ол жалған немесе нағыз тиын болуы мүмкін) таразыда бір өлшеу жүргізуге болады. Осындай операциямен бір нағыз тиынды табуға болатынын дәлелде.

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

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