Задача от интервю

[Malthael]

Отвлекли са 10 души. Съдбата на човечеството е във вашите ръце. Утре десетимата отвлечени ще бъдат наредени в линия един зад друг в тъмна стая. В стаята ще бъде напълно непрогледен мрак. Извънземните ще сложат на главата на всеки човек червена или зелена шапка.

Вие сте един от отвлечените. Осветлението в стаята светва. Не можете да видите своята собствена шапка. Разпределението е всевъзможно. Може вие и хората да сте с 9 зелени и 1 червена шапка или обратно, или всички да сте със зелени или всички с червени, във всевъзможни комбинации. Започвайки от човека най-отзад извънземните питат „Какъв цвят ти е шапката?”. Всеки може да чуе отговора. Ако човекът е прав, спасява 600 милиона души по света и собствения си живот. Ако не, е издухан във въздуха и милионите хора, които представлява, са превърнати във ферма за гъби. Каква система ще предложите, за да спасите колкото може повече хора?

ЖОКЕР: Човекът най-отзад може да види всички шапки отпред пред него/нея. Има решение, което гарантира, че ще бъдат спасени 9 от 10 души в колоната.


Решение:Първият човек е попитан и има 50 на 50 шанс да оцелее. Другите деветима им е гарантирано, че ще бъдат спасени. Как така? Човекът най-отзад брои броя на зелените шапки и ако той е нечетен, той ще каже зелена. Ако е четен, ще каже червена. След това следващият човек пред него ще знае, че човекът зад него вижда или четен брой или нечетен брой зелени шапки. Следващият човек в колоната брои колко са зелените шапки. Ако все още са нечетни, той е със зелена. Казва червена и ще живее. И след това ще има нечетен брой зелени шапки пред него. Ето защо третият човек в колоната отзад напред ще може да каже дали той или тя е със зелена или червена шапка. Ако вторият човек е видял нечетен брой зелени шапки, значи има зелена шапка. И ще живее. Идеята е, че хората трябва да следят дали броят на шапките пред тях четен или нечетен, от което автоматично могат да определят цвета на тази на главата им. Тази математическа система гарантира, че ще бъдат спасени поне 9 от десетимата отвлечени и цялото население, кеото представляват.

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

[pal702004]

И какво чудно или сложно има? Съобщението на последният е информация за всички останали. Той казва четен или нечетен брой зелени шапки има в групата от 9 човека.
Всеки от групата трябва да преброи колко зелени вижда пред себе си и колко пъти отзад са казали "зелено".
Пример: Аз съм на пето място отпред - назад и информаторът е казал, че вижда, да речем четен брой зелени шапки.
Аз виждам пред себе си 2 зелени шапки, зад мен хората 3 пъти са казали "зелено" (изключваме информатора), общо 5 зелени, значи моята е зелена, защото информатора казва, че е четно.

Тоест, броят на зелените шапки, които виждам отпред, плюс броят на зелените, които чуя отзад, плюс моята трябва да е такова по четност, каквото е казал информатора.

Ама аз, какъвто съм си кърък, сигурно ще ме сложат на 10-о място

Ако ли не, зад мен някой тъп ще обърка работите

[Malthael]

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

[vel.angelov]

Друго решение е ето това:
Нека на зелена шапка съпоставим число 1,а на червена -1.
Последния казва шапка която съответства на произведението от шапките пред него-ако е -1 червена ,ако е +1 зелена.
Така всеки от редицата може да познае дали е 1 или -1,като вземе предвид съпоставените числа на шапките пред него и на информацията получена от познатите шапки.

[drago]

Да, хитро,
@Malthael: Не е глупост, а единственота възможна с-ма, гарантираща [tex]n-1[/tex] от [tex]n[/tex]спасени.
@vel.angelov: Това е абсолютно същото само с друг изказ.

Нещо повече, със същата идея може да се обобщи- шапките да са в [tex]k[/tex] цвята [tex]1,2,...,k[/tex]. Първия казва остатъка от деленето на [tex]k[/tex] на сумата от цветовете пред него. Този пред него вижда сумата от цвветове пред него и си прави извода какъв е неговият цвят... и го казва и т.н. ...всички пред последния със сигурност са спасени.