Имеется 5 мешков с монетами. В некоторых мешках монеты фальшивые, они весят 9 граммов. В остальных мешках монеты настоящие, они весят 10 граммов. В каждом мешке монеты только одного веса (или все фальшивые или все настоящие). Имеются электронные весы, которые показывают точный вес (в граммах). На чашу весов можно класть любое количество монет из любых мешков. Требуется за 1 (одно!) взвешивание определить, в каких мешках фальшивые, а в каких — настоящие монеты. Какое минимальное количество монет нужно положить для этого на весы?
Ответы
Відповідь:
Нужно положить 31 монету.
Покрокове пояснення:
Если бы был только один мешок с фальшивыми монетами, то нужно было взять 1 монету из 1 мешка, 2 монеты из 2 мешка, 3 монеты из 3 мешка, 4 монеты из 4 мешка и 5 монет из 5 мешка. Тогда на весах лежали бы 1 + 2 + 3 + 4 + 5 = 15 монет. Если все монеты настоящие, то весы покажут 10 × 15 = 150 грамм. Если весы покажут вес отличный от 150 грамм, то разница в весе между 150 граммами и показаниями весов и есть номер мешка. Например фальшивые монеты находятся в мешке номер 2, то показания весов: 1 × 10 + 2 × 9 + 3 × 10 + 4 × 10 + 5 × 10 = 148 грамм. Разница 150 - 148 = 2 грамма - фальшивые монеты находятся в мешке номер 2.
В нашем случае фальшивые монеты могут быть в нескольких мешках. В таком случае если мы имеем разницу в 3 грамма, то существует 2 варианта: либо искомый мешок 3, либо это мешки 1 и 2. Если мы имеем разницу в 4 грамма, то существует 2 варианта: либо искомый мешок 4, либо это мешки 1 и 3. Если мы имеем разницу в 5 грамм, то существует 3 варианта: либо искомый мешок 5, либо это мешки 1 и 4 или мешки 2 и 3.
Нам необходим метод при котором количество монет взятое из любого мешка не может быть суммой монет взятых из любых других мешков в любой комбинации. Вариант взять 1 монету из 1 мешка, 3 монеты из 2 мешка, 5 монет из 3 мешка, 7 монет из 4 мешка и 9 монет из 5 мешка; так же не дает однозначного ответа. Возможны варианты, когда монеты взятые из разных мешков дают одинаковое их количество в сумме, например: 1 + 7 = 8 монет и 3 + 5 = 8 монет; 1 + 3 + 5 = 9 монет и 9 монет из 5 мешка.
Вариант, исключающий неоднозначность существует. Нужно взять 1 монету из 1 мешка, 2 монеты из 2 мешка, 4 монеты из 3 мешка, 8 монет из 4 мешка и 16 монет из 5 мешка. Тогда на весах будут лежать 1 + 2 + 4 + 8 + 16 = 31 монета. Если все монеты настоящие, то весы покажут 10 × 31 = 310 грамм. Если весы покажут вес отличный от 310 грамм, то по разнице в весе между 310 граммами и показаниями весов и можно определить номер мешка.
Например:
1) фальшивые монеты находятся в мешке номер 2, то показания весов: 1 × 10 + 2 × 9 + 4 × 10 + 8 × 10 + 16 × 10 = 308 грамм. Разница 310 - 308 = 2 грамма - мы взяли 2 монеты из 2 мешка - фальшивые монеты находятся в нем.
2) фальшивые монеты находятся в мешках номер 1 и 4, то показания весов: 1 × 9 + 2 × 10 + 4 × 10 + 8 × 9 + 16 × 10 = 301 грамм. Разница 310 - 301 = 9 грамм. 9 монет в сумме можно получить только в одной комбинации 1 + 8 = 9 - фальшивые монеты находятся в мешках номер 1 и 4.