Бракованные таблетки
В аптеку поступило сильнодействующее лекарство - 8 упаковок по 150 таблеток. Следом пришло сообщение, что в этой партии есть несколько упаковок с бракованными таблетками - их вес на 1 мг больше нормальной дозы. Как за одно взвешивание выявить все упаковки с бракованными таблетками? Упаковки можно вскрывать.
Ответ: Следует учинить непересекающиеся подмножества таблеток от разных упаковок: взять из первой упаковки одну таблетку, из второй - две, из третьей - четыре, из четвёртой - восемь, из пятой - 16, из шестой - 32, из седьмой - 64, из восьмой - 128. Всё это взвесить. Вычесть из полученного веса идеальный вес (идеальный вес каждой таблетки известен из документации, но можно обойтись и без него - подумайте как). Полученный излишек веса (он уже нормализован за счёт единичного излишка веса каждой таблетки) перевести в двоичный вид (ведь мы сформировали подмножества по двоичному закону). В этом числе номера разрядов, равные единице, и будут показывать номера бракованных упаковок.
Рейтинг: +48
Комментарии:
Не осилил! Ответ крут!Если честно, даже ответ не осилил 
)
надо бы математику показать...Необходимо уточнение о том, что весы могут показывать в мг. Эта задача подит на "10 мешков и 10 монет"Андрей, 2009-09-07
Однозначно одна из лучших задач. Я думал над ней три с половиной или три часа (при этом расчитывал только в уме) и я вам скажу, когда додумался, я был просто в шоке. Я думаю, что условия достаточно чтобы ее решить, и сложность как раз в том, чтобы понять условие так, чтобы можно было решить задачу.А мне такую задачку задали на собеседовании)))balderloci, 2010-10-31
Зачем так сложно ? )) Можно просто из 1 упаковки 1 таб , из второй 2 таб и т.д. В общей сложности 36 таб и взвешиваем .Если вес от идеального отличается на 1 мг ,значит фальшивые таблетки в первой упаковке , если разница в 2 мг значит . во второй и т.д.
В принципе , можно из семи упаковок взять всего 28 таб . И если вес одинаков с номинальным , значит фальшивая упаковка № 8 .. Правда есть одно НО : в случае с 36 таб , нам даже не обязательно знать , тяжелее или легче фальшивые упаковки ,это легко выясняется . В принципе ,в условии даже не обязательно знать про вес - легче или тяжелее , важно только знать , что отличие в 1 мг .Poligrafych, 2010-11-03
И кто мине скажет ЧТО потом аптека будет делать с открытами упаковками СИЛЬНОДЕЙСТВУЮЩЕГО лекарства? А я скажу. Загонит пацикам еще и по хорошей цене, а товарисчу ревизору скажуть, что жуть, вся партия бракованная, но вставля-я-я-ет! ЖестьАнтон, 2011-01-25
Прикол не в том, чтоб найти где бракованная коробка. Неизвестно сколько их!!! Может вообще не быть, а может 7 из 8. Потому то и такой сложный ответ. Но поистине, невероятная задачи и решение. А что такое непересекающееся подмножество?Задачка из цикла "считай бит". Чисто для программистов.Игорь, 2011-11-16
Хорошая задача. Если бы бракованной была бы только одна упаковка - решалось бы элементарно, а так пришлось подумать.Андрей, 2011-12-16
Ответ проще понять, если не переводить полученный излишек веса в двоичный вид, а прикинуть, сумме каких чисел из группы (1, 2, 4, 8, 16, 32, 64, 128) он равен. Например, если излишек равен 21, то это сумма 1, 4 и 16. Значит бракованные 1-я, 3-я и 5-я упаковки.
