Interesantan zadatak...

Prije mjesec dana dobio sam od prijatelja koji studira PMF zadatak koji glasi ovako:
U "irish pubu" sjede tri covjeka i piju pivo. Za jednog od njih znamo da uvijek govori istinu. Za drugog, opet, da uvijek laze, dok treci nekad laze, a nekad govori istinu. Imamo pravo da postavimo ukupno tri pitanja, na koja odgovor moze da bude sa da ili ne. Nebitno je kako cemo "raspodijeliti" pitanja, tj. da li cemo pitati jednog, pa drugog, pa treceg, ili pak samo jednog od njih. Vazno je samo da se ukupno ne smije postaviti vise od tri pitanja. Potrebno je na osnovu dobijenih odgovora zakljuciti koji od njih laze, koji govori istinu, a koji, pak povremeno laze (ili povremeno govori istinu).
To je sva postavka. Mada, moram da priznam, meni ovako postavljen zadatak ne izgleda dovoljo definisan, a mozda i jeste...
U svakom slucaju ocekujem rjesenje, ili barem prijedloge i korisna razmisljanja.

Lako se dokazuje da taj zadatak zapravo i nema rešenje. Označimo onoga ko uvek govori istinu sa +, onoga koji uvek laže sa -, a onoga ko ponekad laže, a ponekad govori istinu sa *. Neka nam na primer +*- označava da prvi uvek govori istinu, a treći uvek laže. Imamo sledećih šest mogućnosti:

1. +-*,
2. +*-,
3. -+*,
4. -*+,
5. *+-,
6. *-+.

Bez umanjenja opštosti možemo pretpostaviti da smo prvo pitanje postavili prvoj osobi. Koji god da smo odgovor dobili, ne možemo eliminisati mogućnosti 5 i 6. Dakle, neka je A skup mogućnosti koje nam ostaju ako smo dobili odgovor "da", a B skup mogućnosti koje na ostaju ako smo dobili odgovor "ne". Tada unija ta dva skupa uključuje svih šest mogućnosti, pri čemu se peta i šesta mogućnost nalaze u preseku ta dva skupa. Odatle sledi da ili oba skupa uključuju po tačno četiri mogućnosti, ili barem jedan od tih skupova uključuje barem pet mogućnosti.

U drugom slučaju nema rešenja. Zaista, recimo da skup A ima bar pet elemenata. Tada u slučaju da smo na prvo pitanje dobili odgovor "da", ne bismo mogli sa sigurnošću da utvrdimo ko je ko jer nam ostaje barem pet mogućnosti, a imamo samo četiri moguća odgovora na praostala dva pitanja (oba puta "da"; prvi put "da", a drugi put "ne"; prvi put "ne", a drugi put "da"; oba puta "ne"). Slično se dokazuje da ne možemo sa sigurnošću utvrditi ko je ko i u slučaju kada skup B ima barem pet elemenata.

Pretpostavimo da oba skupa A i B imaju po četiri elementa. Ukoliko bismo ponovo postavili pitanje prvom čoveku, ponovo ne bismo mogli da eliminišemo mogućnosti 5 i 6 bez obzira kakav odgovor dobijemo. Razmotrimo slučaj da smo na prvo pitanje dobili odgovor "da". Preostali slučaj se razmatra sasvim slično. Neka je C skup mogućnosti iz skupa A koje nam ostaju u slučaju pozitivnog odgovora na drugo pitanje, a D skup mogućnosti, takođe iz skupa A, koje nam ostaju u slučaju negativnog odgovora na drugo pitanje. Kako je i mogućnosti 5 i 6 se nalaze u preseku skupova C i D, barem jedan od tih skupova mora imati najmanje tri elementa, pa u slučaju odgovora na drugo pitanje koji odgovara tom skupu nećemo moći trećim pitanjem da odredimo ko je ko, jer imamo barem tri mogućnosti, a samo dva moguća odgovora.

Stoga drugo pitanje moramo postaviti nekom od preostale dvojice. Bez umanjenja opštosti možemo pretpostaviti da je drugo pitanje postavljeno drugom čoveku. Oba skupa A i B imaju po četiri elementa i pritom barem jednom od njih pripada barem jedna od mogućnosti 2,4. Bez umanjenja opštosti možemo pretpostaviti da skupu A pripada jedna od tih mogućnosti. U slučaju da smo dobili pozitivan odgovor na prvo pitanje, ponovo nećemo moći tu mogućnost (2 ili 4 u zavisnosti od toga koja pripada skupu A) da eliminišemo bez obzira kakav odgovor dobijemo na drugo pitanje. Neka je E skup onih mogućnosti iz skupa A koje nam preostaju u slučaju pozitivnog odgovora na drugo pitanje, a F skup mogućnosti iz skupa A koje nam preostaju u slučaju negativnog odgovora na drugo pitanje. Ti skupovi nisu disjunktni (oba sadrže bar jednu od mogućnosti 2,4) i unija im ima četiri elementa, pa opet bar jedan od njih mora imati bar tri elementa, pa u slučaju odgovora na drugo pitanje koji odgovara tom skupu, na osnovu trećeg pitanja nećemo moći sa sigurnošću da utvrdimo ko je ko.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

U redu. Sad sam nabrzaka procitao i odstampao pa cu detaljnije da razmotrim rjesenje.Cini se OK. Namece se ipak jedno pitanje: koji su to uslovi, tj. okolnosti pod kojim zadatak ima rjesenje? Da li je zadatak uopste moguce rjesiti, ako onaj koji povremeno laze, odluci da cijelo vrijeme govori istinu (ili cijelo vrijeme laze) pa se pritom ne bi mogao razlikovati od onog koji uvijek govori istinu (tj. onog koji laze). Koji je to dakle "minimum uslova" pod kojim je zadatak rjesiv? Ovo se odnosi na prvenstveno na dovoljan broj pitanja kojim cemo zasigurno znati ko je ko.

Dragan je nešto zaboravio napisati,a bitno je!
Ona trojica međusobno znaju ko je kakav,pa onda ide ovo:
Šta bi rekao ovaj tu kad bi ga ti pitao....to i to?
(Čini mi se da je ovo već bilo na ES ili sam to vidio negdje na
drugom mjestu.Ima rješenje,zašto bi inače postojao.)

Potpis

________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]

Sve jedno nemoguce je resiti iz gore navedenog razloga (bio sam tvrdoglav, pa sam probao : ), ja znam za fazon gde ili lazu ili govore istinu, pri cemu se ne zna tacan broj "lazova" (niti da li ih ima), sto vazi i za "iskrene". Ovakav problem je dosta lak za resavanje.

Potpis

Go Beograd
Reggae Serbia
Black Ark

Prvo,
zzzz hvala na dopuni. Zadatak sa tom korekturom ima mnogo vise smisla.

Medjutim, ni tada rjesenje (koje bi se oslanjalo na istinosne tablice) ne izgleda jednostavno, jer pravi problem predstavlja covjek koji povremeno laze. Dakle, treba ga odgonetnuti s minimalnim brojem pitanja. Ako neko zna, slobodno neka se javi...

Minimalan broj pitanja za prvi problem: 4.

Pitas sve tri osobe nesto ocigledno i u zavisnosti od raspolozenja '*' osobe dobijes dva tacna ili dva netacna odgovora. Onda onog sto znas koji je pitas u vezi jodnog od ove dvojice.

Potpis

Go Beograd
Reggae Serbia
Black Ark

Ja nigde nisam u dokazu pretpostavio da se oni ne znaju, niti bilo šta o tome šta oni znaju, a šta ne znaju. U dokazu se koriste jedino činjenice da ih je trojica od kojih jedan uvek govori istinu, druhi uvek laže, da za trećeg nemamo nikakvu informaciju o tome kada govori istinu a kada laže (njegova odgovaranja na različita pitanja su međusobno nezavisna, tj. istinitost nekih njegovih odgovora nama nikakvog uticaja na istinitost drugih njegovih odgovor) i da je broj pitanja ograničen na tri i da na kraju moramo znati ko je ko. Dakle, dokaz se odnosi na bilo kakav zadatak u kome su ispunjeni najmanje ti uslovi. Drugim rečima, dodavanjem uslova se ništa ne menja.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ako su dozvoljena samo pitanja ciji je odgovor da ili ne onda ovakvo pitanje nije dozvoljeno.
Ako pitas onog sto govori istinu sta bi rekao onaj sto nekad govori istinu a nekad laze morao i da odgovori sa "ne znam".
Ako lazovu postavis to pitanje situacija je jos gora. Ne moze da kaze ni "ne znam" jer je to istina a ne sme da kaze ni "da" ni "ne" jer bi to mogla da bude istina koju on ne moze da izgovori.

A da li je dozvoljeno pitanje "da li znaš šta bi odgovorio taj i taj kad bi ga pitao to i to?" ? Odgovor može biti samo da ili ne. Ne kažem da je ovo rešenje (nemam pojma) ali da li bi pomoglo? (ni to nemam pojma, sorry, trenutno sam u intuitivnoj fazi i stvarno me mrzi da razmišljam)

Moj dokaz se odnosi na sva pitanja na koja postoje tačno dva moguća odgovora. Morate povećati broj pitanja ili dopustiti pitanja na koja postoje više od dva moguća odgovora.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ne bih da namerno skrecem sa pravca vasu diskusiju, ali ja nadjoh resenje. Vrlo je jednostavno za razumevanje ali nimalo za pronalazenje. Mozda sam radio i malo intuitivno kada sam nakon analiziranja iznalazio pitanje ciji ce odgovori stvoriti onakve uslove kakve ja zelim, odnosno kakvi su mi potrebni. Ne kazem neophodni jer mozda postoje i drugi nacini da se dodje do resenja, ali ja ih ne vidim.

Mala pomoc: situacija kakvu sam zeleo je da se nakon prvog pitanja stvori mogucnost da drugo pitanje NE BUDE upuceno osobi koja daje nasumicno tacne ili netacne odgovore.

Ako si našao rješenje slobodno izloži.
Meni se čini da je ono Nedjeljkovo u redu
pa čak i kad se dozvoli samo onom što
ne laže da ima pravo reći "ne znam"
(pored mogućih odgovora "da" i "ne").

Potpis

________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]

Ok. Shvatam na sta ciljas, ali ja nemam dovoljno vremena da temeljno o tome razmislim (studiram ETF ;-) )pa, ako ti se da, obrazlozi svoju ideju detaljnije.

Sve na vidjelo... ;-)

Pozz

Ne, moje rešenje suštinski počiva na pretpostavci da svako može da da jedan od najviše dva odgovora.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Evo mene nakon dugo vremena. "dragandj", to sam ja, a otvorio sam novi username, jer izgubih sifru, a ni stari e-mail mi nije vise aktivan.

Nego, u medjuvremenu sam se malo bavio ovim zadatkom. Iako ga nisam samostalno rijesio, saznao sam kljucno pitanje pomocu kojeg je moguce rijesiti ovaj problem.

Pitamo osobu A: "Da li je osoba B pouzdanija (tj. cesce govori istinu) od osobe C?"

Ovo je pitanje izgleda sastavljac zadatka imao na umu. Na osnovu ovoga, moguce je u drugom pitanju izbjeci osobu koja povremeno laze, a samim tim, zadatak je rijesen.

E sad, i samo pitanje je malo diskutabilno, i o tom se da raspravljati.

Zanimaju me vasi komentari, nemojte se ustrucavati :-) .

Pozdrav!

Naprotiv, ova pretpostavka umnogome umanjuje opštost tvrđenja ako smo u prvom pitanju pominjali osobe B i C u različitom kontekstu.

Pitanje: "Da li osoba B češće govori istinu od osobe C?" zaista rešava zadatak. Ukoliko dobijemo potvrdan odgovor osoba koja nekad govori istinu a nekad ne sigurno nije treća osoba, pa možemo treću osobu pitati npr.: "Da li je 1+1=2"? Tako saznajemo ko je treća osoba, a ko su preostale dve saznajemo direktnim pitanjem upućenom trećoj osobi (za koju sad već znamo da li joj treba verovati ili ne). Ukoliko dobijemo negativan odgovor na prvo pitanje razmatranje je analogno, s tom razlikom što će ovaj put druga osoba biti ključna.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Bas lepo resenje, svaka cast Bojane! Kada sam video Nedeljkov dokaz, prestao sam i da razmisljam o zadatku...

Ipak mislim da je greska na drugom mestu u Nedeljkovom dokazu:

Tezina zadatka zapravo je lezala u pravilnom izboru pitanja i zaobilazenju osobe koja povremeno laze. Za ovo je bilo potrebno barem jedno pitanje. Izlazi, medjutim, da je jedno i dovoljno. Dalje, kako je Bojan vec napisao, jednim prostim pitanjem "ocigledne istine" saznajemo ko je osoba koja nije osoba koja povremeno laze. Dalje je prosto.

Medjutim, izvorno pitanje koje sam ja cuo jeste:
Pitamo osobu A:"Da li je osoba B pouzdanija od osobe C?".

Ovo pitanje sam ja preinacio u pitanje:"Da li osoba B cesce govori istinu od osobe C?", iz razloga sto "pouzdanost" nije bas jasan pojam. Naime, po mom misljenju,najmanje pouzdan je onaj koji povremeno laze, iz razloga sto nam on ne moze dati ni jednu pouzdanu informaciju. Sastavljac zadatka je imao na umu da je najnepouzdanija ( :-) ) osoba ona koja uvijek laze. Da ovdje ne bi nastala konfuzija, ja sam promijenio pitanje,nadam se - korektno.

Vidim, Bojan se odlucio da citira manje dvosmislenu varijantu.

Takodje, moracu da detaljno prodjem Nedeljkov dokaz da vidim gdje se tu mogla potkrasti greska. Cini mi se ipak da je ovo rjesenje zadatka ispravno.

Sta mislite, da li je moguce rijesiti zadatak na neki drugi nacin, tj. nekim drugim pitanjem?

@gpreda:

Može i tako da se protumači greška. Sve zajedno:

Ne možemo istovremeno načiniti obe pretpostavke. Dakle, možemo pretpostaviti bez umanjenja opštosti ovo što je crveno, ili ovo što je plavo, ali ne oba istovremeno.

Potpis

Ljubičice crvena, što si plava kô zelena trava.