В комнате есть несколько попугаев, один из которых говорящий, и нескольковорон, одна из которых также умеет говорить (по голосу мы не можем различить говорящего попугая от говорящей вороны). Если свет включен, то птицы молчат, если свет выключить, то они начинают говорить. 1. Можно ли за среди 5 попугаев и 3 ворон гарантированно найти обе говорящие птицы, выключая свет не более 4 раз? 2. Можно ли за среди 9 попугаев и 7 ворон гарантированно найти обе говорящие птицы, выключая свет не более 6 раз? 3. Можно ли за среди 2^k-1 попугаев и 2^k-1 воронгарантированно найти обе говорящие птицы, выключая свет не более 2*к раз? 4. Можно ли за среди 50 попугаев и 5 ворон гарантированно найти обе говорящие птицы, выключая свет не более 8 раз?
Помогите разобраться с задачами сам ломал голову первую решить смог, на второй уже висяк но она походу должна решаться, третья это обобщенный случай первый двух задач, при к=2 получаем первую, при к=3 получаем вторую. За последнюю пока вовсе не брался. Интерес представляют все задачи даже первая, может ваши нестандартные мысли помогут мне разобраться что делать дальше.
1.Можно.Нужно взять в каждую руку по птице 2.Можно. Нужно взять в каждую руку и в зубы по птице 3.Можно. Нужно пригласить товарищей 4.Можно. Нужно спросить у птиц, кто из них говорящая
никник, задача на логику значит ты не можеш по голосу понять какая говорит можно например так: посадил первую птицу закрыл выключил свет голос есть значит говорит она и так далее или так: посадил 2 вороны тишина значит третья говорящая и вот логически за 4 раза надо вычислить обоих говорящих птиц
Сожаем двух птиц на разные плечи, выключаем свет, с какой стороны был звук та птица естественно и говорящая, таким образом проверяем сначала воронов потом попугаев или наоборот, Таким способом можно определить говорящую птицу среди n неговорящих за ⌊n/2⌋ включений света. Поэтому имеем следующие ответы на поставленные вопросы: 1. Можно, причём хватит 3 выключений, т.к. ⌊3/2⌋ +⌊5/2⌋ = 1+2=3 2. Можно. Делим попугаев на две группы по 5 и 4 попугая, любую из них проверяем в комноте на разговорчивость. Оставшихся 5 выключений достаточно чтобы установить говорящих птиц т.к. ⌊7/2⌋ +⌊5/2⌋ = ⌊7/2⌋ +⌊4/2⌋ = 3+2=5 3. Можно, т.к. ⌊(2k-1)/2⌋ +⌊(2k-1)/2⌋=(k-1)+(k-1)=2k-2 < 2k. 4. Можно. Делим попугаев на две группы по принципу ⌊k/2⌋ в одной группе, остальные в другой. Имеем 28 и 27 попугаев, проверяем любую на разговорчивость.
После первой проверки делим говорящую группу на две группы по тому же принципу и проверяем любую на разговорчивость. Повторяем действия, - делим, проверяем. После трёх включений, у нас останется 6 попугаев и 5 воронов в лучшем случае и 7 попугаев и 5 воронов в худшем, в любом из этих исходов нам будет достаточно оставшихся 5 включений.
⌊6/2⌋ +⌊5/2⌋= ⌊7/2⌋ +⌊5/2⌋=3+2=5
Сообщение отредактировал Kreativshik - Сб, 24.03.18, 21:06
Отличаем ли мы 2 болтающих голоса от 1? Если да, то: 1. 1)1в+2п=1г а)3п=г - значит ворона из прошлого действа и 1 из 3 попугаев этого. Итого 4 выключения б)3п=т - значит 1 из 2 оставшихся ворон и 1 из 2 попугаев из прошлого действа. Итого 4 выключения 1) 1в+2п=т - значит 3 оставшихся попугая (2выкл) и 2 оставшихся вороны (1выкл.). Итого 4 выключения. 1)1в+2п=2г . Итого 2 выкл.
Сообщение отредактировал никник - Сб, 24.03.18, 19:32
Птиц, в принципе, можно заменить на монеты серебряные и золотые, среди которых бултыхаются по одной фальшивой. А птичий щебет - на звуковой идентификатор фальшивой монеты. Если сигналы от двух и одной фальшивых монет отличимы, то никаких проблем с решением задач нет: 2/3, 1/2, 1/1, 1/1 ( для 1 задачи). Если же сигналы единообразны, то решения нет.
Сообщение отредактировал Ivan - Сб, 24.03.18, 20:11
1)25п+2в=1г 2) а) 25оп=1г Тогда 1 из 2 в из прошлого действа и 1 из 25п этого (13,7,4,2,1=5вык) Итого 8 вык б) 25 оп=т Тогда 25п из прошлого действа и 3 ов. 3) а)13 п2)+ 1ов=1г б) 13 п2)+1ов=т Тогда 12оп2) (6,3,2,1=4выкл) и 2ов Итого 8вык 4) а)25п2)-13п3)=1г Тогда эти 12п и 1в3) Итого 8 выкл б) 25п2)-13п3)=т Тогда 13п3) и 2ов 5. а) 7п4)+1ов=1г б) 7п4)+1ов=т Тогда 13п4)-7п5)=6 (3,2,1=3вык) и 1ов Итого 8вык 6. а) 13п3-7п5=1г Тогда эти 6п и 1в5 б) 13п3-7п5=т Тогда 7п5 и 1ов
_________________________________________________________________________________________________ 1)18п+2в=1г 2) а) 32оп=1г Тогда 1 из 2 в из прошлого действа и 1 из 32п этого (16,8,4,2,1=5вык) Итого 8 вык б) 32 оп=т Тогда 18п из прошлого действа и 3 ов. 3) а)9 п1)+ 1ов=1г б) 9 п1)+1ов=т Тогда 9оп1) (5,3,2,1=4выкл) и 2ов Итого 8вык 4) а)18п1)-9п3)=1г Тогда эти 9п и 1в3) Итого 8 выкл б) 18п1)-9п3)=т Тогда 9п3) и 2ов 5. а) 4п3)+1ов=1г б) 4п3)+1ов=т Тогда 9п3)-4п5)=5 (3,2,1=3вык) и 1ов Итого 8вык 6. а) 9п3)-5п5)=1г Тогда эти 4п и 1в5) Итого 8вык б) 9п3)-5п5)=т Тогда 5п5) ( и 1ов ________________________________________________________________________________
п-попугаи в -вороны, оп и ов - оставшиеся п и в. г-голос, т-тишина 4. 1)18п+2в=1г 2) а) 32оп=1г Тогда 1 из 2 в из прошлого действа (из 2в1)) и 1 из 32п этого (из32п2)) (16,8,4,2,1=5вык) Итого 8 вык б) 32 оп=т Тогда 18п1) (из прошлого действа) и 3 ов (оставшихся ворона). 3) а) 2п1)+ 1ов=1г б) 2 п1)+1ов=т Тогда 16 оп1) (8,4,2,1=4выкл) и 2ов Итого 8вык 4) а)18п1)-2п3)=1г Тогда эти 16п и 1в3) Итого 8 выкл б) 18п1)-2п3)=т Тогда 2п3) и 2ов Итого 6 выкл
1) 18п+2в=2г Тогда 18п(9,5,3,2,1=5вык)+2в. Итого 7 вык. 1) 18п+2в=т Тогда 32оп(16,8,4,2,1=5вык) +3ов(2,1=2вык.)Итого 8 вык. 3) 2п1)+1ов=2г Итого 4вык
Добавлено (24.03.2018, 22:48) --------------------------------------------- Лень расписывать 2 и 3, ответ:да.
Добавлено (24.03.2018, 22:53) --------------------------------------------- Мне кажется, что эта или подобная стратегия может сработать и в том случае, если мы не можем отличить 1 голос от 2, особенно в случае 4. Но это я обдумаю завтра.
Сообщение отредактировал никник - Сб, 24.03.18, 23:12
