Bűvös kockák

A fejtörő pontverseny következő feladványa egy bűvésztrükk. A bűvész szemét bekötik, majd az egyik néző dob négy darab szabályos dobókockával. A bűvész segédje az egyik maga által kiválasztott kockát félretolja, majd a másik három dobás értékét az ugyancsak maga által választott sorrendben közli a bűvésszel, aki ezek után a félretolt negyedik kockadobás eredményét megnevezi. A segéd a bűvész állandó partnere, így korábban megállapodhattak valamiben, de a leírtakon kívül más információt nem kap a bűvész (hangsúly, időközök, minden egyforma). Mit beszélt meg a bűvész a segédjével?

Plusz pontért be lehet bizonyítani, hogy kevesebb kockával nem működik a trükk, azaz két kockával a harmadik nem jósolható biztosan. Vagy azt, hogy minimálisan hány "dobókocka" kell, ha "kockák" helyett tetszőleges K-oldalú dobó testeket használnak a trükkhöz, amely bármelyik oldalára 1/K valószínűséggel esik. Ennél a kérdésnél az is elegendő, ha egy algoritmust tud adni valaki általánosan, nem kell konkrétan kiszámolni zárt alakban. Persze azt is értékelem, ha valamely konkrét K értékre tud valaki megoldást. Még érdekesebb az a kérdés, hogy minimálisan hány N darab 6-oldalú kockával lehet megcsinálni a trükköt, ha nem egy, hanem M darab (a segéd által kiválasztott) kockadobás értékét szeretnénk megmondani a maradék N-M dobás alapján, amiket a segéd rendezhet sorba. Ha valaki az M=2 esetet megoldja 6-oldalú kockákkal, akkor nagy valószínűséggel megkapja a maximális plusz pontot a duplapluszkreatív pontversenyben.

A beküldési határidő március idusa. Az oldalsávon felül található e-mail címre kell küldeni a megoldásokat és a tárgy mezőbe kérlek írjátok be, hogy 3. feladvány, vagy bűvös kockák. Az előző két feladvány megoldásai és a pontverseny állása hamarosan elérhetőek lesznek. Az előző feladvány megoldása is beküldhető még ma éjfélig!

Paradox lottókombináció (megoldás)

Annipanni ezen a héten két szelvénnyel játszik a hatoslottón. Van egy szerencseszáma, amit mind a két szelvényén bejelöl, a többi száma viszont mind különböző. Minek van nagyobb esélye: annak, hogy lesz két hármas találata, ami előző héten például 2 x 1185 = 2370 forintot fizetett volna, vagy annak hogy lesz egy hármas és egy négyes találata, ami előző héten 1185 + 5595 = 6780 forintot ért volna?

Még tavaly áprilisban tűztem ki a paradox lottókombináció című feladványt, de sajnos a meghosszabított beküldési határidő ellenére sem érkezett egyetlen megoldás se azóta. A fenti rávezető feladatban konkrétan megadok egy olyan paradox lottókombinációt, amiről az eredeti feladatban szó volt. Ennek az átfogalmazott feladatnak a megoldását közlöm az alábbiakban, így aki szeretné saját maga kiszámolni, az ne olvassa tovább ezt a bejegyzést.

Megoldás: Természetesnek tűnik, hogy egy hármas és egy négyes találatnak kisebb legyen az esélye a két hármas találatnál, hiszen az előbbinek nagyobb a nyeremény értéke (6780 > 2370), azaz többet fizetnek érte, és azt várnánk, hogy minél nagyobb a találatokhoz tartozó nyereményösszeg, annál nehezebb eltalálni. A feladatban szereplő korlátozó tényezők mellett azonban az az érdekesség adódik, hogy a kétféle nyerő kombinációnak éppen azonos a valószínűsége. Ez azért lehetséges, mert jelentős megszorítást jelent, hogy két szelvényen is találatunk legyen, vagyis a szelvényeken elért találatok egymástól nem teljesen függetlenek. Konkrétan két hármas találatot úgy érhetünk el, ha kihúzzák a szerencseszámot, és még két-két számot mindkét szelvény maradék öt számából, ami (5 alatt a 2)*(5 alatt a 2) = 10*10 = 100 kombináció, vagy úgy, ha nem húzzák ki a szerencseszámot, de kihúznak három-három számot mindkét szelvény maradék öt számából, ami (5 alatt a 3)*(5 alatt a 3) = 10*10 = 100 lehetőség ugyancsak. Összesen tehát 200 kombinációban jöhet ki két hármas találat. Négyes találat azonban egy hármas találat melett csak úgy lehetséges, ha kijön a szerencseszám, mert a két szelvényen lennie kell közös találatnak, hiszen csak hat számot húznak. Tehát a szelvények maradék öt-öt számából 3-2 vagy 2-3 kell legyen a találati arány, ezek mindegyike megintcsak 10*10 = 100 lehetőség egyenként, mert öt alatt a kettő éppen annyi, mint öt alatt a három. Összesen tehát ez is 200 kombináció.

Update: Sajnos a fenti megoldás rossz, elnéztem, lásd Gyarmati Richárd megjegyzését a hozzászólások között!

Shannon száma

Claude Elwood Shannon (1916-2001) amerikai elektromérnök, híradástechnikus, matematikus és kriptográfus, az információelmélet alapító atyja. Ismertségét leginkább ez utóbbinak köszönheti, hiszen a róla elnevezett Shannon-féle entrópia az információelmélet központi fogalma, az információ mérésére bevezetett mennyiség, amely számos tudományterületet forradalmasított, az információelmélet eredményeit pedig megannyi műszaki megoldás felhasználja. Kevésbé ismert azonban az, hogy lényegében Shannon az atyja a számítógépes sakkozásnak is. 1949-ben írta meg úttörő cikkét arról, hogy mi az elméleti alapja egy számítógépes sakkprogram működésének. De műszaki ember lévén ő maga is épített kezdetleges sakkgépet, amint az az alábbi ábrán is látható Emanuel Lasker matematikus, filozófus és sakkvilágbajnok társaságában, aki egyébként rekord hosszúságú 27 éven keresztül tudta 1894 és 1921 között megvédeni világbajnoki címét.

Az kezdetek óta készült sakkprogramoknak lényegében mindegyike a Shannon által vázolt megoldásra épít, a mai sakkprogramok pedig már képesek túlszárnyalni a világbajnoki szintet is. Minden ilyen algoritmus őse az ún. minimax keresés, ami lényegében nagyon egyszerű. A sakkjáték leírható egy fa jellegű gráffal, aminek a csúcsai sakkállások, az irányított élek pedig a lehetséges lépések, amik egyik állapotból a másikba vezetik a játék fonalát. Egy állapothoz hozzá tartozik az is, hogy a sötét vagy a világos játékos következik. Ez az irányított fa a játék kezdő állapotából kiindulva leírja, hogy mik a lehetséges lépés sorozatok. Nyilvánvalóan minden játékosnak azt a lépést érdemes választania, ami az ellenfél legjobb válaszlépése esetén is a legkedvezőbb számára. Ha mindkét játékos ismerné ezt a hatalmas gráfot, és át tudnák tekinteni az összes lehetséges bejárást, akkor mindegyikük eldönthetné minden egyes állásról, hogy az nyerő, vesztő, vagy esetleg döntetlenre jönne ki az ellenfél optimális lépéseit figyelembe véve. Tulajdonképpen elvileg lehetséges, hogy a sakk esetében létezik nem vesztő stratégia, vagyis a kezdő állapot tulajdonképpen döntetlent ér.

A gyakorlatban azonban az említett fa gráfot nem lehet áttekinteni csak néhány lépés mélységig, akár emberről, akár gépről legyen szó, mert a gráf lényegében csillagászati méretű. Ebből kifolyólag az állásokat sem lehet értékelni egyértelműen, csak valamilyen heurisztika alapján, például figyelembe véve a bábuk pontértékét, a gyalogállást, és egyéb tényezőket, amiket tipikusan nagymesterek segítenek megállapítani, vagy játszmák alapján tanulják a programok. Ha azonban valamilyen közelítő értékelést tudunk adni a sakkállásokra, akkor a minimax keresés lesz az, amely valamilyen mélységig a legjobb lépéskombinációt megtalálja valamely játékos számára. Az elnevezés onnan jön, hogy az egyik játékos szempontjából az állásokra adott értékelést felváltva akarják maximalizálni illetve minimalizálni a játékosok, tekintettel arra, hogy felváltva lépnek. Az algoritmus roppant egyszerű, azonban a futási ideje a fa mélységével, azaz a lépések számával exponenciálisan növekszik. A Kaszparovot legyőző Deep Blue például átlagosan hat lépéspárt tekintett előre, míg a mai legjobb Hydra nevezetű gépi sakkozó kilenc lépéspárig tekint előre átlagosan. Sannonról egyébként egy trófeát is elneveztek, amit a sakkprogramok világbajnokságán a nyertes program tervezői kapnak. Ez látszik az alábbi képen, amint azt a Deep Blue elődjének a Deep Tought-nak a tervezője vesz át Shannontól 1989-ben.

De mégis mekkora az a csillagászati szám, amiről beszélünk? Shannon adott erre egy becslést az említett cikkben, amiben azt tekintette, hogy hányféle képpen lehet a táblára helyezni az alap sakkbábu készletet, vagyis azt, amivel a játék elején rendelkeznek az ellenfelek. Ezt nevezik Shannon-féle számnak. Ez természetesen lehet több is és kevesebb is, mint a játék során előforduló valódi sakkálások száma. Egyrészt nem minden állás állhat elő szabályos játék során. Például a gyalogok nem mehetnek hátrafele, vagy nem lehetnek a királyok egyszerre sakkban. Másrészt a gyalogokat más bábukra lehet cserélni, ha elérik a szemközti alapvonalat, ez pedig növeli a lehetőségek számát. Ha azonban nagyságrendi becslést szeretnénk, akkor a Shannon-féle szám egy jó kiindulópont. Hogyan lehet tehát kiszámolni?

Ehhez érdemes tudni, hogy egy n elemű halmazból hányféle képpen lehet kiválasztani k elemet úgy, hogy a sorrendjük nem számít. Matematikusok ezt úgy mondják, hogy "n alatt a k", és úgy is jelölik, hogy zárójelbe téve n alá írják a k számot. Érdemes még azt is tudni, hogy 1-től n-ig összeszorozva a számokat, a kapott számot úgy mondják, hogy n faktoriális, és n! a jelölése, a matematikusok így rövidítik ezt a szorzatot. Faktoriálisokkal n alatt a k könnyen kifejezhető. Ha n elemből k elemet akarunk kiválasztani úgy, hogy számít a sorrend, akkor az első elemet n féle képpen választhatjuk, a másodikat (n-1) féle képpen, és így tovább, míg a k. elemet (n-k-1) féle képpen. Az összes lehetőségek számát tehát megkapjuk, ha ezeket összeszorozzuk, ami n!/(n-k)! lesz. Ha viszont a sorrend nem számít, akkor ezt le kell osztani annyival, ahány féle képpen k elemet sorba rendezhetünk, hiszen mindent ennyiszer számoltunk, ebben az esetben k! darabszor. Végeredményben tehát az alábbi képletet kapjuk.

Ezt felhasználva Shannon számát mostmár ki tudjuk számolni. Először ki kell választani, hogy hova tesszük a 32 sakkfigurát a 64 mezőből álló sakktáblán, ami 64 alatt a 32 lehetőség. Aztán ki kell választani, hogy a 32 helyből melyik 16-ra tesszük mondjuk a világos bábukat, ami 32 alatt a 16 lehetőség. Aztán ki kell választani, hogy a sötét és a világos bábuk közül melyik a 8 gyalog, ami 16 alatt a 8 lehetőség mindkét játékosnál. Aztán ki kell választani a maradék 8 helyből mindkét játékos esetén, hogy hova kerülnek a bástyák, ami 8 alatt a 2 lehetőség mindkét esetben. Aztán ki kell választani mondjuk a huszárokat a maradék 6-6 helyből, ami 6 alatt a 2 mindkét játékosnál. Aztán a futókat, ami 4 alatt a 2 mindkét játékosnál. Vegyük észre, hogy a sakkban szokás a mezők színe szerint fehér és fekete futókról is beszélni, de mi itt most ezt a megkülönböztetést nem tesszük meg. Legvégül azt kell eldönteni mindkét játékos bábuinál, hogy a maradék 2 helyből melyiken van a király és melyiken a királynő, ami kétszer két lehetőség összesen. Mindent összetéve és az egyszerűsítéseket elvégezve az alábbi képlet adódik, ami durván 10^43, vagyis az 1-est 43 darab nulla követi. Ez azt jelenti, ha nanoszekundumonként vizsgálnánk meg egy állást, akkor is 10^34 másodpercig, azaz 10^26 évig tartana az összes lehetséges állás végignézése, ami az Univerzum életkorának is rengetegszerese!