Междинна (Програмисти...)

[MerlinBG]

В една IT фирма шефът страшно се ядосал на програмистите какви са кухи лейки - само бъгове, софтуерът хич го нямало - решил да ги уволнява всичките 100 човека! Решил обаче да им даде последен шанс с една логическа задачка. Ще ги нареди ги в редица... малко странна редица, диагонална една такава - всеки вижда всички наредени пред него и никого зад себе си. Т.е. последният вижда всички, първият - никого. Ще им сложи шапки - има избор между червени и сини в неограничени количества. На всеки програмист - по шапка. Който си познае шапката - остава, който не успее - да си търси нова работа. Заплатите във фирмата са супер високи и изобщо условията на работа са перфектни, така че приемаме, че всеки би желал да запази работата си. Познаването става по следния начин - първо последния в редичката (който вижда всички) обявява на глас цвета на шапката си (т.е. какво предполага), после следващият и т.н. до първият, които не вижда никого. Програмистите имат 1 час да измислят как да се спасят (или поне част от тях) от уволняване. Помежду си всички са много добри приятели и биха направили всичко да си помогнат... доколкото могат, но имат сериозни затруднения с измислянето на начин за "спасение".
Колко най-много програмисти бихте могли да спасите със сигурност от уволнение И как

Хм, едно уточнение - познаването става не на глас, както първоначално бях писал, а шефът минава от зад напред със специална клавиатура с 2 бутона (абсолютно безшумни, както може да се сетите) - червен и син - според цвета на шапката. Програмистът, който е на ред, има точно 30 секунди да въведе своя избор, ако не го направи в този интервал автоматично се смята за отпаднал. След натискането на бутона системата изчаква да доизтече остатъкът от 30-те секунди след което обявява предположението на голям монитор, който виждат всички, след което почват да текат 30-те секунди за следващия програмист. През цялото време шефът зорко следи за всякакво възможно шмекеруване, което се наказва най-сурово.

[Wise]

Това не е ли осакатен вариант на задачата на @Bibi за някакъв остров и шапки - бяха 3 вида даже...
А по принцип - може и за N!
Идеята е да се умножава по 1,2,3... и сумата да се дели на хората. После се гледа остатъка.
Там бяха в кръг, а сега - не.
Не знам дали има значение - може и да е различно, но по-късно ще мога да помисля.....
//извинявам се за оффтопика

//Май е добра идея да се преглеждат публикуваните, че иначе модераторите ще трябва да се гърчат!!


///Сега виждам, че май сме си сирачета - @FearMe -искам червей........искам го пеееечен........

[Lazar]

99
Разбира се - при условие, че през този един час за подготовка шапките са им на главите и те могат да разговарят помежду си в редицата (защото това не е уточнено в условието). Ето как:
1) Последният(този, който вижда всички) съобщава на глас: "Виждам Х броя сини и Y броя червени шапки".
2) Предпоследният съобщава на глас: "Виждам (например) Х-1 сини и Y червени шапки", като едновременно с това прави и извода за себе си, че той е със синя шапка, защото сините са намалели с една. И така нататък до първия. Само на последния, горкия (този дето вижда всички) няма кой да му даде информация как е преди него. Ако обаче програмистите наистина са кухи лейки, броят на спасените от уволнение може да е по-малък!

//Май е добра идея да се преглеждат публикуваните, че иначе модераторите ще трябва да се гърчат!!

На всичко отгоре съставът им намаля на половина...

[MerlinBG]

@Lazar: е не, шефът им е казал какви са условията и ги е пуснал да се разбират, самото нареждане и слагане на шапки ще е след това и тогава никакво говорене!
@Wize: възможно е, не знам - чета назад, но още съм доста далеч от началото... аз самият съм срещал няколко различни вида задачки за шапки, решението на тази е различно като подход от тези на другите които знам... така че дано не повтарям давана задачка

[MitkoS]

Поне половината могат да си запазят работата.
Например, тези които са с четен номер, избират цвета на непосредствено стоящия пред тях с нечетен номер. И по-този начин, всички които са с нечетен номер, предварително ще знаят какъв е техния цвят, тъй като пряко им се подсказва от този зад тях. А
пък тези с нечетен номер, разчитат с (*)вероятност 50% техния цвят да съвпада с този на човека пред тях.

Това разбира се, едва ли е най-доброто решение, но поне е ясно, че има достатъчно проста стратегия, при която поне 50% "оцеляват".

И един въпрос към условието:

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

След като N-тия програмист натисне бутона, става ли веднага ясно какъв е резултата, т.е., (N-1)-вия преди да натисне бутона знае ли дали този отзад (N-тия) е "оцелял" ?

//
(*)вероятност 50% - на пръв поглед, изглежда че вероятността е 50%, но като се замисля, това може и да не е така. Така или иначе, това не променя резултата при тази стратегия, а именно - най-малко половината "оцеляват"

[tonych]

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

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

[Edin_Lud]

При тези условия 99 човека се спасяват от уволнение, а има шанс и всички да се спасят
Първият избира "синьо", ако сините са нечетни и "червено", ако са четни. После е лесно - всеки следващ брои колко сини шапки вижда и колко сини вече са "излезли" и познава собствената си.

[MerlinBG]

@MitkoS: Тези напред по принцип не разбират дали другарчетата им отзад оцеляват или не - само виждат какво е въведено - винаги след 30 секунди, дори задния да го е въвел по-бързо машината изчаква целия интервал. Наложи се да променя малко условието - жена ми cheat-на и реши задачката като въведе индиректно подсказване, нещо за което сега шефът следи зорко
@tonych: Много добре! Има доста подобен алгоритъм, който винаги осигурява шанс на последния поне 50:50 при осигурени 2/3 от другите.
Но... могат да се спасят ПОВЕЧЕ

@Edin_Lud: Браво!! Ще има да те черпят до живот

[Lazar]

При тези условия 99 човека се спасяват от уволнение, а има шанс и всички да се спасят
Първият избира "синьо", ако сините са нечетни и "червено", ако са четни. После е лесно - всеки следващ брои колко сини шапки вижда и колко сини вече са "излезли" и познава собствената си.

А къде в условието се казва, че четните са от един цвят, а нечетните - в друг?

[MerlinBG]

Ами никъде, но е ясно - при 100 програмисти последния вижда шапките на 99 - от тези 99 едните шапки ще са четен брой (или 0), а другите - нечетен...
четно + нечетно = нечетно...
Решението е ОК

[Edin_Lud]

А къде в условието се казва, че четните са от един цвят, а нечетните - в друг?

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

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

[tonych]

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

[Lazar]

Да-а-а! Супер е ! Че аз съм бил по-кух и от програмист бе, щом не схванах конспирацията !

[MerlinBG]

@tonych: Как ги докара до 95?

[tonych]

ееее помислете малко ... комбинация от по-горните разсъждения