Задача 1 ОЧ-2016 (8 класс): Взвешенное решение
У школьника Васи есть 9 внешне одинаковых монет, одна из которых фальшивая (она весит чуть меньше остальных). Мальчик очень любит конфеты и тратит все деньги только на них, его счастье прямо пропорционально числу купленных конфет. Однако он знает, что если он попробует расплатиться фальшивой монетой, то в его городе больше никогда никто не продаст ему конфеты, поэтому ему очень хочется узнать, какая из монет фальшивая.
а) Помочь ему в этом может индивидуальный предприниматель Жора, у которого имеются два экземпляра внешне неразличимых чашечных весов, из которых одни неисправны (при любом взвешивании, в котором на чашах поровну монет, показывают равенство). Какие из весов неисправны, Жора не рассказывает. Вася может сделать сколько захочет взвешиваний, однако, каждое взвешивание у Жоры стоит одну настоящую монету (плата взимается после окончания всех взвешиваний, Вася не может взвешивать «в кредит»). Какое наибольшее количество конфет сможет гарантированно купить Вася, если цена одного килограмма конфет – одна монета?
б) Недалеко от Жоры работает его конкурент, Константин, у которого есть одни исправно работающие чашечные весы. Какую наибольшую цену одного взвешивания может поставить Константин, чтобы Васе было выгоднее идти к нему, если при прочих равных Вася предпочтет иметь дело с честным Константином, а монеты можно разменивать на меньшие по ценности. (При выборе Вася руководствуется тем количеством взвешиваний, которое позволит гарантированно выявить фальшивку, потому что он пессимист).
а) Пронумеруем монеты от 1 до 9. Для первого взвешивания положим на одну чашу монеты под номерами 1,2,3,4 и на другую – с номерами 5,6,7,8. Если монеты на одной чаше оказались легче другой, то данные весы исправны, фальшивая монета в этой четверке, и за два взвешивания на этих весах мы найдем фальшивку.
Если чаши при первом взвешивании остались в равновесии, то вторым взвешиванием кладем на чаши вторых весов монеты с номерами 1,2,3 и 5,6,7. Если в этот раз чаши оказались на разном уровне, то мы нашли хорошие весы и три монеты, среди которых фальшивая, за последнее взвешивание на них найдем фальшивую монету.
Если и во второй раз чаши находятся в равновесии, то возможна одна из двух ситуаций: первые весы неисправны, а фальшивая монета – одна из 4,8,9 ; вторые весы неисправны и 9 – фальшивка. Таким образом, если третьим взвешиванием положить на вторые весы монеты 4 и 9, то, в зависимости от исхода, достоверно определим фальшивую монету: если чаши в равновесии – фальшивая монета с номером 9, если одна перевешивает, то та, чаша с которой легче.
Докажем, что за два взвешивания точно определить нельзя, будем действовать от противного и рассмотрим варианты первого взвешивания:
- На чашах – по 4 монеты, на весах – неравновесие, тогда за оставшееся одно взвешивание не получится выявить фальшивую монету из 4 подозрительных.
- Если на чашах было меньше, чем по 4 монеты, но равновесие при первом взвешивании, то отложено больше одной монеты, и если проведем второе взвешивание на вторых весах (это необходимое условие для проверки весов), а они окажутся неисправными, то мы не сможем понять, какая из отложенных монет фальшивая.
Таким образом, Вася не сможет сделать меньше трех взвешиваний, то есть отдаст Жоре не меньше трех монет. Фальшивую монету Жора не возьмет, а значит Вася сможет купить не больше 5 кг конфет.
Ответ: 5 кг.
Примечание: допускается использование других путей решения или оформление с помощью графа последовательных событий.
б) Из 9 монет на исправных весах определить фальшивую монету можно за 2 взвешивания: кладем на обе чаши по три монеты; если одна из чаш перевешивает, то фальшивая монета на чаше, оказавшейся легче; если чаши оказались в равновесии, то фальшивая – одна из трех оставшихся монет. Таким образом мы выбрали три монеты, среди которых есть фальшивая. Вторым взвешиванием кладем по одной монете на чаши из выбранной тройки, определяем, какая из них фальшивая аналогично алгоритму первого взвешивания.
За одно взвешивание определить фальшивую монету нельзя, так как, сколько бы монет мы ни положили на чаши в первом взвешивании, после него может остаться несколько монет, среди которых будет фальшивка (можно разобрать каждый случай: по 1, по 2, по 3, по 4 на каждой чаше в первое взвешивание). Жоре Вася отдаст 3 монеты, значит, чтобы мальчику выгодно было идти к Константину, цена одного взвешивания не должна превышать 1,5 монеты.
Ответ: 1,5 монеты.