Даны чашечные весы, имеющие особенность — они могут выдержать ровно 3 взвешивания (неважно в каком порядке) неравных грузов, после чего ломаются. Одинаковые веса можно уравновешивать на этих весах бесконечное количество раз. Среди N монет есть одна фальшивая, вес которой меньше настоящих.
Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний на этих весах.
не знаю почему в ответе 527 - но если говорить о задачке, в которой обсуждается ровно 7 взвешиваний - то ответ 2187 так как за 1 взвешивание мы можем найти 1 бракованную максимум из 3 монет тогда 7 взвешивание) 1 1 | 1 - всего 3 6 взвешивание) 3 3 | 3 - всего 9 5 взвешивание) 9 9 | 9 - всего 27 4 взвешивание) 27 27 | 27 - всего 81 3 взвешивание) 81 81 | 81 - всего 243 2 взвешивание) 243 243 | 243 - всего 729 1 взвешивание) 729 729 | 729 - всего 2187 итого ответ 3^7 = 2187
Кто нибудь может объяснить, каим образом надо взвешивать эти 527 монет чтобы уложится в условие ??? Я как ни крутил более 175 монет взвесить не могу.
Как я решал, допустим у нас те же самые 7 взвешиваний, но взвешивать неравный груз можно только один раз. Здесь стандартная схема взвешиваний с делением на 3 группы (2 на весах, 1 в стороне) не пойдет, так как уже при первом взвешивании можно взвесить неравные грузы, и сломать весы, сделав дальнейшее определение фальшивой монеты не возможным. Поэтому мы пойдем другим путем, мы взвесим только 2 монеты, если одна перевесила, то фальшивка найдена, если нет то у нас еще 6 взвешиваний осталось, тогда берем следующие 2 монеты и опять взвешиваем, и так можно взвешивать до тех пор, пока не останется 1 монета, которая (если до этого все монеты были равными по весу) и есть фальшивка. Таким образом для условия с допущением 1-го неравного взвешивания мы можем найти фальшивку из N=2Z+1 монет. Где Z- количество доступных взвешиваний. То есть в данном случае из 15. Если же количество неравных взвешиваний увеличить до двух, то действовать мы будем исходя из этого же принципа, но эти 7 взвешиваний делим на 2 множества, в каждом из которых допустима 1 ошибка. Тогда: N=(2Z1+1)(2Z2+1), Z1+Z2=7 Поскольку на два множества можно поделить разными способами, то делить нужно так, чтобы произведение этих множеств было максимальным. В данном случае Z1=3 и Z2=4, тогда мы сможем узнать фальшивку из 63 монет. И наконец, если можем при 7 взвешиваниях 3 раза взвесить неравные грузы: то N=(2Z1+1)(2Z2+1)(2Z3+1), Z1+Z2+Z3=7, Z1=2, Z2=2, Z3=3. N=5*5*7=175 Если кому-то что-то не понятно, или есть возражения пишите.
Вот моя версия решения, способ я называл "Модифицированные 3 кучки":-) Как правильно заметил Vano "Таким образом для условия с допущением 1-го неравного взвешивания мы можем найти фальшивку из N=2Z+1 монет." где N-кол-во монет, а Z-кол-во взвешиваний. То есть для Z=7, N=15 Для 6 - 13 для 5 - 11 для 4 - 9 для 3 - 7 для 2 - 5 для 1 - 3 Прикинем таблицу для 2-х неравных взвешиваний: Модифицированные кучки,- ваш выход!!! Теперь поделим все монеты на 3 кучки. Две из них будут равными по кол-ву монет, а в третьей все что останется.Теперь будем взвешивать первыые две кучки:если они НЕ РАВНЫ по весу то значит мы нашли кучку с фальшивкой.При этом у нас осталось 6 взвешиваний с возможностью одной попытки неравного взвешивания.Отсылка к верхней таблице. И из верхней таблицы мы знаем, что для 6 взвешиваний чтобы максимальное кол-во монет должно составлять 13. То есть надо чтобы в этой кучке было 13 монет. Тогда задача решена. Значит пусть первые две кучки будут по 13 монет.
Если же первые две кучки(по 13 монет) РАВНЫ по весу(справа ставлю значок "=") то фальшивка в третьей и тогда ее начинаем делить на три кучки.
13 13 Х1 "=" первые две кучки =, значит фальшивка в третьей кучке Х1 - монет 11 11 Х2=(Х1-11-11) "=" первыые две кучки =, значит фальшивка в третьей кучке Х2 - монет 9 9 Х3=(Х2-9-9) "=" 7 7 Х4=(Х3-7-7) "=" 5 5 Х5=(Х4-5-5) "=" 3 3 Х6=(Х5-3-3) "="
В итоге нам необходимо чтобы Х6=3, так как к моменту когда мы доберемся до Х6 у нас останется одно взвешивание, а значит в кучке может быть 3 монеты. Тогда задача решена. Отсюда находим все Х, получаем Х1=73, тогда всего монет 13+13+73=99
13 13 73 То есть для 7 взвешиваний при 2-х допущениях 11 11 51 неравного взвешивания можно максимум взвесит 99 монет 9 9 33 7 7 19 5 5 9 3 3 3
Эх.... К сожалению это еще не все, ведь щедрые условия задачи дают нам целых ТРИ возможности неравного взвешивания. Вобщем привожу сразу таблицу для 3-х неравных взвешиваний.
73 73 233 То есть для 7 взвешиваний при 3-х 51 51 131 допущения неравного взвешивания можно 33 33 65 максимум взвесить (73+73+233)=379 монет 19 19 27 9 9 9 3 3 3
Уфффф...Ответ 379 PS:Спасибо Вано за формулу N=2Z+1
Браво, Вано и joshua! Задача интересная ) Понятно, что делить надо было, скорее всего, на 3, т.к. только при таком делении в общем случае максимально уменьшается неопределенность. Но какого размера кучки брать, сразу не очевидно. И я пока не смог установить, оптимальное ли решение joshua, но похоже на то.
joshua, Привет Всем, Вашем решение я не нашёл ни одной ошибки, Это приятно,я попробую другой подход, Помощь завём формулуСОЧЕТАНИИ из комбинаторики, C^mиз n =n!/(n−m)!⋅m!, С^4 из 7(из 7 попыток 4 равновесия)== ==7!/(4!*3!)==35, 3 неровенство из 3 =2*2*2=8;комбинации, 8*35=280(запомним), С^5 из 7(из 7 попыток 5 равновесия)== ==7!/(2!*5!)==21, 2 неровенство из 2 =2*2=4, 4*21=84(запомним), С^6 из7(из 7 попыток 6 равновесия)== ==7, 2 неровенство из 1=2(или больше или меньше), 7*2=14(запомним), Берём 1 манету вставим под стакан чашки кофе(польный и горячий), Суммируем все (запомним)-ы, 280+84+14===378, В этой решении тоже нету ошибки , Если через 7 взвешив.(макс 3 неровенство), Вы не нашли фальшивку (результат 7 равновесии), Пейте кофе~~~~~ фальшивка под стаканом, Ответ 378+1===>>379, Эрудит всвесил 7 раз 263против263, (7 раз мер~~~пословица~~~~) и нашёл 527-мую фальшивую(повезло~~), Ещё раз 379 (самое лучшее количество самом худшем варианте) Спасибо
затем 
вконце 
