Sáhzamán király kisunokája

A titkos kommunikációval kapcsolatos feladatok legtöbbször nagyon kreatív megoldásokat igényelnek, miközben a megoldásukhoz többnyire nincs szükség magasabb matematikai képzettségre – ugyanakkor érdekes, a való életből vett problémák is tartoznak hozzájuk, főleg a mai digitális világban, amikor az adat komoly érték. A Typotex Kiadó A logika világa-sorozatában korábban megjelent Ezeregy tudós éjszaka című könyve nagyon olvasmányosan mesél a matematika legkülönbözőbb területeiről problémákat, és ezek között szerepel például az alábbi, titkos kommunikációval kapcsolatos alapfeladat is.

Sáhzamán király kisunokája táncversenyen vett részt sokadmagával, és a versenyzők mindegyike szeretné megtudni, hogy jobb pontszámot kapott-e a produkciójára, mint az átlag. A pontszámok nyilvánosságra hozatala azonban tilos! Gondolkozz el rajta hogyan lehetne megoldani ezt a kihívást, és csak akkor olvass tovább, ha van rá ötleted.

Egy lehetséges megoldás, hogy egyvalaki kitalál egy tetszőleges számot, ez lehet akármilyen nagy szám is, vagy akár negatív szám. A számot hozzáadja a pontszámához, és az így kapott számot megsúgja egy másik versenyzőnek. A másik versenyző ebből nem tud meg semmit, viszont hozzáadja a hallott számhoz a saját pontszámát, és ezt továbbsúgja a következő versenyzőnek. Így tovább, mindenki hozzáadja a saját pontszámát, majd az utolsó versenyző a legvégén visszasúgja a legelsőnek a kapott számot. Ekkor ő levonja belőle az elején általa hozzáadott számot, és így megtudja az összes versenyző pontszámainak összegét, amit ha leoszt a versenyzők számával, akkor megvan az átlag. Ezt az átlagot nyilvánosan közli a többiekkel, és így már mindenki meg tudja állapítani, hogy az átlagnál jobban vagy rosszabbul teljesített.

Természetesen ahhoz, hogy ez működjön, az kell, hogy senki ne csaljon, azaz mindenki betartsa a metódust a leírtak szerint. Ha például a végén hamis átlagot mond be a versenyző, aki kiszámolta az átlagot, akkor azzal mindenkit mást átver. Ugyanakkor bárki más is meg tudja téveszteni a többieket, ha direkt nagyobb vagy kisebb számot súg tovább. Ha csak egyvalaki csal, akkor a csaló megtudja az igazságot, míg a többiek tévedésben lesznek. (Az érdekesség az, hogy a megoldáson lehet javítani, és van olyan megoldás, ami még a csalásokat is kiszűri, de most nem erről lesz szó.)

202. feladvány: Sorrendiség kiderítése titkosan

Tegyük fel, hogy senki nem csal, és mindenki a megbeszélteknek megfelelően cselekszik. Ebben az esetben létezik-e olyan metódus, amivel egy teljes sorrendiséget fel tudnak állítani maguk között a versenyzők úgy, hogy eközben senkinek nem derül ki a pontszáma, tehát senki nem ad senkinek olyan információt, amiből valamelyik résztvevő konkrét pontszámára tudna következtetni, csakis a köztük lévő sorrendre derül fény? Számítógépet természetesen nem használhatnak.

Tipp chevron_down

Akárhányan is vannak, ha páronként megoldható a sorrendbe állítás, akkor az összes versenyzőt is sorba tudjuk állítani.

Figyelmeztetés chevron_down

Ahogy azt a tippben említettük, elegendő két játékos esetére megoldani a problémát. Ez alapján viszont mondhatná valaki azt, hogy nagyon egyszerű a dolog, hiszen azt már megoldottuk, hogy kiderítsük titkosan, hogy átlag alatti vagy fölötti valakinek a pontszáma, és ebből az információból két játékos esetén következik kettejük sorrendje. Igen ám, de két játékos esetén az átlagból és a saját pontszámból a másik játékos pontszáma kitalálható, ami tilos!

Megoldás chevron_down

Egy lehetséges megoldás lehet az alábbi. Igaz ugyan, hogy azt a részfeladatot akarjuk megoldani, hogy csak két játékos van, de a procedúrába bevonhatunk egy harmadik játékost is. Legyen a szóban forgó két játékos A és B, C pedig egy harmadik, aki segít. A találjon ki két tetszőleges pozitív számot, X-et és Y-t, amiket súgjon meg B-nek. Ezután A is és B is adja hozzá X-hez a saját pontszámát, majd az összeget szorozzák meg Y-nal, és a kapott számokat súgják meg C-nek. C ebből el tudja dönteni, hogy kinek a pontszáma nagyobb, mert a számok sorrendisége nem fog megváltozni az elvégzett műveletek után. Az Y-nal való szorzásra azért van szükség, hogy C ne tudja visszakövetkeztetni még a pontszámaik különbségét se.

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.