Ha leírom azt, hogy „Ez a mondat hamis", akkor ez egy paradoxon. Ez a mondat nem lehet igaz, hiszen akkor éppen saját maga ellenkezőjét állítaná, de hamis sem lehet, mert akkor az állítás hamis voltából azt a következtetést lehetne levonni, hogy mégiscsak igaz. A paradoxon természetesen feloldható, többféleképpen is, lásd korábbi cikkünket. Ha viszont leírom azt a mondatot, hogy „Ez a mondat igaz", ez egy se nem bizonyítható, se nem cáfolható állítás, azaz lehet a mondat igaz is, és lehet hamis is.

Ha tehát csak úgy felirkálunk önmagukra és egymásra hivatkozó mondatokat, akkor előfordulhat, hogy az állítások egymásnak ellentmondanak tetszőleges igazságértékek esetén, tehát paradoxonra jutunk. De előfordulhat az is, hogy nincs ellentmondás, de nem is határozható meg minden állítás igazságtartalma. Szerencsés esetben pedig lehetséges, hogy csak egyetlen olyan realizáció van, amely konzisztens, így kikövetkeztethető, hogy mely állítás igaz, és melyik nem az állítások rendszerében. Tíz állítás című feladványunkban éppen az volt a kérdés, hogy mit állíthatunk az alábbi tíz állításról, melyek meghatározott sorrendben követik egymást? Egyértelműen meghatározható-e, hogy melyek az igaz és hamis állítások?

1. Minden igaz állítás mellett van egy hamis állítás (alatta vagy fölötte).
2. Minden hamis állítás mellett van egy igaz állítás (alatta vagy fölötte).
3. Van két igaz állítás közvetlenül egymás mellett.
4. Van két hamis állítás közvetlenül egymás mellett.
5. Sehol nincs három igaz állítás közvetlenül egymás mellett.
6. Sehol nincs három hamis állítás közvetlenül egymás mellett.
7. Az igaz állítások száma prímszám.
8. A hamis állítások száma prímszám.
9. Több igaz állítás szerepel itt, mint hamis.
10. Több hamis állítás szerepel itt, mint igaz.

Egyértelmű a megoldás

Dévai Gergely megoldónk gondolatmente alapján meg fogjuk mutatni, hogy létezik konzisztens megoldás, mégpedig egyetlen egy, ami szerint a mondatok igazságértéke rendre: H, H, I, I, H, I, I, I, H, H, ahol I az igaz, H a hamis.

Tegyük fel, hogy az 1. állítás igaz. Ha az 1. állítás igaz lenne, akkor önmagára vonatkozóan ebből következne, hogy a 2. állításnak hamisnak kéne lennie. A 2. állítás hamissága azonban azt jelentené, hogy van olyan hamis állítás, ami mellett csak hamis állítás van. Ezesetben vagy hamis az utolsó két állítás, vagy van valahol három hamis állítás egymás után. Ha az utolsó két állítás hamis, abból következne, hogy az igaz és hamis állítások száma megegyezik, azaz pontosan öt igaz és 5 hamis állításnak kellene lennie. Viszont az 5 prímszám, tehát a 7. és 8. állítás igaz lenne, továbbá az eddigiek alapján a 3. és 4. is igaz lenne, tehát az 5. és 6. állításnak már szükségképpen hamisnak kéne lennie, de az 5. egy igaz állítás ebben a kiosztásban, tehát ellentmondásra jutottunk.

Ha nem az utolsó két állítás hamis, hanem van valahol korábban három egymást követő hamis állítás, akkor a 6. állítás biztosan hamis, mert az épp az ellenkezőjét állítja. Az 5. állítás pedig biztosan igaz, mert ha hamis lenne, vagyis lenne három igaz állítás egymás után, akkor az ellentmondana az 1. állításnak. Mármost a 7. nem lehet hamis, mert akkor a 6. és 7. két egymás mellett lévő hamis lenne, ami miatt a 4. állítás igaz lenne, de akkor az egymás melletti 4. és 5. igaz állítás miatt már a 3. állításnak is igaznak kellene lennie, márpedig az 5. állítás miatt nem lehet három igaz egymás mellett. Tehát a 7. állításnak igaznak kellene lennie. Ekkor viszont 3 egymást követő hamis állítás csak a 2., 3. és 4. állítás lehet, vagy a 8., 9. és 10. állítás. Az előbbi viszont azért nem jó, mert az ellentmondásba kerülne a 4. állítással, az utóbbi pedig azért nem jó, mert abból szintén következne, hogy a 4. állításnak igaznak kell lennie, majd abból, hogy a 3. állítás is igaz, ami szintén oda vezet, hogy a 3., 4. és 5. állítás három egymást követő igaz állítás, ami ellentmond az 5. állításnak.

Ez tehát azt jelenti, hogy az 1. állítás nem lehet igaz, ahogy azt a legelején feltettük, mert minden esetben ellentmondásra jutottunk. Tehát van olyan igaz állítás, ami mellett csak igaz van. Mivel az utolsó két állítás nem lehet egyszerre igaz, ezért biztosan kell legyen valahol három egymást követő igaz állítás. Ebből viszont rögtön következik, hogy a 3. állítás igaz, az 5. állítás pedig hamis. A 4. állítás ekkor nem lehet hamis, mert akkor a 4. és 5. két egymás utáni hamis lenne, ami a 4. állításnak ellentmondana. A 4. tehát igaz.

Nézzük lehet-e a 2. is igaz állítás? Ha a 2. igaz, akkor a 6. is igaz kell legyen, mert ha lenne három egymás utáni hamis állítás, akkor a középső miatt a 2. álltás nem lehetne igaz. Ezen kívül ugyancsak a 2. állítás miatt az utolsó két állítás nem lehet hamis, de mindkettő igaz se lehet, tehát egyik igaz, a másik hamis. Ebből az is következik, hogy van már legalább öt igaz és legalább három hamis állításunk, az igaz és hamis állítások elosztása tehát 5-5, 6-4, vagy 7-3. Ekkor viszont a 7. és 8. állítások egyszerre igazak vagy hamisak. Ha mindkettő hamis, akkor az eloszlásnak 5-5-nek kellene lennie, de az nem lehet, mert az utolsó két állítás nem lehet egyszerre hamis a 2. állítás miatt. Ha viszont a 7. és 8. állítás is igaz, akkor a 4. állítás nem fog teljesülni, márpedig korábban megállapítottuk, hogy annak igaznak kellene lennie.

Azt kaptuk tehát, hogy abban az esetben, ha van megoldás, akkor a 2. állításnak hamisnak kell lennie. Nézzük ezt az esetet. Amit tehát idáig tudunk, hogy az 1., 2. és 5. állítás hamis, a 3. és 4. állítás pedig igaz. Mivel tudjuk hogy van még valahol három igaz állítás egymás után, ami csak az utolsó öt állításban lehet, és azt is tudjuk, hogy az utolsó kettő nem lehet egyszerre igaz, ezért a 7. és 8. állítás biztos igaz, mert azoknak bele kell esniük ebbe a háromba. Ekkor viszont már csak úgy lehet az igaz és hamis állítások száma is prímszám, ha mindkettőből öt van, akkor viszont az utolsó két állítás hamis, a 6. állításnak pedig igaznak kell lennie. Ezután persze még hátra van, hogy minden állítást ellenőrizzünk, de azt kapjuk, hogy az általunk talált egyetlen lehetséges megoldás jó, azaz minden állítás az igazságértékének megfelelő, ha az igazságértékek rendre: H, H, I, I, H, I, I, I, H, H.

Bónusz kérdésünk az volt, hogy a fenti állításokat az összes lehetséges módon összekeverve hány olyan sorrend van, amelynél minden állításról pontosan meghatározható, hogy igaz-e vagy hamis? A tíz állítás összes lehetséges felírási sorrendje 10! = 3628800, ezekből 1037664 esetében nincs megoldás, azaz paradox rendszer, 1625536 esetében van egyértelmű megoldás, ahogy a kitűzött példában is, minden más esetben nem egyértelmű a megoldás, azaz van legalább egy olyan mondat, ami lehet igaz is és hamis is, de nem eldönthető. Érdekesség még, hogy a legkevésbé egyértelmű esetekben is maximum hat különböző megoldás, azaz igazságérték kiosztás lehetséges.

A legértékesebb megoldást beküldő versenyzők megtalálhatók a Dicsőségfalon!

Kapcsolódó cikk a Qubiten: