Есть 11 одинаковых с виду монет. Среди них одна монета после каждого взвешивания с участием этой монеты её меняет вес: то он такой же, как и у остальных, то меньше. За какое минимальное число взвешиваний её можно гарантированно найти с помощью чашечных весов? Состояние монеты при первом взвешивании неизвестно. Нужно доказать минимальность(если решили за 6, то нужно доказывать, что за меньшее нельзя)
1. 4(1)=4(2) 2.4(1)>4(2) отсекли 1 и 3 кучку. Если опять равно, то монета в 3(3), это решается за 2 взвеса 3.2(2.1)=2(2.2) не дает никакой информации, но выводит монетку из состояния идентичности остальным 4.2(2.1)<2(2.2) 4.1(2.1.1)=1(2.1.2). 4.1(2.1.1)<1(2.1.2) 5.1(2.1)=1(2.2) 5.1 (2.2.1)<1 (2.2.2) 6.1(2.1)<1(2.2) Взвешиваний то по-ходу 5. Вроде я самый негативный сценарий с самой оптимальной стратегией рассмотрел.
Напишите своё решение. И я Вам покажу, что гарантированно, а это означает рассмотрение всех вариантов, за 4 раза найти монету, меняющую вес, невозможно. При наилучшем стечение обстоятельств, возможно решение в три хода. Но это будет частным решением, но не решением задачи.
Напишите своё решение.И я Вам покажу, что гарантированно, а это означает рассмотрение всех вариантов, за 4 раза найти монету, меняющую вес, невозможно. При наилучшем стечение обстоятельств, возможно решение в три хода. Но это будет частным решением, но не решением задачи.
отправил в личку, может тут кто-то захочет сам решить
По идее здесь логика простая, если изменить условия на те в которых фальшивая всегда отличается по весу от настоящих (однозначно), то среди n монет можно найти фальшивую не менее чем за ⌈ log3n ⌉, и для n=11, мы имеем 3 необходимых взвешивания. В данной здесь задаче мы имеем дело с тем же самым, только последующее(или предыдущее) взвешивание у нас поражняком ( не информативное, - все монеты не отличимы от настоящих), таким образом всегда найдётся ситуация в которой на каждое информативное взвешивание придётся не информативное, следовательно ответ на данную задачу 2•⌈ log311 ⌉ =6. И мне конечно интересен результат никника и engelan, видимо они где то ошибаются( возможно я), у никника мне не совсем ясны обозначения, и то как после третьего взвешивания где у него равенство, идёт четвёртое взвешивание где опять равенство. никник, можно чуть подробней об обозначениях? Ну и так же вопрос к вам, если Вы решили якобы за 5 взвешиваний, то если например первое у вас поражняком, то таковое будет и третье и пятое, и таким образом вы имели только два взвешивания при которых у Вас фальшивая монета была меньшего веса чем настоящая, следовательно, Вы можете за 2 взвешивания найти фальшивую среди 11 монет, в случае когда её вес отличен всегда. Очень интересно, можно подробнее? Тот же вопрос к engelan,, вы сделали 4 взвешивания среди которых 2 поражняком, и значит Вы как и никник можете за 2 взвешивания выявить фальшивку из 11, при том что её вес всегда отличен. Не вижу иной логиги, по этому действительно будет интересно выслушать Вас.
Сообщение отредактировал Фигаро - Пн, 04.01.21, 16:44
