Получена по Skype

[ins-]

"Имаш 7 затворника и един карцер. Всеки от затворниците е в различна килия и не вижда нито чува другите, шефа на затвора е казал: 'Ще вкарвам колкото си искам пъти всеки от вас в карцера. Там има лампа в стаичката, когато някой от вас се осмели да ми каже че всички са минали през карцера - ако е вярно ще ви пусна, ако сгреши оставате завинаги в затвора, имате 15 мин да измислите стратегия.'"

Цитирам дословно, интересно ми е как се решава.

[Baronov]

Знам я тази задача. Има 2 варианта, при по-лесния затворниците знаят първоначалното състояние на лампата, при по-трудния - не.

[ins-]

аз не я знаех ... но определено не е лесна, особено, ако те боли главата

[dgs]

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

1. Нека предположим, че положението на лампата е известно предварително и нека да приемем, че тя е изгасена. Затворниците се наговарят за следното:
- всеки от първите шестима пали лампата само веднъж, а седмия ще гаси заварена светната лампа и ще брои
- тия шестимата палят, само ако я заварят загасена, ако я заварят светната, не правят нищо.
И така, когато седмия преброи че е изгасил лампата 6 пъти, то той заявява на надзирателя че всички са минали през карцера

2. Нека сега положението на лампата да не е известно
Абсолютно същия алгоритъм, с единствената разлика, че седмия трябва да брои до 7.

[dgs]

...
2. Нека сега положението на лампата да не е известно
Абсолютно същия алгоритъм, с единствената разлика, че седмия трябва да брои до 7.

Това не е вярно

[ins-]

Браво ... много усилия сте положили. Дано задачата да Ви е харесала. Мен ме няма на логическите задачи. Но намирам решението на почти всичко - някъде гледах в мрежата решение на английски език, ако е и за другия случай (с неизвестно състояние на лампата) ще пусна линк.

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

[dgs]

По принцип не грешиш, но има един гаден случай:

При първото си влизане, Седмия е влязъл на светната лампа и след това е направил шест изгасяния.
Какво да прави - да чака ли седмо или не ?
Ако е влязъл пръв (на светнато), значи ще има седмо и трябва да го чака.
Обаче ако не е влязъл пръв, значи и шестимата са минали и повече святкания няма да има и той ще си чака до безкрайност.
Но той не знае дали е влязъл пръв на светнато или някой от шестимата преди него е запалил лампата и не е в състояние да вземе решение дали да чака или не.

Затова, решението е такова:
1. Първите шестима палят по два пъти
2. Седмия брой до 12