Az ügynökös feladványban az ügynök neve nem véletlenül volt Fitch Hall. A név első fele William Fitch Cheney (1894–1974) amerikai matematikaprofesszorra utalt, akinek a neve a róla elnevezett ötlapos kártyatrükkről ugorhatott be azoknak, akik már találkoztak ezzel a nagyon régi és rengeteg helyen népszerűsített, nem triviális matematikán alapuló telepatikus kártyatrükkel. Az ügynökös feladvány teljesen hasonló elven működik, mint a trükk, csak az eretei trükkben PIN-kódok helyett kártyalapok szerepelnek, és nem a hatodikat, hanem csak az ötödiket kell kódolni. A kártyatrükk lényege, hogy a nézők választanak öt tetszőleges kártyalapot a francia kártyacsomagból, amikből a bűvész segédje sorra megmutat négyet a bűvésznek, aki kitalálja az ötödiket.

A név második fele pedig Philip Hall angol matematikusra utalt, akiről a Hall-tétel kapta a nevét, aminek egyik leggyakoribb alkalmazása, hogy megadja a szükséges és elégséges feltételét annak, hogy adott preferenciákkal rendelkező férfiakat és nőket össze tudunk-e úgy párosítani vagy házasítani, hogy mindenki elégedett, illetve boldog legyen. Nem kell azonban megijedni, mint látni fogjuk, a feladvány a Hall-tétel ismerete és felhasználása nélkül is megoldható, az csak azok számára volt kis segítség, akik már hallottak róla.

A feladvány egyik része annak kitalálása, hogy milyen információ kódolhatja a hatodik PIN-kódot, ha egyébként semmi mást nem küldünk át, csak a másik öt PIN-kódot. A feladvány második része pedig a konkrét kódolási eljárás megkonstruálása. (Itt jegyzem meg, hogy a félreérthetőség elkerülése végett a háromjegyű kódszámokat ezentúl simán PIN-eknek fogom hívni, ugyanis a kód és kódolás szavakat sokszor fogom használni, és nem szeretném, ha összekevernénk a kódolandó dolgokkal, amik történetesen éppen kódszámok, de bármi mások is lehetnének, egy kártyatrükk esetében például kártyalapok, ahogyan az föntebb már említésre került.)

Egy ötlet nem elég

Mindkét részben volt nehézség. Az elsőhöz az egyik ötlet az, hogy mivel a feladat szerint a PIN-ek sorrendje nem számít, azt mi választhatjuk meg, és ezt kihasználva tudunk plusz információt kódolni. Öt dolgnak 5! = 5·4·3·2·1 = 120 féle különböző sorrendje létezik, és a PIN számok nagyság szerinti sorbarendezhetőségét kihasználva a fogadó ügynök is értelmezni tudja, hogy a küldő éppen melyik permutációra gondol. Igen ám, de a feladat feltételeinek megfelelő háromjegyű PIN, amiben nincs két egyforma számjegy, 720 féle lehet, így elvileg a hatodik PIN is 720 féle lehet, tehát a 120 variáció nem elegendő, ennek éppen a hatszorosa kéne a kódolásához. Szükség van tehát még egy plusz ötletre.

A plusz ötlet az, hogy nemcsak az öt PIN sorrendjét választhatjuk meg önkényesen, de azt is, hogy a hat közül melyiket hagyjuk ki a közlésből, amit aztán kódolni akarunk. Ez elvileg lehetőséget ad plusz információ kódolására, vagy úgy is fogalmazhatunk, hogy a hatodik PIN-nek nem kell 720 variációt lefednie, hiszen az nem tetszőleges, ugyanis mi választhatjuk ki, hogy melyik legyen a hatodik. Mivel azonban a fogadó fél eredetileg nincs ismeretében annak, hogy a küldő mik közül választhatja ki az öt PIN-t, amit végül elküld, így a kiválasztással információt kódolni nem triviális. Nézzük mi az pontosan, aminek teljesülnie kéne ahhoz, hogy a feladat megoldható legyen.

189 492 294 437 160 variáció – nem sok az egy kicsit?

Mivel a PIN-ek különbözőek, és a sorrendjük nem fontos, ezért a hat PIN-t 720 lehetőségből 720 alatt a 6 = 189 492 294 437 160 féleképpen választhatjuk ki, az átadott információnak tehát ennyi különböző lehetőséget kéne kódolni valamilyen módon. Az átadott információ pedig öt PIN a lehetséges 720-ból, és azok bemutatási sorrendje. 720-ból ötöt 720 alatt az 5 = 1 590 145 128 144 féle képpen választhatunk ki, és ezek mindegyikét 120 féle sorrendben mutathatjuk be, ahogy azt már korábban megbeszéltük. A két szám összeszorzandó, így tehát összesen 190 817 415 377 280 féle lehet a küldött üzenet. Ez a szám szerencsére nagyobb, mint amennyi lehetőséget kódolni akarunk, viszont van még egy feltétel. A kódoló öt PIN-nek minden esetben olyan hat PIN-t kell kódolnia, amelyek a kódoló PIN-eket tartalmazzák. Hogy ez a párosítás a rengeteg kódoló és kódólandó között lehetséges, az nem triviális. Ez az, amit az említett Hall-tétel segítségével be lehet látni, vagy meg lehet adni egy konkrét párosítási konstrukciót. Mi ez utóbbit fogjuk tenni, ami természetesen szemléletesebb és praktikusabb, hiszen egyúttal megadja az ügynökeinkek a kódolási és dekódolási procedúrát is.

Mielőtt azonban megadnánk egy lehetséges konstrukciót a párosításra, hadd szemléltessem azt a gráfot, amiben ezt a párosítást el kéne végezni. Képzeljük el, hogy egy nagyon hosszú papírlap bal oldalán egymás alatt felsoroljuk az összes lehetséges hatelemű halmazt, amit a 720 féle PIN-ből ki lehet választani. Ez tehát egy 189 492 294 437 160 elemű lista lesz. Ezután soroljuk fel a papír jobb oldalán egymás alá az összes lehetséges rendezett ötöst, amit a PIN-ek 720 elemű halmazából ki lehet választani. Így kapjuk a 190 817 415 377 280 elemű jobb oldali oszlopot. Mármost kössük össze egymással azokat az elemeket, amik összepárosíthatók lennének elvileg, vagyis egy rendezett ötöst a jobb oldalról kössünk össze minden olyan hatelemű halmazzal a bal oldalon, aminek az ötös (mint halmaz) részhalmaza, azaz az ötös minden tagja eleme a hatos halmaznak.

Mivel minden hatelemű halmazból hatféleképpen hagyhatunk ki egy elemet, és a maradékot 120 féleképpen rendezhetjük sorba, ezért 720 összeköttetése lesz minden egyes elemnek a bal oldali listában. Ennek az ún. páros gráfnak tehát, amiben csak ellentétes oldali elemek lesznek összekötve, összességében 136 434 451 994 755 200 éle lesz. Ezek közül az élek közül kéne kiválasztani egy párosítást, azaz minden bal oldali elemhez egy jobb oldali elemet úgy, hogy egyik jobb oldali elemet sem használunk fel kétszer, vagyis 189 492 294 437 160 diszjunkt összeköttetést.

Lássuk a konstrukciót

Annak ellenére, hogy milyen brutálisnak tűnik a feladat, egy egyszerű elv segítségével könnyen konstruálhatunk megoldást az elrettentő nagy számoktól teljesen függetlenül, ami nagyon szépen mutatja a matematika erejét. A PIN-eket nagyság szerinti sorrendbe rendezve számozzuk meg őket 1-től 720-ig. A küldő fél adja össze mind a hat PIN sorszámát, és vegye hattal osztva az osztási maradékát az összegnek, ezt jelüljük s-el, ami tehát 0-tól 5-ig vehet fel tetszőleges értéket. A küldő stratégiája az lesz, hogy a nagyság szerint sorrendbe helyezett hat PIN közül az (s+1)-ediket fogja kihagyni a közlésből.

Miért jó ez? Nézzük meg, ha a vevő fél is tudja, hogy a küldő ezt a megbeszélt stratégiát követi, akkor milyen plusz információt hordoz számára az átküldött öt PIN. Tegyük fel, hogy az A, B, C, D és E sorszámú PIN-eket kapja a fogadó, amiknek ez a nagyság szerinti sorrendje, tehát A < B < C < D < E. Legyen továbbá X az át nem küldött PIN sorszáma. Mivel a fogadó ügynök a hat PIN-ből csak ötöt lát, ezért ennyiből nem ismerheti a hat sorszám összegét, se azok maradékát hattal osztva, amit s-nek neveztünk. Ha viszont tudná, hogy X az eredeti nagyság szerinti sorrendből melyik helyről lett kihagyva, akkor már ismerné s-t, és ezzel együtt az X hatos maradékát is ki tudná következtetni. Ha például A < X < B < C < D < E lenne a helyzet, akkor s + 1 = 2 lenne, mert X a második helyen szerepel a nagyság szerinti sorrendben. Ebből pedig s = 1 következne, és ekkor az ismeretlen X sorszám hatos maradéka is számolható a többi sorszám hatos maradékának ismeretében. Ha mondjuk a többi öt sorszám összege éppen hattal osztható, akkor X maradéka csak 1 lehetne hattal osztva, mert csak így jöhet ki s = 1 maradék mind a hat PIN sorszámának összegére.

Az A, B, C, D, E sorszámok hat tartományra osztják az 1-től 720-ig terjedő sorszámokat. Az első tartományba esnek az A előtti sorszámok, a második tartományba az A és B közötti sorszámok, és így tovább, egészen az E utáni sorszámok tartományáig. Ezen tartományokban összesen 715 sorszám szerepel, amik közül az X kikerülhet. Azonban bármelyik tartományban is van az X, azon a tartományon belül a hatos maradéka rögzített, tehát a számoknak csak a hatoda jöhet szóba, és pont ez az, amit akartunk, vagyis az átküldött PIN-ek sorrendjétől függetlenül hatodára tudtuk csökkenteni a lehetséges jelöltek számát.

Az alábbi ábra szemlélteti a fent leírtakat. A sorszámokat balról jobbra 1-től 720-ig kiszíneztük úgy, hogy az azonos maradékot adó sorszámok vannak azonos színnel színezve, vagyis hatosával ismétlődnek a színek. Az át nem küldött X lehetséges helyeit kérdőjelekkel jelöltük. Ha mondjuk a fogadó fél azt látja, hogy az átküldött öt PIN (A, B, C, D és E) sorszámai összegének hatos maradéka négy, akkor ebből tudja, hogy X hatos maradékának kettőnek kell lennie, amennyiben A előtt szerepel a sorban, hiszen a kiválasztási stratégia szerint ekkor lesz mind a hat kód sorszámainak összege hattal osztható (s = 0). Ha tehát X A-nál kisebb, akkor narancssárga helyre eshet, ha viszont A és B közé esik, akkor egyel nagyobb kell legyen a maradéka, azaz piros lehet csak, és így tovább.

Valójában az egyes tartományokra vonatkoztatva a kérdőjelek aránya eltérhet a hatodtól, hiszen az egyes tartományokban lévő pontok száma nem biztos, hogy éppen osztható hattal. Viszont az, hogy a rákövetkező tartományra mindig egyel nő a maradék, ez garantálja, hogy 720/6 = 120 kérdőjelnél több biztos nem lesz. A dekódolást végző ügynök feladata tehát lényegében az, hogy elkészíti a fenti ábrát, vagyis A, B, C, D, E betűkkel bejelöli az átküldött öt PIN sorszámát, majd az öt sorszám összegének hatos maradéka alapján berajzolja a kérdőjeleket, végül a legfeljebb 120 kérdőjel közül az öt PIN sorrendje fogja neki kódolni, hogy melyik ezek közül a hatodik PIN.

Érdemes még megjegyezni, hogy a feladvány általánosítható. Ha N dologgal egy (N+1). dolgot szeretnénk kódolni a kiválasztás és a sorrend segítségével, akkor ez abban az esetben tud működni, ha a szóban forgó dolgok maximum N!+N-1 lehetséges értéket vehetnek fel. A Fitch-féle ötlapos kártyatrükknél például N = 5, tehát a pakli maximális nagysága, amivel a trükköt meg lehet csinálni: 5! + 5 - 1 = 124, azaz a trükköt akár két csomag eltérő hátú francia kártyapaklival is meg lehet csinálni. Egy csomag esetén azonban létezik egyszerűbb konstrukció is, amivel a dekódolás könnyebben elvégezhető egy bűvésznek.