* Задругата на логиците
Публикувано на 24 юни 2009 в раздел Математика.
Малко от вас знаят, но съществува световна тайна организация на логиците. В нея се правят тайни съвещания и се обсъждат нови, изключително сложни логически въпроси. Членството обаче е изключително трудно - нужно е да се премине през редица логически изпитания, а по време на съвещанията често се изхвърлят членове, поради слаба логическа подготовка.
Веднъж гуруто на логиците събрал всички в голямата тайна зала. Казал им, че ще се проведе нова, логическа загадка, от която ще се разбере кои членове са добри логици и кои не...
Всички се наредили в един голям кръг така, че всеки виждал другите около себе си. Гуруто минавал пред всеки член и залепвал по една лепенка цветно тиксо на челото му. Всички можели да виждат цвета на лепенката тиксо залепена на челото на човека, но самия човек не можел да види своята лепенка. Имало много и най-различни цветове лепенки.
След като налепил участниците, гуруто им казал, че на регулярни интервали отвън ще бъде бита камбана. В момента, в който някой участник знае със сигурност цвета на своето тиксо, той трябва да напусне с биенето на следващата камбана. Ако някой излезе и обърка цвета на тиксото си, то ще бъде изключен от организацията. Ако пък участниците не излязат - проблемът си е техен, защото никой няма да им даде храна и вода. Освен това ако някой проговори - ще бъде заключен в тъмната тайна наказателна стаичка до края на дните си.
Въпреки огромното негодувание, гуруто все пак уверил участниците, че задачата има решение и всеки един може с достатъчно разумна логика да излезе от стаята и да остане член на организацията.
Всички в крайна сметка се справили със задачата с изключение на тайния агент Иванчо, който се оказа, че бил не какво да е, а адвокат под прикритие - липсвала му каквато и да е логика в разсъжденията! Как са се справили останалите?
Кво праим сега? Седим в стаята и мълчим, а?
Хайде някой да измисли нещо? :)
Значи аз ще дам няколко предложения, и ще си изложа реда на мисли :)
Първо, приемам че все пак цветовете тиксо са краен брой, и са известни на участниците в задачата. Тоест всеки участник знае всички възможни цветове, които може да му лепнат.
Иначе задачата ми се струва нерешима.
За улеснение приемам, че е имало 10 цвя
Светльо Антонов - Да кажем, че вървиш в правилна посока, но все още си далече от решението. Не - не се прави специална организация и пренареждане. Нямат право да си подсказват - иначе е ясно и тривиално. Можеш да разбереш цвета на челото само от информацията дадена в задачата.
Опс... грешно натиснат ентер :)
За удобство приемаме, че е имало 10 цвята тиксо, и ги означаваме с цифрите от 0 до 9.
Така, всеки има на челото си цифра в границите 0 - 9, като вижда цифрите на останалите, но не вижда своята.
В случай, че цифрите не се повтарят, решението е очевидно - цифрата която не виждаме е на нашето чело.
Значи вероятно има повтарящи се цифри... няма как да знаем дали цифрата на нашето чело не се повтаря някъде.
Тук си представям, че може да са направили някаква организация, така че да се сортират по ред на номерата например. Може да си измисля някакъв вариант, но ми се иска да знам дали това е позволено от условието?
Тоест това, че трябва да мълчат означава ли че не могат да се разместват, и да си дават знаци тип "премести се наляво", "премести се надясно"?
Ако приемем че всички от възможните N цвята са използвани тогава:
Ако има едиствен човек с тиксо от даден цвят той виждайки, че всички други цветове ги има освен неговия, лесно ще определи какъв е неговия цвят. На първото биене на камбаната всички такива хора ще излязат. Следователно ще останат всички които са дублирани и адвокатът.
На втора стъпка всички хора от кръга, един по един се оглеждат за най-дългата поредица от хора с еднакъв цвят и се нареждат на една от границите й. Това се повтаря докато редицата от хора с еднакъв цвят се уголемява, след всяко успешно удължаване трябва всички да се наредят отново по веднъж.
Когато всички от дадения цвят на редицата вече са в нея, всичките й членове ще знаят, че са част от нея защото след тяхното нареждане са видели, че границата където другите се редят се е преместила, тогава цялата редица може да излезе знаейки цвета си. След това всичко се повтаря, докато остане само адвокатът.
Mertol - хареса ми тактиката за дълга редица от еднакъв цвят. Много добра и функционална идея. За съжаление решението ти се основава на нещо, което не е казано в условието - колко точно са цветовете и какви са, т.е. за да подскажа още повече - ти виждаш почти всички цветове, но не знаеш общия брой и вид на цветовете. Ако хората са N, и ти виждаш общо K цвята, то цветовете може да са K или K+1. Ако са K+1, то K+1вия (твоя единствен) какъв точно е - не се знае!
Иначе бих казал, че решението ти има възможност да стане доста добро. В него обаче в момента има потенциален проблем - какво се случва ако няма най-дълга редица? Представи си подреждането:
червено, зелено, ТИ, бяло, черно, червено, зелено, бяло, черно...
Къде би отишъл "ТИ" в този случай? Изобщо - кой да е от другите къде би се преместил (приемаме, че ТИ не е зелено или бяло)?
Мисля, че този коментар вече ще ви даде добра насока и ще "разбиете" задачата :)
в случая който описваш горе, просто приемаш че най-дългата е с дължина 1 и тогава няма значение каде ще се наредиш, ако има повече от една редици с максималната дължина, следващите са длъжни да те последват
Ако си с единствен цвят и няма кой да ти каже какъв е невиждам как може сам да си го измислиш без да знаеш какви са възможните цветове.
Е добре, време е да изплюя част от камъчето:
"Въпреки огромното негодувание, гуруто все пак уверил участниците, че задачата има решение и всеки един може с достатъчно разумна логика да излезе от стаята и да остане член на организацията."
Това означава, че всеки цвят присъства поне два пъти! В противен случай както Mertol каза, не е възможно човек с единствен цвят да знае кой е той...
От тук задачата се решава по индукция. Стоите в кръга и гледате другите участници. Ако има човек, чието чело е с единствена лепенка, то със 100% сигурност на вашето чело има същата лепенка. На първата камбана може да излезете заедно. Ако пък са двама, то чакате. Ако видите, че те не излизат след първата камбана, то със сигурност е понеже вие сте третия (заради който те не са излезли). Така излизате на втората камбана... и т.н.
Получава се така, че на първата камбана излизат всички двойки цветове. На втората - всички тройки цветове. На третата - всички четворки цветове... и т.н.
Знаеш ли, Иванчо го сложих като допълнителна заблуда, а се оказа, че може би прецаква задачата. Готин момент - естествено не му обърнах внимание.
Може просто гуруто да е прецакал Иванчо? Ако пък е бил с редовен цвят и другите от неговия цвят си тръгнат би било проблем - той ще остане с единствен и някой друг ще се заблуди. Да, но хората не са толкова глупави (очевидно) и ще са видели, че другите от цвета на Иванчо са станали, т.е. могат да го игнорират като играч.
За двама Иванчовци наистина има проблем... Може би... Не е лоша задача - какъв е максималния брой идиоти, при които все пак задачата е решима? Трябва да се покаже тяхното разпределение... :)
Дам, изпревари ме, а го бях измислил вече.
Само да добавя някои условия.
Цветовете трябва да са помалко или равни на броя на участниците, и всеки цвят трябва да бъде използван поне веднъж.
Елементът Иванчо внася интересна интрига, защото ако виждаш по един от всеки цвят и никой не си тръгва, то значи твоя цвят се дублира с този на Иванчо.
В общи линии колкото повече хора си излизат, ще остават само Иванчо и хората дублиращи се с него.
Ако има повече от един Иванчо, мисля че задачата няма решение, поне за тези които се дублират с Иванчовците :)
Да, това й е интересното на тази, и на този тип задачи, като онази с философите с въглен на челото и хората с бели и черни шапки - решението става, само ако разчиташ, че останалите не са идиоти :)
За съжаление това е случай неприложим на практика :Р
Защо, ето че с "един идиот" няма проблем :)
Знаеш ли, Иванчо го сложих като допълнителна заблуда, а се оказа, че може би прецаква задачата. Готин момент – естествено не му обърнах внимание.....
Малка забележка от мен - на такива задачи решението винаги се цитира дословно и не се добавят външни елементи. Освен това, ако не си абсолютно сигурен, че човека, който задава условието, знае оригиналното решение на задачата, то всякакви опити за решение са необосновани, понеже всеки малък детайл от условието променя цялостната логика на играта. Подобна ситуация се разигра в блога на Пешо Събев преди около година.
В случая обаче нотката е интересна и поставя не само въпроса "каква им е била тактиката", но и много по-интересния въпрос "а колко Иванчовци могат да си позволят да имат в групата, за да не се прецакат всичките". Понеже съгласи се, ако са ен плюс един, където ен е максимума, то цялата група заминава, понеже си е позволила да приеме нелогик в редиците си.