Becsöngettek, de okosteló nélkül!
Elérkezett a a szeptember, elkezdődött a tanév, és egy új kormányrendelet szerint a diákoknak a tanítási nap kezdetén le kell adniuk telekommunikációs eszközeiket, különös tekintettel az okostelefonjaikra. Ezzel kapcsolatos első őszi feladványunk, ami rögtön egy megoldandó technikai problémára mutat rá, nevezetesen arra, hogy a nagyon hasonló kinézetű okostelefonokat meg kell tudni valahogy különböztetni egymástól, vagy az iskoláknak több ezer különálló és zárható fakkot kell hirtelen üzembe állítaniuk, ami szintén nem egyszerű feladat, főleg így, az utolsó pillanatban.
Az egész mizéria ezzel párhuzamosan egy társadalmi vitát is gerjesztett arról, hogy kell-e, és ha igen, akkor milyen módon kell az okoseszközöket bevonni a modern oktatásba. Vannak iskolák, ahol az okoseszközök már eddig is teljesen tiltva voltak, miközben mások már a mesterséges intelligencia oktatásba integrálását szorgalmazzák. Egy biztos: számos tanár használja már a digitális eszközöket az oktatásban, és ezt a folyamatot persze a covid is gyorsította. Azokon a helyeken, ahol a tanári gárda már hatékonyan és érdekfeszítően be tudta építeni a digitális eszközök használatát az oktatásba, sok bonyodalmat okozhat majd, ha mondjuk tesióra előtt le kell adni a telefont, amit aztán nyelvóra előtt felvehetnek, hogy utána újra leadják, majd digitáliskultúra-óra előtt ismét felvegyék, és így tovább.
Az alábbi feladvány duplán is kötődik a digitális eszközökhöz. Egyrészt a témájában, másrészt azért, mert a megoldáshoz megengedett mindenféle program és kereső használata, amit most érdemes is kihasználni. A feladványt segítség nélkül is meg lehet oldani, de teljesen rendben van, ha valaki nem áll neki papíron kiszámolni, hanem inkább megkeresi a szükséges információkat hozzá a neten. Lássuk, kinek sikerül! Ha megvan a megoldás, akkor nézegessétek majd egy kicsit, mert elég meglepő.
209. feladvány: Összekevert mobilok
A felcsúti mészáros azzal sietett a helyi iskola segítségére, hogy névre szóló, ujjlenyomat-felismerős, zárható fakkokat adományozott minden diáknak, hogy abba a tanítási nap elején elhelyezhessék laptopjaikat, tabletjeiket, iPhone-jaikat és okosóráikat. A szállítmány azonban sajnos még nem érkezett meg, ezért az igazgató jobb híján elrendelte, hogy a diákok a tanterembe belépve egy zsákba dobálják be a telefonjaikat, amiket majd az utolsó tanóra után a tanár fog kiosztani.
Az egyik harmincfős osztályban így is tettek, ám a nap végén kiderült, hogy az összes diáknak ugyanaz a típusú telefonja van, amik mind ugyanúgy néznek ki. Nem is csoda, hiszen a telefonokat is a mészáros bácsitól kapták ajándékba még tavaly, amikor a focicsapat győzött a megyei kupán. Így aztán a felügyelő tanár nem tehetett mást, véletlenszerűen kiosztotta a diákok között a telefonokat, és azt kérte mindenkitől, hogy próbálja feloldani a kapott telefont a saját PIN-kódjával – végül is egy próbálkozással még nem kerül senki letiltásra. Abban reménykedtek, hogy ha legalább egyvalakinek sikerül belépnie így, akkor ő majd sorban meg tudja csörgetni a többiek telefonját. Ha mindenkinek más a PIN-kódja, akkor mi a valószínűsége annak, hogy legalább egyvalaki a saját telefonját kapja vissza, és be tud lépni?
1. Tipp chevron_down
Ha egy halmaz elemeit, például az osztály tanulóit, vagy a telefonjaikat valamilyen sorrendbe rakjuk, akkor azt egy permutációnak nevezzük. Harminc telefon lehetséges sorbarendezéseinek száma, azaz permutációinak száma harminc faktoriális, aminek a jele 30!, ahol a felkiáltójel nem a mondat végét, hanem a faktoriálist jelzi, ami kifejtve az alábbi szorzat, aminek a végeredménye egy 33 jegyű szám:
30! = 30×29×28× ... ×3×2×1 = 265 252 859 812 191 058 636 308 480 000 000.
Most képzeljük el, hogy a tanulókat és a telefonjaikat is megszámoztuk 1-től 30-ig, és a tanulók a kiosztáskor sorszámaik szerinti sorrendbe kapják meg az összekevert (permutált) telefonokat. Akkor kapja valaki a saját telefonját, ha a telefon permutációban elfoglalt sorszáma, vagyis az, hogy hányadikra osztjuk ki, éppen megegyezik a ráírt sorszámmal.
Mivel a permutáció felfogható úgy mint egy függvény, ami adott számhoz a megkevert sorrendbeli pozícióját rendeli, ezért a függvények nyelvén szólva azt mondhatjuk, hogy akkor kapja valaki a saját telefonját, ha a permutációnak van fixpontja, azaz van olyan sorszám, amihez a permutáció, mint függvény, önmagát rendeli.
Harminc helyett néggyel mutatok példát. Az 1, 2, 3, 4 számsor egy permutációja a 3, 2, 4, 1 számsor. Ennek van egy fixpontja, mert a 2-es szám helyben maradt. Ezzel szemben mondjuk a 4, 1, 2, 3 permutációnak nincs fixpontja, mert mindegyik szám más sorszámú helyre került, mint ahol eredetileg volt.
Mármost a lehetséges permutációkról feltételezzük, hogy teljesen egyforma valószínűséggel valósulnak meg a keverés során. Ezért mi azt keressük, hogy 30 fős osztály esetén ennek a 30! permutációknak mekkora része, azaz hány százalékuk olyan, hogy van legalább egy fixpontjuk. Ezt nem triviális megoldani, de mostmár megismertük a szükséges fogalmakat a matematika nyelvén, így rákereshetünk a neten a megoldásra. Ahogy mondani szokták: A Google a barátod!
2. Tipp chevron_down
Ahogy azt az első tipp alapján megtudtuk a kulcskifejezés: fixponttal rendelkező permutációk száma. Természetesen azzal is ki vagyunk segítve, ha a fixponttal nem rendelkező permutációk számára találunk forrást. Ezen a ponton érdemes felkeresni a oeis.org weboldalt, ami az egész számsorozatok online enciklopédiája, és több százezer számsorozat található meg rajta a sorozatokhoz tartozó rengeteg fontos információval és hivatkozással. Nehéz olyan számsort kitalálni, amiben van valami összefüggés, és ne lenne benne ebben az enciklopédiában.
Megoldás chevron_down
A tippben említett OEIS oldalon a sorozatok között kulcsszavak alapján is tudunk keresni, így beírva hogy: number of permutations with no fixed points, ki is adja nekünk az első helyen az A000166 jelzésű sorozatot, amit keresünk. Ha pedig a sorozat oldalán lejjebb görgetünk, akkor a LINKS címszó alatt az első link egy táblázatra mutat, amiben megtaláljuk a sorozat első 450 tagját. Innen kiolvashatjuk, hogy a fixponttal nem rendelkező 30 hosszú permutációk száma 97 581 073 836 835 777 732 377 428 235 481. Ha ezt a(30)-nak nevezzük, akkor az általunk keresett valószínűség p = [30!-a(30)]/[30!] ≈ 0,6321.
Az az érdekes, ha ugyanezt megnézzük egy 20 fős osztályra, akkor a fent kiírt negyedik tizedesjegyig ugyanezt a számot kapjuk a valószínűségre, sőt még egy 10 fős osztály esetén is. Vagyis ez a valószínűség nagyon gyorsan konvergál egy bizonyos számhoz. Azt kaptuk tehát, hogy szinte az osztálylétszámtól függetlenül kb. 63,2% annak a valószínűsége annak, hogy szerencsével járnak, és sikerül kiosztani a telefonokat a tervezett módon. Ha pedig nézegetjük még ezt a számot, akkor rájöhetünk, hogy itt az 1-1/e számról van szó, ahol e az Euler-féle szám, vagyis a természetes logaritmus alapszáma. Ez egészen meglepőnek tűnhet, de valójában számos kombinatorikai feladat határértékeként meg szokott jelenni az Euler-féle szám valamilyen formában.
Végezetül pedig egy kis útmutatás, hogy kézzel hogyan tudtuk volna kiszámolni a megoldást. A fixponttal rendelkező permutációkat sorba tudjuk venni, aszerint, hogy hány fixpontjuk van. Ha például 29 fixpontja van egy permutációnak, akkor már az utolsó kimaradó is fixpont kell legyen. A 29 vagy 30 fixponttal rendelkező permutációkból tehát összesen egy van, mégpedig az, amikor nincs semmi keveredés, hanem marad az eredeti sorrend. A pontosan 28 fixponttal rendelkező permutációk számának kiszámolásához meg kell néznük, hogy hányféleképpen tudunk 30-ból 2 számot kiválasztani, amik fixpontok lesznek, és ezt meg kell szoroznunk a fixponttal biztosan nem rendelkező 28-as permutációk számával, és így tovább. A lényeg ebben az, hogy a fixponttal rendelkező permutációk számát vissza tudjuk vezetni a fixponttal nem rendelkező kisebb hosszúságú permutációk számára. Vagyis a választ nem tudjuk rögtön kiszámolni zárt alakban, de kiszámolhatjuk a megoldást 1, 2, 3 fős osztályokra, és ha valameddig már kiszámoltuk, akkor egy eggyel népesebb osztályra a korábbi eredményeket felhasználva ki tudjuk már számolni az eredményt. Ezt hívják rekurziónak. Ilyen rekurziós összefüggéseket egyébként találunk a sorozat OEIS weboldalán is, sőt még programkódokat is találunk, amikkel a rekurziók számítógépen számolhatók.
Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.