Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

2. A BARKOCHBA JÁTÉK ÉS AZ INFORMÁCIÓ MÉRÉSE

2. A BARKOCHBA JÁTÉK ÉS AZ INFORMÁCIÓ MÉRÉSE

A Barkochba játéknál az egyik játékos – nevezzük a „felelő”-nek – gondol valamire (vagy valakire), a másodiknak – őt nevezzük „kérdező”-nek – ki kell találnia, hogy a „felelő” mire gondolt; ecélból tetszőleges, igennel vagy nemmel megválaszolható kérdéseket tehet fel, amelyekre a „felelő”-nek legjobb tudása szerint, az igazságnak megfelelően kell válaszolnia. E válaszokból kell a „kérdező”-nek kitalálnia, hogy mire gondolt a „felelő”. Akik gyakran játsszák e játékot, általában megállapodnak abban, hogy mire lehet gondolni. Akinek van gyakorlata, tudja, hogy viszonylag könnyen kitalálható élő vagy történelmi személyek neve (feltéve, hogy a „kérdező” tud arról a személyről, akire a „felelő” gondolt). Pl. ha Pascalra gondolt az első játékos, a kérdezés mehet a következőképpen:

Személy?Igen
Él?Nem
Művész?Nem
Tudós?Igen
1900 után született? Nem
1700 után született? Nem
1600 után született? Igen
Angol vagy olasz? Nem
Német vagy Holland? Nem
Francia? Igen
Matematikus? Igen
Filozófus is volt? Igen
Janzenista volt? Igen

Ezek után a második játékos már közölheti, hogy kitalálta, hogy Pascalról van szó. Látszik a kérdésekből, hogy amikor a kérdező odáig eljutott, hogy egy francia matematikusról van szó a XVII. században, megfordult fejében Pascal, Descartes, Desargues, Fermat neve; a két utóbbit kizárta azzal a kérdéssel, hogy filozófus is volt-e, míg Descartes-ot az utolsó kérdéssel zárta ki, úgyhogy ezek után szinte biztosra vehette, hogy Pascalról van szó.

Mármost vizsgáljuk meg azt, hogy általában hány kérdéssel lehet valamit a Barkochba játékban kitalálni. Az, hogy hány kérdéssel sikerül kitalálni a gondolt dolgot, persze függ a kérdező gyakorlatától, műveltségétől, fantáziájától, pszichológiai érzékétől, sőt bizonyos mértékben a véletlentől is, de döntő mértékben mégis attól függ, hogy milyen tág azoknak a dolgoknak a köre, amelyekre a játékosok megállapodása szerint gondolni lehet. Ha például szabad olyasmire gondolni, mint „az a jelző, amivel a New York Times tudósítója jellemezné Cleopatra ruháját, ha Cleopatra feltámadna és mint egyiptomi államfő megjelenne az ENSZ-ben”, a kérdezőnek nyilván jóval több kérdésre van szüksége, és nemcsak a kérdezés, de a kérdések helyes megválaszolása sem egyszerű. Ahhoz, hogy választ kapjunk arra, hogy hány kérdéssel lehet valamit kitalálni, próbáljuk egyszerűsíteni a problémát azáltal, hogy kikötjük, hogy a „felelő” csak egy hatjegyű számra gondolhat. (6-nál kevesebb jegyű számokat is megengedünk, mert 0-k eléírásával ezek 6 jegyűvé tehetők; pl. 313=000 313

313 = 000 313 .)

Ebben az esetben azoknak a dolgoknak a száma, amelyekre gondolhat a „felelő”, 1 000 000

1 000 000 . Könnyen belátható, hogy első kérdésként célszerű pl. azt a kérdést feltenni: a gondolt hatjegyű szám kisebb-e, mint 500 000 500 000 ? Ez esetben ugyanis akár igen a válasz, akár nem, az első kérdésre kapott válasz után a még számba jövő lehetőségek száma 500 000 500 000 -re csökken. (Ha a válasz „igen”, a szám 000 000 000 000 és 499 999 499 999 között kell, hogy legyen, míg, ha a válasz „nem”, a szám 500 000 500 000 és 999 999 999 999 között kell, hogy legyen.) Persze azt is kérdezhetjük, hogy a szám legalább 500 000 500 000 -e; ez tulajdonképpen ugyanaz a kérdés másképp megfogalmazva. Hasonlóképpen kérdezhetjük, hogy a szám páros-e, ill. bármilyen más olyan kérdést feltehetünk, amelyre 500 000 500 000 hatjegyű szám esetében „igen” és a többi 500 000 500 000 hatjegyű szám esetében „nem” a válasz. Könnyű belátni azonban, hogy csak ezek a célszerű kérdések, mert ha olyan kérdést teszünk fel, amelyre 500 000 500 000 -nél több szám esetében „igen” a válasz, úgy, ha igenlő választ kapunk, kedvezőtlenebb helyzetben vagyunk, mint pl. ha azt kérdeztük volna, hogy páros-e a gondolt szám. Ha viszont olyan kérdést teszünk fel, amelyre 500 000 500 000 -nél kevesebb szám esetében „igen” a válasz, nemleges válasz esetében kerülünk kedvezőtlenebb helyzetbe. Hasonlóképpen a második kérdéssel a számításba jövő számok számát megint meg tudjuk felezni, azaz le tudjuk szállítani 250 000 250 000 -re a harmadik kérdéssel 125 000 125 000 -re, a negyedikkel 62 500 62 500 -ra, az ötödikkel 31 250 31 250 -re, a hatodikkal 15 625 15 625 -re. Mivel 15 625 15 625 páratlan szám, ennyi lehetőséget nem lehet két egyenlő részre bontani, hanem csak úgy, hogy az egyik válasz esetén 7813, a másiknál 7812 lehetőség maradjon nyitva. Így jól választott hetedik kérdés után a fennmaradó lehetőségek száma legfeljebb 7813, a nyolcadik után hasonlóképpen 3907, a kilencedik után 1954, a tizedik után 977, a tizenegyedik után 489, a tizenkettedik után 245, a tizenharmadik után 123, a tizennegyedik után 62, a tizenötödik után 31, a tizenhatodik után 16, a tizenhetedik után 8, a tizennyolcadik után legfeljebb 4, a tizenkilencedik után legfeljebb 2. Így tehát – ha előbb nem – a huszadik kérdésre biztosan kitalálhatjuk a gondolt számot. Ha meggondoljuk, hogy miért éppen 20 kérdés adódott, könnyű észrevenni, hogy ez azon múlott, hogy

2^(19)=524 288l1 000 000l1 048 576=2^(20).
2 19 = 524 288 l 1 000 000 l 1 048 576 = 2 20 .

Ebből az is látszik, hogy 20 kérdéssel nemcsak 1 000 000

1 000 000 közül lehet kitalálni a gondolt dolgot, hanem még 1 048 576 1 048 576 közül is, de már ha 1 048 577 1 048 577 dologra szabad gondolni, akkor 20 kérdés nem biztos, hogy elég a kitalálásra.[31] Ugyanis minden egyes kérdéssel felére tudjuk csökkenteni a még számításba jövő lehetőségek számát; így tehát ha eredetileg 2^(20) 2 20 dolog jött tekintetbe, k k kérdésre kapott válasz után a még megmaradó lehetőségek száma már csak 2^(20–k) 2 20 k lesz és így 20 kérdés után – mivel 2^0=1 2 0 = 1 – már csak egyetlen lehetőség marad. Könnyű belátni, hogy ha a lehetőségek száma eredetileg pontosan 2^(20) 2 20 volt, és az ismertetett kérdezésmódot alkalmazzuk, akkor a gondolt dolgot mindig pontosan a 20-ik kérdésre fogjuk kitalálni, és sohasem előbb. Persze ez a kérdezésmód teljesen gépies, és ezáltal a játék érdektelenné válik; az említett kérdezési módszerrel egy számítógép is tud Barkochbát játszani.

Az elmondottakból az is következik, hogy ha N

N -féle dologra szabad gondolni, a gondolt dolgot mindig ki lehet találni K K kérdéssel, ahol K K a legkisebb egész szám, amelyre 2^K≥N 2 K N , tehát K K a legkisebb egész szám, amelyre K≥log_2N K log 2 N .[32]

Az eddig elmondottakból úgy tűnik, mintha minden egyes kérdés megfogalmazása az előző kérdésekre kapott választól kellene, hogy függjön. Ez azonban nincs így. Ha nem számít az, hogy a kérdés minél egyszerűbben legyen megfogalmazható, meg lehet a kérdéseket előre adni úgy, hogy a válaszokat a kérdező csak az összes kérdés feltevése után kapja meg. Például, ha csak a 0, 1, 2, 3, 4, 5, 6, 7 számok valamelyikére szabad gondolni, egy lehetséges optimális kérdésrendszer (amely persze 3 kérdésből áll, mivel 8=2^3

8 = 2 3 ) a következő:

1. kérdés: A gondolt szám az 1 2 3 4

1 2 3 4 számok egyike?

2. kérdés: A gondolt szám az 1 2 5 6

1 2 5 6 számok egyike?

3. kérdés: A gondolt szám az 1 3 5 7

1 3 5 7 számok egyike?

E 3 kérdésre kapott válaszból a gondolt szám egyértelműen kitalálható a következőképpen:

Ha a válaszok a 3 kérdésre
a fenti sorrendben akkor a gondolt szám
igen igen igen 1
igen igen nem 2
igen nem igen 3
igen nem nem 4
nem igen igen 5
nem igen nem 6
nem nem igen 7
nem nem nem 0

E kérdezési rendszer lényegét még jobban megvilágítja a következő megjegyzés. Tegyük fel, hogy az első 2^N

2 N nem negatív egész számra lehet gondolni. E számokat állítsuk elő a kettes számrendszerben; könnyen beláthatjuk, hogy a 0, 1, …, 2^N–1 2 N 1 számok mindegyike a 2-es számrendszerben egy pontosan N N jegyből álló számként állítható elő, ha megengedjük, hogy egy szám előállítása zérussal, ill. zérusokkal is kezdődhet. Pl. ha N=3 N = 3 , az első nyolc szám előállítása:

0 = 000 4 = 100 1 = 001 5 = 101 2 = 010 6 = 110 3 = 011 7 = 111
0 = 000 4 = 100 1 = 001 5 = 101 2 = 010 6 = 110 3 = 011 7 = 111

Mármost, ha a „felelő” csak a 0, 1, 2, …, 7 számok valamelyikére gondolhat, a gondolt számot egyszerűen kitalálhatjuk a következő 3 kérdéssel:

  1. A gondolt számot a 2-es számrendszerben 3 jegyű számként felírva az első jegy 0-e?

  2. A gondolt számot a 2-es számrendszerben 3 jegyű számként felírva a második jegy 0-e?

  3. A gondolt számot a 2-es számrendszerben 3 jegyű számként felírva a harmadik jegy 0-e?

Ha pl. a 3 kérdésre a válaszok: igen–nem–nem, akkor a gondolt szám a 2-es számrendszerben felírva 011, tehát a szám 3.

Mármost állapodjunk meg abban, hogy a gondolt szám, ill. dolog kitalálásához szükséges információ mennyiségén a kitaláláshoz szükséges kérdések számát értjük, feltéve, hogy a lehető legjobb kérdezési rendszert használjuk. Ez azt jelenti, hogy az információ egységének az egyetlen egy igen–nem válaszban foglalt információt választjuk. Az információ egységét bit-nek nevezzük.[33]

Így tehát pl. ha valaki elkészíti a keresztnevek egy listáját, amely 512 keresztnevet tartalmaz,[34] és a játékosok megállapodnak abban, hogy csak e listában szereplő keresztnévre szabad gondolni, úgy, mivel 512=2^9

512 = 2 9 , a gondolt keresztnév kitalálásához 9 bit információra van szükség, és – mivel egy kérdésre kapott válasz legfeljebb egy bitet tartalmazhat – tehát legalább 9 kérdés kell a gondolt keresztnév kitalálásához. A mondottakhoz azok megvilágítására néhány megjegyzést fűzünk.

  1. megjegyzés. Az előbb azt mondottuk, hogy egy igen–nem válasz legfeljebb egy bit információt tartalmaz. Valóban, ha pl. az előző példában az első kérdést úgy tesszük fel, hogy nem 256, hanem kevesebb esetben igenlő a válasz, akkor nemleges válasz esetén még 256-nál több lehetőség maradt; ez esetben a válasz 1 bitnél kevesebb információt nyújtott.

  2. megjegyzés. Ahhoz, hogy valóban 9 kérdéssel ki tudjuk találni, hogy az 512 keresztnév közül a felelő melyikre gondolt, szükséges, de nem elégséges, hogy minden egyes kérdés 1 bit információt nyújtson, vagyis, hogy mindegyik kérdés olyan legyen, amelyre az 512 keresztnév közül pontosan 256 esetben igen és 256 esetben nem a válasz. Lehetséges ugyanis, hogy két kérdés külön-külön jó, de nem illenek össze: külön-külön ugyan mindegyikre a válasz egy bit információt tartalmaz, de a kérdésekre kapott válaszban foglalt információk részben vagy egészben fedik egymást, vagyis legalább részben ugyanazt az információt kapjuk meg kétszer. Kirívó példa erre, ha pl. az első kérdést másodszorra megismételjük; ez esetben a második kérdésre kapott válasz ugyanazt az 1 bit információt nyújtja, mint az első kérdésre adott válasz és így a két válasz – bár külön-külön mindegyik 1 bit információt tartalmaz – együtt nem 2 bit, hanem csak 1 bit információt nyújt. Hasonlóképpen pl. az előbb kétféle módon is megadtunk 3-3 kérdést, amelyekkel ki lehet biztosan találni, hogy a 0, 1, 2, 3, 4, 5, 6, 7 számok közül melyikre gondolt a „felelő”. Ha azonban az első kérdéssorozat első kérdése után (A gondolt szám az 1, 2, 3, 4 számok egyike-e?) a második kérdéssorozat első kérdését tesszük fel (A számot a kettes számrendszerben felírva az első jegy 0-e?), a két kérdésre kapott válasz együtt nem ad 2 bit információt. Ugyanis az első válaszból azt tudjuk meg, hogy a szám az 1, 2, 3, 4 számok között (vagy a 0, 5, 6, 7 számok között) van-e, a második válaszból viszont azt tudjuk meg, hogy a szám a 0, 1, 2, 3 számok között (vagy a 4, 5, 6, 7 számok között) van-e. Így tehát aszerint, hogy a két válasz hogyan hangzik, a még tekintetbe jövő számokat az alábbi táblázat tünteti fel:

    A gondolt szám az
    Ha a válaszok alábbi számok egyike
    igen, igen 1, 2, 3
    igen, nem 4
    nem, igen 0
    nem, nem 5, 6, 7

    Így tehát például abban az esetben, ha mindkét kérdésre igen a válasz, a még fennmaradó lehetőségek száma 3, és így további 2 kérdésre van szükség. Más szóval a második kérdés ugyan 1 bit információt tartalmazott, de ennek egy része[35] nem volt számunkra új információ, hanem olyan, amivel már rendelkeztünk. Ha viszont az első kérdéssorozat első kérdése után (A gondolt szám az 1, 2, 3, 4 számok között van-e?) a második kérdéssorozat második kérdését tesszük fel (tehát a második válaszból azt tudjuk meg, hogy a gondolt szám a 0, 1, 4, 5 számok között van-e?), akkor a még tekintetbe jövő számokat az alábbi táblázat mutatja:

    Ha a válaszok A még tekintetbe jövő számok
    igen, igen 1, 4
    igen, nem 2, 3
    nem, igen 0, 5
    nem, nem 6, 7

    Ebben az esetben tehát akármilyen válaszokat kaptunk is a két kérdésre, már csak 2 lehetőség marad nyitva és így a harmadik kérdésre biztosan kitalálhatjuk a gondolt számot. Tehát nemcsak az igaz, hogy a két válasz külön-külön egy-egy bit információt tartalmaz, hanem az is, hogy együtt 2 bit információt adnak, tehát a két válaszban foglalt információ még részben sem fedi egymást, a második kérdésre kapott válaszban foglalt információ teljes egészében új.



[31] Amerikában egyébként a Barkochba játék neve „húsz kérdés”, és ott úgy játsszák, hogy legfeljebb 20 kérdéssel kell kitalálni a gondolt dolgot.

[32] log_2N

log 2 N itt és a következőkben az N N szám 2 alapú logaritmusát jelenti.

[33] A „bit” szó az angol nyelvből származik és a binary digit (= kettes számrendszerbeli számjegy) rövidítése.

[34] A naptárban csak 437 keresztnév van felsorolva, azonban számos olyan keresztnév van, amelyhez nem tartozik névnap, pl. Györgyi, Romeo, Héraklész, Trisztán, Izolda stb.; némi fáradsággal a listát ki lehet egészíteni 512-re.

[35] Belátható, hogy a második kérdésre kapott válasz

(1/4)log_2(256/27)∼0,8
1 4 log 2 256 27 0,8

bit új információt és

(1/4)log_2(27/16)∼0,2
1 4 log 2 27 16 0,2

bit olyan információt ad, ami már az előző válaszban benne volt.