Cím: Az igazmondó, a hazug és a kiismerhetetlen emberekről
Szerző(k):  Blecher, B. 
Füzet: 1981/április, 145 - 149. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az igazmondó, a hazug és a kiismerhetetlen emberekről*

 
A gondolkodtató matematikai feladatok között különösen érdekesek a logikai feladatok. Ezek általában nem kívánnak különösebb matematikai ismereteket, és megoldásaikat még azok is meg tudják érteni, akik különben távol állnak a matematikától. Ebben a cikkben négy ilyen logikai feladatot ismertetünk. A feladatokban lesz szó igazmondó emberekről, akik minden esetben csak az igazat mondják, és hazugokról, akik csak hazugságot mondanak. Azonban, ahogyan látni fogjuk, a legnehezebbek és egyúttal a legérdekesebbek azok a feladatok, melyekben még kiismerhetetlenekkel is találkozunk, azaz olyan emberekkel, akik bármit mondhatnak csakhogy a kérdezőt minél jobban összezavarják.
 
1. feladat*. Két út találkozásánál, melyek közül az egyik az A városba, a másik pedig a B városba vezet, egy matematikus találkozik valamelyik város lakójával. Az A városban csupa igazmondó ember lakik, a B városban pedig csak hazugok élnek. Megtudhatja-e a matematikus egyetlen kérdéssel, hogy melyik út vezet a A városba?
Erre a feladatra még akkor is ,,igen'' a válasz, ha még azt a további megszorítást is tesszük, hogy csak olyan kérdést lehet feltenni, melyre ,,igen''-nel vagy ,,nem''-mel kell válaszolni. Például az 1. feladatot megoldó kérdés a következő lehet: ,,Ez az az út (és az egyik útra rámutatunk), amelyik az ön lakhelyére vezet ?'' Könnyen ellenőrizhetjük, hogy az ,,igen'' válasz azt jelenti, hogy az út A-ba vezet, a ,,nem'' válasz pedig azt, hogy B-be. Valóban, ha a válaszadó az A város lakója, akkor mindig igazat mond, ezért az ,,igen'' azt jelenti, hogy a kérdéses út A-ba vezet, a ,,nem'' válasz pedig azt, hogy B-be. Hogyha a válaszadó B-ből való, akkor az ,,igen'' válasz ‐ mivel ez az ember soha nem az igazat mondja ‐ azt jelenti, hogy az út nem B-be vezet, vagyis hogy A-ba, a ,,nem'' válasza pedig azt jelenti, hogy az út a lakhelyére, azaz B-be vezet. Így mindkét esetben az ,,igen'' válasz jelenti azt, hogy az út A-ba, a ,,nem'' válasz pedig azt, hogy B-be megy, ahogyan állítottuk.
Vegyük észre, hogy a megoldás során nem döntöttük el, hogy A vagy B város lakójával beszéltünk, de erre nem is volt szükségünk. A szerző sok más megoldását is ismeri ennek a feladatnak, de mindegyik egy és ugyanazon az ötleten alapszik: azt a kérdést, hogy az egyik út A-ba vezet-e, olyan formában kell feltenni, hogy a hazugnak ,,kétszeresen tagadott'' választ kelljen adnia. S mivel a kétszeresen tagadott állítás ekvivalens az eredetivel, azért ilyenkor a hazug ugyanazt a választ adja, mint az igazmondó. Ez történt a mi megoldásunkban is.
A második feladat, amit elemezni fogunk, az elsőnek egy nehezített változata. A nehezítés abban áll, hogy a válaszadók közé egy kiismerhetetlen is kerül.
 
2. feladat. Az 1. feladat feltételei mellett tegyük fel, hogy a matematikus az elágazásnál nem egy, hanem három emberrel találkozik. Közülük az egyik az A városból, a másik a B városból való, a harmadik pedig kiismerhetetlen. A matematikus tudja, hogy a három közül az egyik A-beli, a másik B-beli, a harmadik pedig kiismerhetetlen, de azt már nem tudja, hogy ki kicsoda. Megtudhatja-e két kérdéssel, hogy melyik út vezet A-ba?
Kicsit pontosabban fogalmazva: mindkét kérdését az ott álló három ember bármelyikének felteheti, de a kérdésekre csak az válaszol, akinek azt feltette. Ezen kívül a három ember tudja egymásról, hogy ,,ki kicsoda'' és azt is, hogy melyik út vezet A-ba és melyik B-be.
Az első feladat megoldása a következő ötletet adja. Ki lehetne-e az első kérdéssel a három ember közül választani valakit, aki biztosan nem a kiismerhetetlen (vagyis aki kiismerhető)? Ezzel ugyanis a 2. feladatot visszavezetjük az 1. feladatra: a kiválasztott embernek ugyanazt a kérdést tennénk fel, mint az első feladat megoldásánál, és a válaszból megtudnánk, melyik út vezet A-ba. Bár ilyen kérdést fel lehet tenni, de a kérdésre, legalábbis a szerző véleménye szerint, nem könnyű rájönni.
Az egyszerűség kedvéért állítsuk sorba a három embert. Az elsőnek a következő kérdést tesszük fel: ,,Tegyük fel, hogy mindhárman, azonnal elindulnak vagy az A-ba vagy a B-be vezető úton a következő feltételek szerint: az A város lakója A-ba, a B város lakója B-be, a kiismerhetetlen pedig ‐ hacsak nem ön az ‐ önnel tart, ha pedig ön a kiismerhetetlen, akkor oda indul, ahová tetszik. Vajon ezekkel a feltételekkel ez az ember (itt a másodikra mutatunk) A-ba indulna el ?''
Azt állítjuk, hogy ha a válasz ,,igen'', akkor a harmadik ember biztosan nem kiismerhetetlen, ha pedig a válasz ,,nem'', akkor a második nem az. Valóban, ha a kiismerhetetlent kérdeztük meg, akkor sem a második, sem a harmadik nem kiismerhetetlen. Ha a kérdést az igazmondónak tettük fel, akkor az ,,igen'' azt jelenti, hogy a második a kiismerhetetlen, következésképp a harmadik nem az. Ellenkezőleg, a ,,nem'' válasz arról tanúskodik, hogy a második ember a hazug (hiszen csak a hazug nem megy vele együtt). Ha ugyanezt a kérdést a hazugnak tesszük fel, akkor az ő ,,igen''-je azt jelenti, mivel a kiismerhetetlen B-be tart, az igazmondó pedig A-ba, hogy a második ember a kiismerhetetlen; a harmadik pedig az igazmondó. A ,,nem'' válasz pedig, éppen ellenkezőleg, azt jelenti, hogy a második az igazmondó, a harmadik pedig a kiismerhetetlen.
Az összes lehetséges esetet végignézve láttuk, hogy az ,,igen'' válasz esetén a harmadik, a ,,nem'' válasz esetén a második ember egészen biztosan kiismerhető. Ily módon mindkét esetben ki tudjuk választani az egyik kiismerhető embert, és ezzel a 2. feladatot megoldottuk.
Vegyük észre, hogy az 1. feladat megoldásához hasonlóan az alapötlet az, hogy a hazugot kétszeres tagadásra kényszerítettük, azaz elértük, hogy válaszai ugyanazok legyenek, mint az igazmondó válaszai, és ezzel a kérdéssel megkülönböztettük a kiismerhetetlent a többiektől.
 
3. feladat*. Egy tudományos kongresszuson N tudós vesz részt, piripócsiak és nekeresdiek. A résztvevők között a piripócsiak vannak többen, és mindig igazat mondanak, a nekeresdiek viszont mindig hazudnak. A kongresszusra egy matematikust küldtek azzal a feladattal, hogy állapítsa meg a tudósokról, hogy ki honnan jött. Ehhez bármelyik tudóstól megkérdezheti, hogy bármelyik másik tudós honnét való. Adjunk még olyan eljárást, mellyel a matematikus N-1 kérdéssel ki tudja deríteni, hogy ki hova való.
A 3. feladat megoldása aránylag egyszerű. Nevezetesen kérdezzünk meg egy tetszőleges tudóst (a meghatározottság kedvéért nevezzük őt elsőnek) az összes többiről. Végeredményben a többi N-1 tudóst két részre oszthatjuk; azokra, akikről az első tudós azt állította, hogy piripócsiak, és azokra, akikről azt állította, hogy nekeresdiek. Csatoljuk az első tudóst az első csoporthoz, és vegyük a csoportok közül a nagyobbikat. Az ebben a csoportban levő tudósok a piripócsiak, a másik csoport tudósai a nekeresdiek. (Bizonyítsuk be!) Ezzel a feladatot megoldottuk.
 
Most érkeztünk el cikkünk legfontosabb feladatához. Ennek feltételei megegyeznek a 3. feladat feltételeivel, azzal a különbséggel, hogy a nekeresdiek már nem hazugok, hanem kiismerhetetlenek.*
Ez a feladat összehasonlíthatatlanul nehezebb az előzőnél. Ez azért van így, mert bár a hazug emberek nem mondanak igazat, de mondhatni ,,következetesen hazugok'', és így válaszaikból csaknem ugyanannyi információt lehet kapni, mint az igazmondó emberek válaszaiból. A kiismerhetetlenek válasza viszont tetszőleges lehet, így tőlük sokkal nehezebb feladat bármiféle információt kapni.
Az alább vázolt megoldás egy módszert ad arra, hogyan lehet [3N/2]-nél kevesebb kérdéssel eldönteni, hogy ki piripócsi és ki nekeresdi. Pontosabban q=3k kérdéssel, ha N=2k+1 páratlan szám, és q=3k+1 kérdéssel, ha N=2k+2, páros szám (k≥1).
Elsőként azt az esetet tekintjük, amikor N páratlan. A keresett módszert k-ra vonatkozó indukcióval adjuk meg. Ha a konferencián N=1 tudós vesz részt (k=0), akkor ő nyilvánvalóan piripócsi, mivel Piripócsról jött a résztvevők többsége. Egyetlen kérdést sem kell ebben az esetben föltennünk, tehát q=0=3⋅0.
Tegyük fel most már, hogy minden, adott N=2k+1-nél kevesebb páratlan egész számra már ismerünk olyan eljárást, amely a feladatot a megkövetelt számú kérdéssel megoldja. Mutatunk N=2k+1-re is egy ilyen eljárást. A kényelem kedvéért számozzuk meg a konferencia résztvevőit tetszőleges sorrendben, és kérdezzük meg a második, harmadik stb. résztvevőt, hogy honnan jött az első. A kérdezősködést csak akkor hagyjuk abba, mikor az alábbi két esemény valamelyike bekövetkezik:
A esemény. A megkérdezett tudósok közül a többség azt állítja, hogy az első tudós nekeresdi.
B esemény. Azoknak a tudósoknak a száma, akik azt állították, hogy az első tudós piripócsi, éppen k.
Világos, hogy ha az A esemény következik be, és addig a pillanatig a megkérdezettek közül p állította azt, hogy az első tudós piripócsi, és n azt, hogy nekeresdi, akkor n=p+1. (Valóban, n>p, és ha n≥p+2, volna, akkor az A esemény már legalább egy kérdéssel korábban is bekövetkezett volna.) Ezenkívül az is világos, hogy addig q1=n+p=2n-1 kérdés hangzott el. (Speciálisan az A esemény következik be, ha mindjárt a második tudós állítja az elsőről, hogy nekeresdi, akkor p=0 és n=1.)
Ha a B esemény következett be, és n tudós azt állította, hogy az első nekeresdi, akkor a feltett kérdések száma éppen q1=k+n.
Nem nehéz belátni, hogy a kérdezősködést még azelőtt befejezzük, mielőtt a konferencián részt vevő összes tudósra sor kerülne. Valóban, tegyük fel, hogy nem így volna. Ekkor az utolsó tudós megkérdezése előtt sem az A, sem a B esemény nem következett be. Legyen ebben a pillanatban p azoknak a tudósoknak a száma, akik az elsőről azt állították, hogy piripócsi, és legyen n azoké, akik szerint az első nekeresdi. Mivel az A esemény nem következett be, azért n≤p. S mivel a B esemény sem következett be, azért p≤k-1. Így a kérdések összes száma n+p≤2(k-1). Ha ehhez hozzávesszük az első és utolsó tudóst is, akkor azt kapjuk, hogy a konferencia résztvevőinek száma legfeljebb 2k, noha összesen (2k+1)-en vannak. A kapott ellentmondás igazolja, hogy az A és B események valamelyike biztosan bekövetkezik még azelőtt, mielőtt az utolsó tudóst is meg kellene kérdeznünk.
Tegyük fel, hogy az A esemény következett be. Állítjuk, hogy abban a csoportban, mely az első tudósból és a megkérdezettekből áll, a nekeresdiek legalább annyian vannak, mint a piripócsiak.
Valóban, ha az első tudós piripócsi, akkor az az n tudós, aki őt nekeresdinek mondta, maga is Nekeresdről jött. Mivel a csoportban összesen 1+n+p=2n tudós van, azért a nekeresdiek száma nem kevesebb a piripócsiak számánál. Ha viszont az első tudós nekeresdi, akkor az a p tudós is nekeresdi, akik róla azt állították, hogy piripócsi. Ezért ez esetben is a nekeresdiek száma legalább 1+p=n.
Továbbá a feladat feltételei szerint a piripócsiak együttvéve többen vannak a nekeresdieknél, ezért az N-2n=2(k-n)+1 főből álló maradék társaságban a piripócsiak száma szintén meghaladja a nekeresdiekét. Az N-2n nyilvánvalóan kisebb N-nél, ezért az indukciós feltételünk szerint létezik olyan, legfeljebb q2=3(k-n) kérdést felhasználó eljárás, amely tisztázza, hogy a maradék társaságban melyik tudós hová való. Válasszunk ki most ebből a társaságból egy piripócsit (ilyen nyilvánvalóan van), és kérdezzük meg tőle (erre q3=1 kérdést használunk el), hogy az első tudós honnan való.
Ha Nekeresdről való, akkor az a p tudós aki azt állította, hogy ő piripócsi, biztosan Nekeresdről jött. Ezért csak az maradt hátra, hogy a Piripócsról való tudósunk segítségével megtudjuk, hogy az az n tudós honnan jött, akik az első tudósról azt állították, hogy nekeresdi (ehhez q4=n kérdés kell). Végeredményben tehát a konferencia mindegyik résztvevőjéről megtudtuk, hogy honnan jött, és ehhez összesen q=q1+q2+q3+q4=2n-1+3(k-n)+1+n=3k kérdést tettünk fel, ahogyan azt ígértük.
Ha az első tudósról az derülne ki, hogy piripócsi, akkor az az n tudós, aki őt nekeresdinek mondta, biztosan nekeresdi lakos. Így a piripócsi tudósunk segítségével csak azt kell tisztáznunk, hogy az a p tudós honnan való, akik szerint az első tudós piripócsi. Ehhez q4=p kérdés kell, és a kérdések száma összesen q=q1+q2+q3+q4=2n-1+3(k-n)+1+p=3k-1, eggyel kevesebb, mint amennyit felhasználhattunk volna. Ezzel azt az esetet, mikor az A esemény következett be, teljesen kielemeztük.
Tekintsük most azt az esetet, mikor a B esemény következik be. Állítjuk, hogy ekkor az első tudós piripócsi.
Valóban, ha nekeresdi volna, akkor az a k tudós, aki őt piripócsinak mondta, szintén Nekeresdről jött volna. Így a nekeresdiekből legalább k+1 lenne, több a tudósok felénél, ellentétben a feladat feltételeivel.
Így az első tudós piripócsi, és az az n tudós, aki róla azt állította, hogy nekeresdi, maga is Nekeresdről való. Most azt az első tudós segítségével tisztázzuk, hogy ki hova való a közül a k tudós közül, akik őt piripócsinak mondták (ehhez q2=k kérdést használunk el), és hogy ki hová való azok közül, akiket korábban még nem kérdeztünk meg (ehhez további q3=N-(1+k+n)=2k+1-1-k-n=k-n kérdésre van szükség).
Ezzel tökéletesen tisztáztuk mindegyik lakhelyét q=q1+q2+q3=k+n+k+k-n=3k kérdéssel. Mindkét lehetséges esetet ‐ amikor az A esemény és amikor a B esemény következik be ‐ megvizsgáltuk, tehát páratlan sok résztvevő esetére a feladatot teljesen megoldottuk.
Páros N esetén a feladat megoldása szó szerint megegyezik azzal, amit páratlan N-re megadtunk, és gyakorlásként azokra hagyjuk, akik alaposabban meg kívánják érteni a bemutatott megoldást.
*Kvant, 1980, 11. szám

*Az 1. és a 2. feladatot a szerző először Major Péter magyar matematikustól hallotta. Lásd még Futó Péter cikkét: A sivatag törvénye, avagy: ne bántsd a hazugot! KÖMAL, 1979. szeptember, 12. oldal.

*A feladatnak itt az F.2255-nek megfelelő változatát mondjuk el.

*Lásd az F. 2255. feladat megoldását 1980. októberi számunk 67. oldalán. Az F. 2255. feladat azt követelte, hogy a) N2/2, illetve b) 10N kérdéssel döntsük el, hogy ki hová való.