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.

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.)

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.

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.

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.

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.

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").

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.

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.

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.

Nije baš jasno šta znači "nekim drugim pitanjem". Svakako da je moguće preformulisati postojeće pitanje pitajući za neke druge osobe, postavljajući ga nekoj drugoj osobi, ubaciti negaciju ispred svega i sl. Međutim, ja bih sve to smatrao za isto pitanje (verujem da delimo to mišljenje). Ono što bi, po mom mišljenju, bilo drugačije pitanje je neko pitanje na koje odgovori "da" odnosno "ne" ostavljaju potpuno drugačije skupove mogućih situacija u odnosu na one koje sada imamo (potpuno drugačije znači da se ne mogu dobiti od sadašnjih nekom permutacijom ljudi, zamenom odgovora "da" i "ne", i na slične načine).

Ako tako gledamo dokazaćemo da postoji jedinstveno prvo pitanje koje vodi ka rešenju zadatka (i to je upravo ovo diskutovano). Tokom dokazivanja poslužićemo se nekim delovima Nedeljkovog razmatranja. Znamo da nas i pozitivan i negativan odgovor na prvo pitanje mora ostaviti sa po tačno 4 mogućnosti. Znamo i to da drugo pitanje moramo postaviti nekoj od preostale dve osobe. Ukoliko za svaku od te dve osobe postoji moguća kombinacija u kojoj oni nekad lažu a nekad ne onda važe i crvena i plava pretpostavka i Nedeljkov dokaz biva korektan do kraja. Dakle, skupovi koji nam ostaju posle odgovora na prvo pitanje su jednoznačno određeni (uz gornju definiciju), i prvo pitanje je zaista jedinstveno.

S druge strano, drugo pitanje može biti jedno od tri različita. Neka smo, na primer, dobili potvrdan odgovor na prvo pitanje (drugi slučaj se radi analogno). Tada možemo nastaviti nekim od sledećih pravaca:

1) Pitamo osobu C: "Da li je 1+1=2"? Ovaj primer je već obrađen.

2) Pitamo osobu C: "Da li osoba B češće govori istinu od osobe A"? Ostaju nam samo mogućnosti +*- i -*+ u slučaju potvrdnog odgovora, odnosno *+- i *-+ u slučaju odričnog odgovora, pa trećim pitanjem lako otklanjamo sve nedoumice.

3) Pitamo osobu C: "Da li osoba A ponekad govori istinu a ponekad laže"? Ostaju nam samo mogućnosti +*- i *-+ u slučaju potvrdnog odgovora, odnosno -*+ i *+- u slučaju odričnog odgovora, pa trećim pitanjem opet lako otklanjamo sve nedoumice.

Ispravno si protumacio sta sam htio da kazem, mada priznajem da nisam dobro definisao "razlicito pitanje", jer bih morao da otkucam upravo ono sto si ti sam zakljucio (negacija i ostalo) :-) . Naravno, pod "razlicitim pitanjem" podrazumijevao sam pitanje koje ne daje "izomorfnu" situaciju, ako se zna sta hocu da kazem (stvarno se ovdje nezgodno precizno izraziti!).
Bilo kako bilo, odgovor na moje pitanje je potpun.

Pošto ukupno ima 6 mogućnosti, opšti slučaj pitanja se može formulisati kao podskup tog šestočlanog skupa.

Pardon, moguća su pitanja oblika: ako bih pitao X osobu Y, šta bi mo Y odgovorila. Ako bih Pitao osobu X šta bi odogovorila osoba Y na pitanje Z, šta bi odgovorila osoba X itd.

Jel može za nas sa jeftinijim ulaznicama šta se tačno dobija (ili eliminiše) ako prvo natrčiš na ovog što ponekad govori istinu a ponekad laže, i pitaš ga da li je B pouzdaniji od C? Odgovoriće sa da ili ne, a oba odgovora mogu biti istiniti ili lažni, šta se tačno eliminiše?
@Nedeljko mislim da ne možeš da pitaš "šta bi odgovorila osoba...itd" jer u ovakvim zadacima lažov se ponaša tako što uvek izvrće istinu, šta ako naletiš na lažova i pitaš ga za onog što ponekad govori istinu a ponekad laže, kako da ti odgovori a da to bude laž?
Mislim da je jedino dozvoljeno pitanje ovde Da li ta i ta osoba uvek govori istinu :)

Da preformulišem: možeš uvek da pitaš za karakter osobe da li je onaj što uvek govori istinu, laže, ponekad govori istinu ili laže, a nikad ne možeš da pitaš "šta bi odgovorio... " jer onaj što ponekad govori istinu a ponekad laže ni sam ne zna šta bi odgovorio, zavisi mu od trenutne inspiracije