Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

7. TOTÓ és kódok

7. TOTÓ és kódok

A kódelméletből tanultakat a népszerű TOTÓ játékban is hasznosíthatjuk. A TOTÓ-ban 13 focimeccs eredményét kell eltaláljuk (az egyszerűség kedvéért a „ + 1 ” mérkőzésről feledkezzünk meg). Minden meccsnek három kimenetele lehet, 1,2 vagy X. Az eddigiek szerint ezt a modulo 3 maradékokkal azonosíthatjuk, azaz pl. X helyett 0-t írunk. Ha biztos 13 találatra törünk, akkor persze 3 13 szelvényt kell kitöltenünk. A gyakorlatban az a helyzet, hogy bizonyos meccsek eredményét a tippelő tudni véli, más meccseknél kizárja pl. a vendégcsapat győzelmét. A kérdés az, hogy ha ilyen jellegű várakozásai bejönnek, akkor hogyan kell úgy kitöltenie a szelvényeket, hogy biztosan legyen olyan szelvénye, amely legalább 12 találatos. A „sárga újság”-ban (a Sportfogadás c. lapban) számtalan ilyen TOTÓ-kulcsot találhatunk. Érdekességként megemlítjük, hogy az 6.1 Tételben szereplő egyik Golay-kódot ( Q = 3 , n = 11 , e = 2 ) egy finn TOTÓ-magazinban a matematikai megjelenésnél két évvel korábban, 1947-ben közölték. A TOTÓ-val kapcsolatos kérdésekben alapvető referenciánk az [5] dolgozat. Ennél a cikknél is többet tudhatunk meg a [3] könyvből.

Ezután nézzük, hogyan hozható kapcsolatba a TOTÓ a korábbi modellünkkel. A kitöltött TOTÓ-szelvények tehát bizonyos n = 13 hosszú vektorok a modulo 3 maradékosztálytest felett, ezek halmazát jelölje S . Ha 13 - r találatot szeretnénk elérni, akkor az kell, hogy minden n hosszú vektorhoz legyen olyan S -beli, amely tőle legfeljebb r Hamming távolságra van. Más szóval, az S elemei köré írt r sugarú gömbök le kell fedjék a teljes Q n halmazt, azaz 3 n elemet. Ha r = 1 , akkor a gömb pontosan 2 n + 1 elemű, azaz

S ? 3 n / ( 2 n + 1 ) .

Az r //>// 1 esetben az r sugarú Hamming gömbben található pontok száma ? i = 0 r n i 2 i , így ilyenkor az

S ? 3 n / ? i = 0 r n i 2 i

(10)

becslés érvényes. Korábban a Hamming-korlát igazolásakor a gömbök diszjunktak voltak, most le kell fedniük a Q n teret. Ennek megfelelően mind a becslések, mind a bizonyítások azonosak a korábban leírtakkal, csak az egyenlőtlenségek iránya változik az ellenkezőjére.

A bináris esethez hasonlóan lássuk az r = 1 esetet. Tekintsük a modulo 3 test feletti 13 hosszú Hamming-kódot. Ennek leírását kényelmi okokból most megismételjük. A bináris esethez hasonlóan egy 3 sorból álló mátrixot definiálunk, ahol az oszlopok bizonyos 1 , , 3 3 - 1 számok hármas számrendszerbeli alakjai. Ezen 26 szám közül csak 13-nak szerepel a felírása, mégpedig azoké, amelyekben fentről lefelé az első nem nulla számjegy 1-es. Tehát pl. 1 felírása szerepel, 2-é nem, 13 felírása szerepel, 26-é nem. Mivel az első nem nulla jegy kétféle lehet, így valóban a számok felét kapjuk meg. A konkrét mátrix a

H = 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 2 2 2 1 0 1 2 0 1 2 0 1 2 0 1 2

lehet. A bináris esethez hasonlóan igazolhatjuk, hogy a H mátrix sorai által felírt három egyenletből álló lineáris egyenletrendszernek 3 10 megoldása van, és két megoldásnak a Hamming távolsága legalább 3. Ez azt jelenti, hogy ki lehet 3 10 szelvényt úgy tölteni, hogy mindenképp legyen 12 vagy 13 találatunk.

Kevesebb szelvény kitöltése esetén előző becsléseink szerint lesz olyan végeredmény, amelynek esetén egyik szelvényünk se lesz 12 vagy 13 találatos. Az 5. a) feladat végeredménye tehát 3 10 = 59 049 .

Az [5] cikkben részletes táblázatot találunk legfeljebb 1, 2 és 3 meccs eredményét elrontó TOTÓ-kulcsokra. Meglepően keveset lehet tudni az r //>// 1 esetben. Ha például a 13 mérkőzéses totón legalább 11 találatot szeretnénk elérni ( r = 2 ), akkor csak az ismeretes, hogy 5062 szelvényre biztosan szükség van, és találtak példát 6561 olyan szelvényre, amely garantálja a kívánt eredményt. Ugyanennyi mérkőzés, de 10 megkövetelt találat esetén arányaiban még rosszabb a helyzet, csak annyit lehet tudni, hogy 609 és 1215 között van az optimális megoldás. Bosszantó, de sok ennél kisebb esetben sem ismert az igazság: az 1995-ben megjelent [5] cikk szerint például még az sem ismert, hogy hány szelvény kell a 6 mérkőzéses totón a biztos 5 találathoz. Ezek közül „kilóg” egy viszonylag nagy ( n = 11 , r = 2 ) biztos eredmény, amely a következő fejezetben tárgyalt Golay-kódhoz kapcsolódik.

Természetesen a valóságos TOTÓ-kulcsokban bizonyos meccseknél valamelyik eredmény „kizárható”, azaz mondjuk n 2 mérkőzésnél csak két esélyt, n 1 mérkőzésnél 3 esélyt játszunk meg. Az [5] cikkben az n 1 + n 2 ? 13 esetre találunk a vegyes TOTÓ-kulcsok esetén szükséges szelvények számát megadó táblázatot. Az erre az esetre érvényes

S ? 2 n 2 3 n 1 ? j = 0 r ? i = 0 j n 2 i n 1 j - i 2 j - i

(11)

becslés igazolásával az Olvasó is sikerrel próbálkozhat.