Преписано

[MitkoS]

Ей това го преписвам от едно място във вида в който е публикувано там (само е публикувано като условие без решение)

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

Пробвах да я реша, но не се получи нито за 15 минути, нито за повече.
Ако ви е интересно, пробвайте и вие.

Също така, подозирам, че или трябва някаква допълнителна логическа постановка (например отвъртане на крушката, а не само включване/изключване на лампата), или трябва допълнително в условието да се укаже още нещо, като например, че със сигурност един затворник не влиза в стаята два пъти последователно.

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

[Edin_Lud]

На мен какво ми хрумва на първо четене...
Имаме два обекта, които можем да манипулираме независимо един от друг - крушката и ключа на лампата. Крушката има две положения: завита - 1и развита (оставена на пода) - 0. Ключът има две положения - включен - 1 или изключен - 0. Значи можем да номерираме 4ма затворници така:
1. винаги, когато влезе отвива крушката и оставя ключа в положение изключен - 00
2. винаги отвива крушката и оставя ключа в положение включен - 01
3. винаги в положение 10
4. винаги в положение 11

Добрата новина е, че крушката има и трето състояние - развита, колкото да не свети, но на фасунгата. При това положение можем да играем само с ключа:
5. винаги с изключен ключ, но крушката е частично развита
6. винаги с включен ключ, но крушката е частично развита

Затворник 7 следи дали е влизал след всеки един от останалите затворници и не прави нищо (или инициализира с 11, за да му е светло и комфортно ). След като види всички възможни 6 комбинации, той казва, че всички са минали през карцера.

Може да отнеме много време, но гарантира успех.

П.С. Отне ми около 10 мин, вкл. писането, така че се вписвам и в условието за време

[MitkoS]

Не искам да ти попарвам ентусиазма, ама дай да наблегнем да видим другия вариант - само с "ВКЛЮЧЕНО/ИЗКЛЮЧЕНО".

Щото така е много лесно - можем да въведем още тригери като "отвъртяна малко", "отвъртяна повече", "отвъртяна по средата", "оставена до вратата", "оставена по средата на стаята", и т.н. ... и ако го докараме до достатъчно голям брой различни тригери, то всеки затворник ще може и да сумира - не да прави едно и също, а да прави това, което ще е сумата на това което е заварил плюс неговия "персонален код". И съответно веднага щом наистина минат всичките по един път, то това вече става известно на този който минава последен

[Edin_Lud]

На втори прочит се сещам как да стане само с ключа. Пак имаме един броящ.
Ако приемем, че лампата първоначално е изключена:
Всеки затворник, който влезе в стаята включва лампата. Ако вече е включена, не прави нищо. Броящия я изключва. След като изключи 6 пъти лампата всички са минали поне по веднъж през стаята.

Не знаем първоначалното положение => броящият трябва да преброи и себе си. Т.е., за да е сигурен, трябва да брои до 7.

Глупости, това става само, ако влизат в определен ред.

[MitkoS]

Що си го задраскал, май не е чак толкова лошо ?
Ако предположим, че първоначалното положение на лампата е известно предварително (да кажем че е загасена в началото), то:
- всеки от първите шестима пали лампата само веднъж, а седмия ще гаси и брои
- тия шестимата палят, само ако я заварят загасена

[Edin_Lud]

Да, точно го поправях отново и видях, че си писал
Всеки пали лампата по веднъж. Ако е запалена или вече я е палил, не прави нищо.

[MitkoS]

А какво да правим при "неизвестно първоначално състояние на лампата" ?

[Edin_Lud]

Ще брои и себе си. Ето как си представям нещата:
случай 1: лампата не свети, първи влиза брояча
Светва, после брои до 7.
случай 2: лампата свети, първи влиза брояча
Гаси (инициализира), при второ влизане на загасено е в случай 1 - светва и после брои до 6 (вече е гасил веднъж => не е нужно да брои до 7)
случай 3: лампата не свети, първи влиза някой друг:
Светва, броячът след него е в случай 2 - гаси, и брои до 6
случай 4: лампата свети, първи влиза друг:
Не прави нищо, докато не влезе брояча - пак е в случай 2

П.С. Ето как разсъждава броячът:
1во влизане в карцера:
1.1. лампата не свети => преди мен никой не влизал => светвам => никой няма да промени състоянието, докато не влезна отново => при второто си влизане ще загася, ще се преброя и после ще броя до 6 светванията на останалите затворници
1.2. лампата свети = >
1.2.1. първоначалното положение на лампата е било такова => ще загася и ще се преброя => после ще броя до 6 останалите 6 затворници
1.2.2. преди мен е влизал някой =>ще загася и ще го преброя = > после ще броя до 6 останалите 5 затворници + себе си ( в някакъв момент ще влеза на загасено, ще запаля и после пак ще загася)

=> от 1.2.1 и 1.2.2 не ме интересува дали съм бил пръв или след някой друг - ще загася, ще преброя 1 и после ще трябва да броя още 6.

[MitkoS]

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

Защо например брояча ще знае че е пръв ? И ако не знае, как ще различи Случай 2 от Случай 3 ?

случай 2: лампата свети, първи влиза брояча
...
случай 3: лампата не свети, първи влиза някой друг:
Светва, броячът след него

[Edin_Lud]

Писали сме едновременно. Разсъжденията нямат пропуск - винаги брои до 7 и познава.

[MitkoS]

П.С. Ето как разсъждава броячът:
1во влизане в карцера:
1.1. лампата не свети => преди мен никой не влизал => светвам => никой няма да промени състоянието, докато не влезна отново => при второто си влизане ще загася, ще се преброя и после ще броя до 6 светванията на останалите затворници
1.2. лампата свети = >
1.2.1. първоначалното положение на лампата е било такова => ще загася и ще се преброя => после ще броя до 6 останалите 6 затворници

Добре, може би е по-правилно да попитам, как втория ще знае че е втори, а не е първи и че точно преди него брояча вече е минал ? Втория ще види някакво състояние на лампата, но то няма да му говори нищичко.

[Edin_Lud]

По принцип не мога да обяснявам добре в писмен вид...ще се постарая
Ако броячът влезе в карцера и лампата е загасена, значи преди него не е влизал никой. В противен случай щеше да я е запалил. Това е случай 1 или 1.1 в разъжденията. Този случай е ясен - трябва да преброи до 7.
Другият случай - броячът влиза за първи път на светната лампа. Или така си е била, или някой е влизал. При всички положения я гаси и брои 1.
След това влиза произволен затворник, който до момента не е палил лампата, може и броячът => светва, а по-късно броячът гаси - брои 2.
И т.н. до 7.

[MitkoS]

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

ПП. Ей, голяма работа си, да знаеш

ПП2

След това влиза произволен затворник, който до момента не е палил лампата, може и броячът => светва, а по-късно броячът гаси - брои 2.
И т.н. до 7.

Предлагам брояча да не пали никога, а само да гаси.
Щото изгаси ли я 7 пъти без да я е палил, пак значи че всички са минали.

Но ако пали един път и гаси 7 пъти в следната последователност:
Гаси + Пали + 6xГаси
то може един от шестимата още да не е минал
Затова викам само да гаси - седем пъти

[Edin_Lud]

Затова викам само да гаси - седем пъти

Така няма да може да преброи до седем, ако първоначално лампата не е светела и броячът е влезнал пръв. Ще загаси 6 пъти и ще му се изчака чакането след това.

Излиза, че първото влизане на брояча е важно, за да се избере правилна стратегия.
Ако първото му влизане е на изгасена лампа, значи той е първият влязъл затворник. Може и да не пали - вече знае, че трябва да брои 6 души => гаси 6 пъти и познава.
Ако е на светната лампа, не може да познае дали преди него е имало някой. В този случай трябва да почне да гаси лампата, докато не му се случи да влезе на загасено. В този момент ще знае, че е влезнал след себе си.
Ако вече е преброил до 7, смело може да познае, че всички са влизали - бил е пръв на светната лампа и после е гасил след всеки от останалите затворници.
Ако е преброил до по-малко то 6 е очевидно, че не всички са минали. Броячът продължава да чака.

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

[MitkoS]

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

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