Пак за лъжци, честни и др.

[dedis]

Пред вас стоят трима мъдреци (знаят всичко) условно наречени А, В и С.
Единият говори само истината (И).
Другият винаги лъже (Л).
Третият е шегаджия (Ш) - скрито хвърля монета ези/тура и така определя дали да каже "да" или "не".
Задавате само два въпроса с отговори да/не и определяте съответствието на А, В и С с И, Л и Ш.
Пояснения:
1. Въпросите се задават последователно във времето (вторият може да зависи от отговора на първия).
2. Въпросите се задават всеки път само на един от мъдреците - може и на един и същ - по ваш избор. Получавате отговор само от него.
3. Възможен отговор е и мълчание - когато мъдрецът не може да определи еднозначно отговора. Но това се брои за въпрос/отговор. Само Ш винаги ще отговаря, щото не му пука.
3. (НАЙ-ВАЖНОТО) Мъдреците разбират български, но отговарят на техен си език, който вие не знаете. Отговорите са "му" и "гу". Единият означава "да", а другият "не", но не знаете съответствието.
Дано не пропускам нещо.
Който се е спасил от минното поле на Камен - да заповяда.
Жалим Wise, мацки няма, ама може да измислим нещо - я в условието, я във въпросите .

[MitkoS]

Посочваме с ръка B и задаваме следния въпрос към А:
"Вярно ли е, че ако го попитам тоя дали лъже, то той ще отговори МУ ?"

Разглеждаме следните два случая: Случай1 - В е Ш и Случай2 - В не е Ш

Случай 1 - В е Ш (това е по-лесния случай)
Тогава, независимо дали А е И или А е Л, то А ще замълчи на този въпрос. При другия Случай2, А със задължително ще каже нещо и няма да замълчи, затова сега от мълчанието със сигурност можем да определим, че сме в този Случай 1 и че В e Ш.
При което можем да питаме пак А "Вярно ли е, че ГУ е ДА ?"
На този въпрос И винаги отговаря ГУ, а Л винаги отговаря МУ (независимо дали ГУ е ДА или ГУ е НЕ)
И ако на този втори въпрос получим отговор ГУ, то със сигурност можем да определим, че търсеното съответствие е (А=И, B=Ш, C=Л)
А ако на този втори въпрос получим отговор МУ, то със сигурност можем да определим, че търсеното съответствие е (А=Л, B=Ш, C=И)

Случай 2 - В не е Ш
Тогава със сигурност, ще получим някакъв отговор от A и затова успяваме със сигурност да определим, че В не е Ш, което всъщност е важното за момента.
При което задаваме същия въпрос на В, но посочваме с ръка C.
Ако В замълчи, то със сигурност можем да определим, че C е Ш, и ще трябва да тълкуваме отговора на първия въпрос към А, за да определим съответствието докрай.
Ако В не замълчи, то със сигурност можем да определим, че А е Ш и ще трябва да тълкуваме отговора на втория въпрос към В и да игнорираме първия въпрос към А и неговия отговор.

Дотук, важното е, че сме успели да определим двамата които не са Ш (т.е. изолирали сме Ш), а също така имаме отговор на въпрос относно тия двамата (т.е. питали сме единия от тия двамата, посочвайки другия от тия двамата). А от тълкуването на тоя отговор, ще определим кой точно от двамата е И и кой е Л.

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

ПП. Да, объркал съм. Но лесно се поправя с добавяне на "изключително или - XOR" и въпроса се изменя така:
"Вярно ли е че: или (ако го попитам тоя дали лъже, то той ще отговори МУ), или (МУ е ДА) ?"
т.е.
"Вярно ли е че: (ако го попитам тоя дали лъже, то той ще отговори МУ) XOR (МУ е ДА) ?"

[MitkoS]

"Вярно ли е, че ако го попитам тоя дали лъже, то той ще отговори МУ ?"

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

Най-лесно се онагледява с таблички, но тъй като ми е трудно тук в поста да пиша текстови таблички с променлива ширина на колоните, ще го направя с равенства и изчисления, като ще ползвам следните означения:
- с 0 ще означавам лъжа, с 1 ще означавам истина
- с И(въпрос) ще означавам отговора на И на въпроса в скобите
- с Л(въпрос) ще означавам отговора на Л на въпроса в скобите
- ако X и Y са две стойности, то с "X==Y" ще означавам верността на израза "X и Y са равни"
- ... и разни други интуитивни означения, които ако не се разбират какво точно значат, то питайте ...
- ... като например, пак с 0 ще означавам "НЕ" и пак с 1 ще означавам "ДА"

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

Вариант 1:
При тоя вариант ГУ означава ДА, а МУ означава НЕ, т.е. ГУ=1, МУ=0

Ако сме питали И, то имаме:
"получен отговор от И" = И("ако го попитам тоя дали лъже, то той ще отговори МУ") =
= И(Л(1)==МУ) = И(0==МУ) = И(1) = 1 = "ДА" = ГУ (ГУ, защото при тоя Вариант ГУ е ДА)

Ако сме питали Л, то имаме:
"получен отговор от Л" = Л("ако го попитам тоя дали лъже, то той ще отговори МУ") =
= Л(И(0)==МУ) = Л(0==МУ) = Л(1) = 0 = "НЕ" = МУ (МУ, защото при тоя Вариант МУ е НЕ)


Вариант 2:
При тоя вариант ГУ означава НЕ, а МУ означава ДА, т.е. ГУ=0, МУ=1

Ако сме питали И, то имаме:
"получен отговор от И" = И("ако го попитам тоя дали лъже, то той ще отговори МУ") =
= И(Л(1)==МУ) = И(0==МУ) = И(0) = 0 = "НЕ" = ГУ (ГУ, защото при тоя Вариант ГУ е НЕ)

Ако сме питали Л, то имаме:
"получен отговор от Л" = Л("ако го попитам тоя дали лъже, то той ще отговори МУ") =
= Л(И(0)==МУ) = Л(0==МУ) = Л(0) = 1 = "ДА" = МУ (МУ, защото при тоя Вариант МУ е ДА)

т.е., независимо от варианта,
И винаги отговаря ГУ, а Л винаги отговаря МУ,
което ни позволява да определим със сигурност кой кой точно е.

[dedis]

"Вярно ли е, че ако го попитам тоя дали лъже, то той ще отговори МУ ?"

Предполагам, че това е вторият въпрос, в случай 2,отправен към В, сочейки С.
Обяснил си случай, в който С е или И или Л. Но не и ако е Ш - тогава май трябва да тълкуваш и отговора на първия въпрос, за да решиш задачата.

т.е., независимо от варианта,
И винаги отговаря ГУ, а Л винаги отговаря МУ,
което ни позволява да определим със сигурност кой кой точно е.

Искам да кажа, че има и вариант да не чуеш отговор.

[Tommorow]

Въпрос към мъдрец А:
Дали ще отговориш с "МУ" на въпроса използвайки дума на вашия език значеща "ДА" дали ти( мъдрецо А ) и мъдреца Б ще дадете еднозначен отговор ако ви попитат: @dedis ли беше човека задал загадка от 1996 известна още като THLPE в нейния вариант за два въпроса?

мълча мълча

[dedis]

Ей, куче, браво, надуши източника, макар че го бях маскирал с моя редакция. Нарочно, за да не се намери лесно в нета решението.
Точно така! Това се води за вариант на най-трудната логическа задача от този тип ever. Митето набара бързо решението и то с негови, оригинални по замисъл, въпроси. А най-трудният вариант е със зарче с три състояния на Ш, т.е. той може случайно и да мълчи. Но тогава май не става само с два въпроса.

[Tommorow]

Бях я срещал много отдавна някъде около 2000г където се изписаха цели дисертации по темата. Решенията при три въпроса не са проблем, решението и на твоята версия за два въпроса не е проблем, освен обаче при варианта с трите състояния на "комарджията" решение за два въпроса няма и при вариант като горния, но с изискване въпросите те да се зададават само на един от мъдреците.

[MitkoS]

Предполагам, че това е вторият въпрос, в случай 2,отправен към В, сочейки С.
Обяснил си случай, в който С е или И или Л. Но не и ако е Ш - тогава май трябва да тълкуваш и отговора на първия въпрос, за да решиш задачата.Искам да кажа, че има и вариант да не чуеш отговор.

Всичко съм си обяснил, както трябва (в двата последователни поста):

Случай 2 - В не е Ш
Тогава със сигурност, ще получим някакъв отговор от A и затова успяваме със сигурност да определим, че В не е Ш, което всъщност е важното за момента.
При което задаваме същия въпрос на В, но посочваме с ръка C.
Ако В замълчи, то със сигурност можем да определим, че C е Ш, и ще трябва да тълкуваме отговора на първия въпрос към А, за да определим съответствието докрай.
Ако В не замълчи, то със сигурност можем да определим, че А е Ш и ще трябва да тълкуваме отговора на втория въпрос към В и да игнорираме първия въпрос към А и неговия отговор.

Дотук, важното е, че сме успели да определим двамата които не са Ш (т.е. изолирали сме Ш), а също така имаме отговор на въпрос относно тия двамата (т.е. питали сме единия от тия двамата, посочвайки другия от тия двамата). А от тълкуването на тоя отговор, ще определим кой точно от двамата е И и кой е Л.

[MitkoS]

Ето ви нещо доста по-лекичко да не скучаете. Копирам го от друго място (там не е решено, но така или иначе е доста лесно).
(copy/paste)

Представете си, че се намирате на космически кораб с N процесора. Удря ви астероид и се развалят по-малко от N/2 процесора. Как с най-много N-2 въпроса можете откриете работещ процесор, като един въпрос се състои в питането какво мисли даден процесор за друг процесор (друг, т.е. без него самия). Всеки повреден процесор винаги лъже, т.е. за работещ процесор казва, че не работи и обратно, а всеки работещ винаги казва истината.

[dedis]

Прав си, Мите!
Просто се чудех как да стиковам двата поста. Но ти си подходил с математическа лаконичност.
Да подхващаме твоята задача. За три компа, с един въпрос...мисля (значи съществувам, пардон, мързелувам...)...

[dedis]

За три компа (един скапан) питаме някой от тях:
"И двата ли компа, освен теб, са скапани?"
"Не" означава, че сме попаднали на здрав комп,
"Да" - скапан. Т.е. другите два са здрави.
Така става ли, за да продължавам?

[MitkoS]

Ами не е така, защото "И двата ли компа, освен теб, са скапани?" всъщност трябва да се брои за два въпроса (даже три), защото питаме за два(три) процесора.

В другия форум (там откъдето преписах условието) задачата вече е решена и доколкото става ясно от написаното, решена е от ученичка в начални класове (3ти-5ти клас).

Честно казано, учудвам се, че тук не беше решена бързо - или няма интерес, или я надценявате.
Или пък, пак е някаква "добре известна задача" и затова никой не се хаби да я решава.
Както и да е, на мен не ми беше известна предварително, стори ми се интересна и приятна занимавка и затова я публикувах тук (бях добре подгрял от предишната задача и ми трябваха 10-тина минути за да видя решението - по-точно, едно от решенията).

ПП. А иначе, човек справи ли се при N=3, лесно ще се справи и с общия случай.

[dedis]

Разбрах условието.
За три - 1, 2 и 3 питаш 1 дали 2 е здрав.
"Да" означава, че и 1 и 2 са здрави.
"Не" - че е здрав третият.
За 4 - питаш първия и втория дали е здрав третият.
При еднакви отговори, здрави са 1 и 2.
При различни - здрави са 3 и 4.
Е, утре продължението.

[MitkoS]

"Да" означава, че и 1 и 2 са здрави.

"Да" означава че са от "един модел" преди всичко. И понеже в конкретния случай имаме N=3, то следва, че са "здрави" (2 > N/2 = 3/2).
Лаконичността била заразна, не знаех.

[dedis]

Ти форсираш индукцията на доста ранен етап, но да опитаме:
И - работещ правилно комп.
Питаме първите N-2 какъв е (N-1)-ят или N-тият, но да е един и същ във всичките питания.
Ако има най-малко N/2 еднакви отговори - те са дадени от И - компове.
В противен случай - последните два компа са И.
Доказателството, че индукцията е пълна (ако решението е вярно за N, е вярно и за N+1) го оставям на математиците.