Задача абсолютно стандартная. Разобрана в миллиарде книг. Мне кажется, даже каждый школьный учитель её рассказывает в какой-то момент своим ученикам. Тем не менее задача встречается на олимпиадах в разных классах едва ли не чаще остальных. И все равно находятся люди, которые не понимают что к чему. Даже среди взрослых.
Давайте разберем одну из таких задач. Имеется 12 монет. Одна из которых фальшивая. Она отличается от подлинных только по весу (но заранее не известно в меньшую или в большую сторону). Как на чашечных весах определить фальшивку за 3 взвешивания и понять легче она или тяжелее, чем остальные? Как вы понимаете количество монет и взвешиваний может быть разным. От этого суть не изменится.
В любом случае нам надо будет разбить монеты на кучки, чтобы взвешивать их группами. В данной задаче удобно разбить монеты на 3 кучки по 4 монеты в каждой.
В какой-то момент в одном из случаев вам может показаться, что для некоторых случаев трех взвешиваний мало и надо бы четвертое. Ну или не получится определить легче или тяжелее фальшивка. Если так, то вы ошибаетесь, надо думать снова. Трех взвешиваний достаточно в любом случае. И в любом случае получится узнать легче фальшивка или тяжелее.
Для наглядности пронумеруем монеты: {1,2, 3, 4}; {5, 6,7, 8}; {9,10, 11, 12} и приступим к решению.
Первое взвешивание
Сравниваем первые две кучки монет {1,2, 3, 4} и {5, 6,7, 8}. Если весы находятся в равновесии, значит фальшивка в третьей кучке. Переходим к пункту а) во втором взвешивании.
Если весы не в равновесии, то фальшивка в одной из этих двух кучек, а в третьей все монеты настоящие. Запоминаем, какая кучка перевесила [я для примера буду считать, что перевесила кучка {1,2,3,4}, но если нет, то решение будет симметричным] и переходим к пункту б) во втором взвешивании.
Второе и третье взвешивания
а) Фальшивка среди монет {9,10, 11, 12}. Взвешиваем {1, 2, 3} и {9,10, 11}. Если весы в равновесии, значит фальшивая монета под номером 12. третьим взвешиванием узнаем, легче она или тяжелее.
Если не равны, значит, фальшивка среди монет 9, 10, 11. При этом уже после второго взвешивания мы будем точно знать легче фальшивка или тяжелее. Третьим взвешиванием однозначно находим фальшивку: взвешиваем монеты 9 и 10. Если они равны, то фальшивка - 11. Если не равны, то фальшивка либо 9, либо 10 в зависимости от того, какая монета легче (оригинал или фальшивка), ведь эту информацию мы узнали после второго взвешивания.
б) Фальшивка в одной из первых двух кучек. Для того, чтобы понять в какой, взвесим {1, 2, 5} и {3, 4, 9} [опечатки нет, монета 9 заведомо настоящая]. Если весы в равновесии, значит, фальшивка среди 6, 7, 8, причем одна из них легче остальных [это потому что мы для ясности рассматриваем случай, когда первое взвешивание показало, что первая кучка тяжелее]. Третьим взвешиванием сравниваем монеты 6 и 7. Если они равны, то фальшивка - 8. Если нет, то фальшивка та, которая весит меньше.
Если весы после второго взвешивания оказались не в равновесии, возникает два случая
б.1) Если перевесила кучка {1, 2, 5}, то фальшивка среди монет 1 и 2. Третьим взвешиванием мы узнаем, какая из них тяжелее и это и есть фальшивка.
б.2) Если перевесила кучка {3, 4, 9}, то фальшивка среди монет 3, 4 и 5. Если фальшивка - 5, то она будет легче других. А если 3 или 4, то фальшивка тяжелее настоящих. Третьим взвешиванием сравниваем монеты 3 и 4. Если одна из них тяжелее, то это фальшивка. Если они равны, то фальшивка - 5 и она легче.
Всё. Как вам задачка? Как видите, рассмотрены все случаи и трех взвешиваний достаточно даже для того, чтобы определить не только фальшивку, но и её относительный вес.
Ещё интересно:
