Инквизитор и Вещици

[drago]

Има инквизитор и 1000 жени, някои от тях вещици. Всяка жена знае коя е вещица, и коя не е, а инквизиторът първоначално не знае. След това се случва следното: Инквизитора задава на всяка жена въпрос, на който може да се отговори с "да'' или ''не''. Порядъчните жени отговарят честно, а вещиците могат да дадат всякакъв отговор. След получаване на 1000 отговори, Инквизитора нарежда да се изгори една жена. По време на екзекуцията става ясно, била ли е тя вещица. Сега остават 999 жени. Той отново задава въпроси и изгаря една жена, и така нататък. Във всеки един момент той може да спре процеса.
Докажете, че инквизиторът може да изгори всички вещици, като убие не повече от една порядъчна жена.

ПП Мисля, че си заслужава да е в отделна тема. Преведох я от руския оригинал с гугъл транслейт, с малки корекции.

[ptj]

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

[drago]

Не съм обърнал внимание на линка ти. Просто видях тази от една съседна тема(viewtopic.php?f=60&t=16872), хареса ми, и понеже там нещата отидоха в друга посока я пуснах начисто. Не е нужно да гледата линкове. Задачата ще ви достави удоволствие, ако я решите самостоятелно.

[ptj]

Малка подсказка:
След като изгорите първата жертва, целта е всеки път да намирате чрез въпросите една обикновена жена (да не е вещица), а чрез този факт да изгорите вещица...

[drago]

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

[ptj]

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

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

[drago]

Наблюдение 1. Да допуснем, че сме открили(т.е. инквизитора е открил) по някакъв начин порядъчна жена примерно [tex]W_1[/tex]. Нататък e лесно. Питаме [tex]W_1[/tex] каква е [tex]W_2[/tex], ако каже, че е вещица я горим. Ако каже, че е порядъчна, питаме [tex]W_2[/tex] за [tex]W_3[/tex] и т.н.
Наблюдение 2. Ако изгорим някоя жена и тя се окаже вещица, не губим нищо. Но ако се окаже порядъчна, нямаме право на повече грешки и трябва да имаме вече ценна информация. Какво по-ценно от това да сме я питали преди това каква е някоя друга жена и тя да е потвърдила, че е порядъчна. В този случай жертваме порядъчна жена, но ще знаем че някоя друга също е порядъчна. Това е целия анализ.

И така избираме произволна жена [tex]W_1[/tex] и питаме всички останали каква е [tex]W_1[/tex]. Ако някоя каже, че [tex]W_1[/tex] e порядъчна я горим и ако е вещица не губим нищо, но ако се окаже порядъчна ще знаем, че [tex]W_1[/tex] също е такава.
Остава случая, когато всички кажат за [tex]W_1[/tex], че е вещица. Тогава или тя наистина е вещица и като я изгорим не губим нищо или е порядъчна и тогава всички останали са вещици. Така, че просто я горим и виждаме каква е ситуацията.

[ptj]

Изчисти си идеите и напиши цялостно решение (разбито по случаи), това не е вярно.

Не забравяй, че нямаш право да изгориш повече от една порядъчна жена.

[drago]

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

[ptj]

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

Ето авторовото решение (алгоритъм) :

Нека жените са подредени в редица. Отначало инквизитора задава въпрос на всички жени започвайки от втората
" Вещица ли е първата жена". Ако някой от отговорите е "не" (т.е. че първата не е вещица), то той избира нея за първа жертва. Възможни са 2 варианта:
1) Изгорената жертва е вещица. В този случай имаме една вещица по-малко, т.е. минаваме към задача с по-малък брой вещици и отново се връщаме към началото на алгоритима. При това за случай с 2 жени очевидно инквизитора може да изгори всички вещици.
2) Изгорената жертва е добра жена. В такъв случай нейния отговор за първата жена е истина, т.е. тя не е вещица.
След това инквизитора задава на първата въпрос " Вещица ли е следващата жена?". При отговор "не" същия въпрос към следващата и т.н.
Ако изчерпа всички жени и отговорите са само "не", то всички са нормални (няма вещици сред тях).
Първия отговор "да" от [tex]i-тата[/tex] жена , ще означава ,че всички от 1-ва до [tex]i[/tex]-та са нормални, а [tex](i+1)[/tex]-вата е вещица. Тогава инквизитора екзекутира [tex](i+1)[/tex]-вата и започва отново процедурата с въпросите за съседката от i-тата.

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

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

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

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

[inveidar]

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

По принцип, ако това е вярно, щеше да е пълно с интересни задачи от този вид, а не е така. Що не вземеш да измислиш една задача и да ни демонстрираш?

[ptj]

Иска се време и мислене...

Нещо от рода на:

Във флота на Лапландия има само 3 вида криптографи.
1.) Първите разменят в радиограмите точката и тирето.
2.) Вторите кодират "точка, тире" или "тире, точка" с "точка, точка".
3.) Третите кодират обратно на вторите, т.е. "точка, тире" или "тире, точка" ги заменят с "тире,тире".

Според легендата вълшебника предавал им този начин на кодиране, имал различни каменни таблички за декодиране на произволно съобщение от морзовата азбука. Един пожар в кралската библиотеката изгорил документа, описващ начина за използването на табличките, но самите те оцеляли.
След смърта на вълшебника намерили радиограма описваща мястото на огромно съкровище. Царя обявил награда- половината от него за всеки успял да разгадае тайната + ръката на красивата си дъщеря. Гъливер бил безумно влюбен в нея и един ден успял да разгадае шифъра. Ключа в неговата идея бил на всяка табличка да съпостави точно определен набор от дешифратори (криптографи). Дали вие ще успеете да възстановите неговия успех, ако знаете че задната страна на табличките имала стълб от 4 символа (точки или тирета), а предната била еднаква за всички:
. .
. _
_ .
_ _

[drago]

...Друга добра възможност за създаване на логически задачи е теорията за крайните автомати.

И как крайните автомати ще създадат лог. задача? С тахна помощ може да се онагледи решението на такава задача, но да се създаде!? Всъщност "краен автомат" е еквивалентно на "компютър"(с крайна памет, т.е. реален компютър), имам предвид като разрешителна мощ. Така, че по-просто казано, може би имаш предвид да се създават задачи с машина. Сигурно може, но едва ли ще са толкова хубави.

А тази за Лапландия, честно казано не я схващам, може ли я да поясниш?