Една група туристи, жадни за смели приключения и вълнуващи изживявания, както си бродели из едно от най-затънтените кътчета на планетата, внезапно попаднали в плен на канибали, които, чужди на всякакво лицемерие и фалш, директно им заявили, че възнамеряват да ги изядат.
Разбира се, имало алтернатива, иначе историята нямаше да бъде за този клуб.

Най-напред канибалите донесли един чувал, от който изсипали множество разноцветни шапки и след това разяснили плана си. Туристите трябвало да се подредят в кръг, така че всеки да вижда останалите и след това, на главата на всеки турист щяла да бъде поставена една от шапките, така че той да не види каква е. След това по произволен начин щели да бъдат посочвани
туристи и щели да бъдат пощадени само онези, които успеели да отгатнат какъв цвят шапка имат на главата си.
След изясняване на тези подробности, туристите били оставени да обсъдят положението си.

Каква стратегия би им позволила да се отърват с минимум жертви ?

Горното може и да не е вярно !

Като им наредят шапките - по даден знак всеки хваща шапката на съседа си и я поставя на собствената си глава (надявам се преди това да се сетят поне да видят цвета и) :)

Това е интересен, нестандартен подход към проблема. Остава само да се надяваме канибалите да имат необходимото чувство за хумор

Горното може и да не е вярно !

съдбата на първия посочен не е за завиждане...

poneje niama informacia otnosno broia na cvetovete, i broia na shapkite ot vseki cviat, mislia che minimuma na ojivelite shte da e floor(broi) [ + niakoi drug ucelil tototo]

nai-proshaskata strategia e prosto vseki da kazva cveta na shapkata primerno v liavo, ili cveta na svoiata - ako veche ia znae

chudeh se dali da ne zvema da napisha niakia slojno izglejdashta super glupost ot sorta - parvia kazva na tozi do nego, tvoria prez 1, tretia prez 2, chetvurtia prez 3.., ama me domurzia
a i, shte da e bez znachenie, ako primerno kanibalite sa im naslagali shapkite proizvolno, bez da se stremiat vseki 2 sasedni da sa razlichni

Може би има малко повече информация, отколкото казваш.

Горното може и да не е вярно !

Зависи, хора различни - някои за всичко завиждат

Горното може и да не е вярно !

Ami iavno ste se iska samozgertva. Purviat, koito e izbran smelo kazva cveta na shapkata na suseda si ot liavo i otiva kum kazana (nai-veroiatno). Ot tuk natatuk vseki koito e "nauchil" cveta na shapkata si go kazva (kogato e popitan) i se spasiava). Vseki, koito ne go e nauchil povtaria samozgertvata na purvia turist. Ochevidno v nacaloto st ima mnogo samozgertva, no kum kraia nestata ste se promeniat.

PS. Ochevidni ako tozi otliavo veche si e "nauchil" cveta, kazvash cveta na shapkata na tozo, koito e oste po-naliavo.

Interesnoto e, che kolkoto poveche napredva procesa na zapitvane toklova po- goliama ste e informiranostta na turistite, i toklova po goliam ste e shansa na niakoi ot znaestite da bude izbran i da se spasi. Po tozi nachin skorostta na natrupvane na informiranost ste namaliava. No ne mislia , che ot gorespomenatoto tvurdenie mozge da izvlechem polezna informacia.

Ochevidno ako budat vuvedeni niakoi ogranichenia za broi cviat na shapkite i dali poveche ot edin chovek mozge da ima sustia cviat shapka togavava i strategiata ste e razlichna.

"In umbra, igitur, pugnabimus"

Редактирано от errata на 12.05.05 12:46.

Ако правилно съм разбрал идеята, половината от туристите ще имат реалната възможност да влязат в казана, защото за всеки турист, който е научил цвета на шапката си, някой друг преди това се е жертвал.
Но пък и никоя саможертва не отива напразно, стига само всеки турист изрядно да поддържа базата си от данни за това кой от другите вече е научил цвета на шапката си и кой още не

Горното може и да не е вярно !

V osbsti linii da. No nevinagi ste e viarno, che za vseki spasen ste ima edin pozhertvan. Taka naprimer ako poveche ot edin turist mozge da ima sustia cviat shapka, ochevidno poniakoga ste im stastlivi sluchainosti na spasili se ot kazana "samopozhertvovateli".
Tezi stastlivi sluchainosti za suzhalenie ste budat kompensirani ot sluchai, v koito hora veche nauchili (ot niakoi ot svoite susedi) kakuv e cveta na shapkata im ,ste budat zapitvani i suotvetno ste napuskat kruga bez da doprinesat za spasiavaneto na, koito i da e bilo drug.

S drugi dumi dva vzaimno "anulirasti" se procesa i nakraia pak ste e 50:50.

No ako ne mozhe da ima dva i poveche turisti s edin i sust cviat na shapkata iavno e, che niama i da ima stastlivi sluchainosti. Taka, che maiche poveche ste budat iziadeni otkolkoto spaseni.

I posledno, za bazata danni, iavno ste stane trudno ako nikolko turista posledovatelno budat izvikani i to vinagi v diasno ot predhodnia, no v tozi sluchai vseki "po-desen" ste triabva da predava informacia na vseki "po-liav" (za da se izbegna dublirane). Viarno ste stane po slozhno , no ne i nevuzmozhno. Vse pak v uslovieto na zadachata niamshe ogranichenia za pametlivostta na turistite (kakto i za vuzmozhnite cvetove shapki)


"In umbra, igitur, pugnabimus"

От тенденциите, които споменаваш, според мен, е в сила само тази за щастливите случайности, защото наистина няма ограничение всички туристи да бъдат с различен цвят на шапките. Всеки турист или спасява някой друг или сам се спасява, така че ще бъдат спасени поне половината туристи. В най-лошия случай на нечетен брой туристи и нито една щастлива случайност, спасените ще бъдат с един по-малко.

Иначе можеш да разглеждаш туристите като достатъчно паметливи и съобразителни

Горното може и да не е вярно !

Може и малко по-лесно. Ако посоченият турист вече знае цвета на шапката си - спасява се. Ако не знае, казва цвета на този от ляво. Ако този от ляво си знае цвета, казва цвета на този от дясно. Ако и двамата знаят цветовете си - гадае и евентуално се спасява(тогава той е последния, чийто цвят е неизвестен - случва се при нечетен брой туристи).
Имаше една задача за "мълчаливи индианци", беше нещо подобно, но сега не мога да си я спомня.

Има още една тактика, която може би е по-успешна. Обаче е необходимо туристите да са наясно с цветообразуването(даже много наясно), а диваците да не са особено придирчиви към цветовете, които използват(като примитивни хора те не би трябвало да имат богата цветова палитра).
Запитаният за цвета на шапката му отговаря по следния начин:
- ако двата му съседа имат еднакъв цвят на шапката и той е основен(червен, син, жълт), както и ако е бял или черен той го произнася. Така и двамата около него вече са информирани;
- ако двата му съседа има еднакъв цвят на шапката и той не е основен, той произнася името му с едно “светло” отпред, напр. светлозелен. Така и двамата около него вече са информирани;
- ако двата му съседа са с различни цветове на шапките, той произнася името на цвета, който би се получил при смесването им. Така всеки от двамата знае двете възможности за цвета на шапката си. Ако някой от тях бъде запитан, то той с шанс 50% ще познае. Другият вече ще бъде сигурен. След време е възможно да се получат комбинации, от които логично да следва извод за това кой с какъв цвят е;
- ако е известна комбинацията от цветове на шапките за двата му съседа, казва цвета на този отдясно или прави разкриваща комбинация отдясно;
- ако цвета на шапките на двата му съседа вече е известен, то може да даде информация за първата неизяснена двойка надясно или нещо подобно.
Има ситуации, когато този метод отстъпва на вече споменатия, но мисля че по-често ще е по-добър от него.

i, tova veche go biah napisala po gore..

kakvo ste sednali da se obiasniavate na tazi vuz tupa zada4ka, ne moga da razbera

pone polovinata drug put

ami ako sa necheten broi? pochvash da me draznish s nedoobmislenostite si, fellow!

mnogo dobre! samo che vav zadachata niama nishto zadadeno za broia na cvetovete, i ako chovekoiadcite si padat pedanti, nomera sas svetlozelenoto ne moje da mine, ako ima 5 nuansa na zeleno..

При този вариант, както го разбирам, може да се получи следното - имаме пет туриста номерирани отляво надясно от 1 до 5. В началото бива избран 2 и той (жертвайки се) спасява този отляво - 1. След това бива избран 5 и той (жертвайки се) спасява този отляво - 4. После бива избран 3 и тъй като и двамата му съседи са с известни цветове на шапките, той рискува.
Така от пет туриста, трима са изложени на произвола на съдбата и само два сигурно спасени.

Горното може и да не е вярно !

Ами това е номерът. Ако каже напр. "светлозелено", а има на себе си "тъмнозелено", винаги може да спори с диваците за субективизмът на светлоусещането(така де, важното е, че е познал цвета).

Така е, това е случаят, когато се спасяват половината без един(при нечетен брой туристи). Разликата с по-горе споменатия метод е само в смяната на посоката на обявите -така обявяваш винаги само някой съсед - не е нужно да броиш колко надясно(наляво) са информирани - достатъчно е да следиш само за двамата си съседи.

Мултиплицирай тази петорка колкото искаш пъти и на всеки пет ще имаш три пожертвани

Горното може и да не е вярно !

ако питаш мен, един гладен дивак най-вероятно няма да играе по правилата, а вместо това ще се повесели, наричайки зеленото синьо и червеното жълто

Не е така. При петте се получава защото са само толкова, т. е. кръгът се затваря. Ако не вярваш, пробвай се с 10 - тогава половината се спасяват със сигурност.

Изглежда нещо не се разбираме. Добре, нека туристите бъдат 10 и бъдат посочени в следния ред - 2, 5, 3, 7, 10, 8 ... тогава какво ще стане и кой от тези шест туристи ще бъде сигурно спасен ?

Горното може и да не е вярно !

Става така(обявяване преимуществено наляво):
- 2 спасява 3;
- 5 спасява 6;
- 3 се самообявява и се спасява;
- 7 спасява 8;
- 10 спасява 1;
- 8 се самообявява и се спасява.
До момента има 2 сигурно спасени.
Останали са 1, 4, 6 и 9. 1 и 6 вече знаят цветовете си, така че, при запитване ще си ги кажат и ще напуснат щастливи кръга. Достатъчно е 4 да каже цвета на 9 или обратното(зависи от диваците) и ще има още един щастливец.
В крайна сметка наистина не е много разумно да се сменя посоката, защото са възможни ситуации, когато двамата съседи ще знаят цвета си, а ще се налагат още обяви... Трябва да се въведе правилото при двама съседи с известни цветове на шапките да се назовава тази на най-близкостоящия с неизвестен(ако отстоянието е еднакво в двете посоки се помага на левия). Както казах, този начин не дава нищо повече от вече споменатия по-рано с броене в една посока.

Аз, разбира се, както и в предишния случай с 5 туриста, имах предвид варианта, при който 1 е отляво на 2 и тогава при посочената последователност, първите 6 туриста се жертват. Но наистина, с някои изглаждания на стратегията, можем да спасим поне половината. Въпросът е дали не можем да постигнем малко повече ?

Горното може и да не е вярно !

Би трябвало да минат с не повече от една жертва.
1) Преминаваме към модел N цвята и на всеки цвят му отговаря число от 1 до N.
2) Първият събира числата на всички получава число S и казва цветът съответстващ на S mod N( ако S mod N == 0, то казва цвят N).
3) След като първият се маха останлите събират числата които виждат(S1) и получават собственият си цвят чрез ((S mod N)-(S1 mod N)) mod N, който ако е 0-а казват N-тият цвят.

Как да осъществят стъпка 1)? - Тука вече може да философстваме дали всеки от туристите вижда по един и същи начин, дали диваците нямат непознати за туристите цветове, с които да ги изненадат и т.н.(Тогава стигаме до "аз виждам както си искам, а ти познай кое как виждам" и диваците ще изядат всички) Да речеме, че всеки от диваците и туристите различва по 16 милиона различна цвята и за всяка от шапиките нямат разминаване във възприятието и. Разбира се за първият колкото по-малко цветове толкова по-добре, макар, че ако диваците им знаят стратегията първият е обречен 100%.
2) се надявам да е ясно
3) сами се убедете, че е вярно

Това е то ! А ако съответствието е с числата от 0 до N-1, ще си спестим и някои дребни допълнителни условности. Браво !

Горното може и да не е вярно !

Браво!!!

1) малко ми е трудно да си представя как туристите ще номерират хилядите основни цветове предварително (аз поне не останах с впечатлението, че това е недопустимо - цветовете стават известни едва като се излезе в кръга.)

2) задачата използва математически трик (решението не е видимо в контекста на самата задача. Това е все едно - "ти защо не знаеш Африкаанс"?!)

3) ако се използват само цветовете видими в момента, номерирани според да речем наредбата им по дъгата, то това все още не е достатъчно всеки да познае собствения си цвят - примерно, ако имаме различен цвят за всеки от туристите, тогава всеки ще знае, че неговият цвят е точно този, който той не може да види на шапката на никой от останалите туристи. С какво ще му помогне това?

1) е сгрешено - искам да кажа, че според мен не може да се наговарят предварително цветовете.

1) N няма проблеми да е много по-голямо от реално използваните цветове. Просто всеки си казва всички цветове, които знае - правят едно обединение на тези цветове и номерират. Ако след това се появи цвят, който никой не го знае какъв е, то тогава няма смисъл да им слагат шапките на главите, а могат да им дадат да си ги гледат колкото искат - така или иначе няма да знаят какъв е този цвят. Поне аз от услоивието на задачата не останах с впечатление, че ще се появи цвят, който някой от туристите няма да може да назове, ако го види, а щом може да го назове, то значи го знае.
2) Да използва математически трик - това не видях да противоречи на условието на задачата? А и математическият трик се свежда до това да номерираш цветовете и след това да можеш да събираш и когато сумата ти стане по-голямо от N, то да вадиш N. Струва ми се доста по-просто от Африаканас.
3)Погледни малко по-нагоре - достатъчно е някой от туристите да го знае този цвят и да го е казал докато си правят стратегията - т.е. достатъчно е да е в множеството на номерираните цветове(евентуално може да си въведът и цвят 'не знам' и на който му се падне направо да ходи да го хапват).

Разбира се сега може да ми кажеш, че някой може да е далтонист, че друг да е сляп, че трети не може да запомни наредба на повече от 2 цвята, четвърти не знае да смята по модул от N, пети не знае да брои, че диваците и туристите може да виждат цветовете по различен начин и т.н.
Както и писах като давах решение, ако влезем в сферата на философията може да докараме до нито един оцелял

Ами лошо за тях, ако не могат.
Но това означава, че ще се появи цвят, който никой от туристите няма да може да разпознае.

По принцип според мене е невъзможно да има остров с канибали , на който ходят туристи, които не са обезопасени с достатъчно огнена мощ, че да ги изтребят.
Струва ми се невъзможно канибалите да тръгнат да си правят игрички с туристите - дори и ако не им трябва да изядат всички, то поне ще си изберат най-крехките.
Общо взето ми се струва невъзможно канибали и туристи изобщо да успеят да си комуникират нормално.
Ама кой ме пита.

В условието, струва ми се, съвсем ясно е казано, че възможните (цветове на) шапки са били видими за туристите, преди да започне обсъждането.

Горното може и да не е вярно !

Нещо ми писна и не доетох всичките отговори, така е може и да повторя някой но ми се стори, че няма....

значи задачката е готина но не е много лесна ....

нека допуснем за начало че цветовете са били само 2 бял и черен или къде къде по известните цветове 0 и 1 ....
и ся първия който избират гледа всички шапки събира ги и казва остатъка по модул 2 .. или ако има нечетен брой 1 казва 1 иначе 0 .. от тук нататък е тривиално как всички останали познават цвета си ....

ся тая логика може да продължи за повее цветове като колкото повее нараства броя цветове толкова повее хора отиват в наалото .. ако не се лъжа (при всички положения не ми се смята) ако имаш Н цвяата отиаха около лог с основа н от 2^Н .... което дава едно доста добро решение но винаги съм имал проблем да докажа оптималност на въпросното ...

Join the dark side, and get a free cookie.

а от самолет се вижда, че ми заяажда Ч-то за което се извинявам.....

Join the dark side, and get a free cookie.

Погледни моят отговор, че така като гледам май очакваш lgN/lg2 да бъдат изядени, а може да се мине с не повече от един.

Абе хора, не е ли най-лесно туристите да си извадят по едно огледалце и да си видят шапките....те и без това канибалите няма да са виждали до този момент огледало!!!