A születésnap paradoxon ugyanaz, mint amikor 2 apa és két fia összesen 3 ember?

Bizonyos szempontból van hasonlóság. Mindkét esetben nem az emberek számát, hanem a relációk (emberpárok) számát kell alapul venni.

Csak míg a születésnap paradoxon esetén a relációk száma annyi, amennyi, x darab emberből x*(x-1)/2 reláció állítható fel, és mindegyik relációhoz van egy jól meghatározott valószínűség rendelve, hogy a reláció megfelel-e a feltételnek, addig az apa-fia relációban ilyen nincs. Elvileg lehet 50 embert is venni úgy, hogy abból csak két apa van és mindkettőnek a fia is szerepel az 50 csoportban. Ott a kérdés nem az, hogy valami milyen valószínűséggel áll fenn, hanem a kérdés az, hogy adott számú csoportban hogyan lehetséges, hogy az állítás igaz. A válasz az egyik esetében egy valószínűség, a másikban meg a konkrét relációk leírása a válasz.

Bizonyos értelemben igen, de csak nagyon távolról.

Mindkettő esetén az emberek elsőre egy "szimpatikusnak" tűnő választ fogalmaznak meg. A apa-fia eset elég egyszerű ahhoz, hogy a többség viszonylag hamar rájöjjön, hogy tévedett, és kiszámolja a helyes eredményt.

A másik eset jóval bonyolultabban számolható, jóval több ismeret kell az átlátáshoz, ezért a kényelmes ember nem fog utánaszámolni.

Ha az "ugyanaz" betű szerint értendő, akkor a kérdésbeli állítás nem igaz. Ha viszont egy jelenség gyökerét jellemzi, akkor igaz. Mindkét "kapásból való válasz", amely téves lesz, az emberi agy működési sajátosságából következik, ennyibe nugyanaz csak.

Igen, a születésnap paradoxon esetén a relációkat – emberek közötti viszonyokat – kell nézni. 23 ember összesen 23*22/2=253 különböző párt alkot. 3 ember esetén is az a helyzet, hogy ez összesen 3*2/2=3 relációt alkot (Aladár-Béla, Aladár-Cecil, Béla-Cecil). Ilyen szempontból hasonló a kettő, hogy az ördög a relációkban rejlik.

~ ~ ~

A különbség viszont az, hogy míg a születésnap paradoxonnál minden relációnál van egy fix esélye annak, hogy az adott relációban szereplő két embernek azonos napon van a születésnapja. Ennek ugye az esélye – szökőévet nem számítva – 1:365. Ebből lehet aztán kiszámolni, hogy mekkora az esélye annak, hogy 23 emberből van legalább két ember, akinek azonos napra esik a születésnapja. Ráadásul itt a reláció szimmetrikus, ha az egyik embernek a születésnapja a másikéra esik, akkor a másiké az egyikére.

Az, amit kiszámolunk, az viszont egy valószínűség. 23 ember esetén (1-(364/365)^253) = 50,04% annak a valószínűsége, hogy két embernek azonos napra esik a születésnapja. 30 ember esetén meg már 69,68%. Tehát itt alapvetően valószínűségszámításról van szó.

~ ~ ~

Az apa-fia feladványnál viszont más a helyzet. Ott megmondjuk, hogy hány ember van. És megmondjuk, hogy hány adott típusú reláció van., Az megmondjuk, hogy kettő darab „apa-fia” reláció van (100%-os eséllyel, hiszen azért van „apa-fia” reláció, mert azt mondtuk). Tehát nem számolunk itt semmiféle valószínűséget. Ráadásul a feladvány pont azért tud működni, mert a reláció bár szimmetrikus, a relációban betöltött szerep nem az. Illetve a relációk is sajátos viszonyban vannak egymással, hiszen ha valaki az egyik relációban apa, attól még lehet a másik relációban fiú. Nyilván nem működik úgy a feladvány, hogy két fivér és két nővér az három ember, hiszen nem lehet az, hogy valaki fivér az egyik, nővér a másik relációban. Szintén trivális lenne a megoldás, ha a feladvány úgy szólna, hogy két báty meg két öcs, az három ember. Valahogy itt az emberi elme hamarabb felveti azt a lehetőséget, hogy valaki lehet egyszerre bátyja, és öccse is valakinek. Valamiért az apa-fia kapcsolatban kevésbé gondolunk erre az eshetőségre. Szintén túl könnyű lenne a feladat, ha úgy szólna, hogy két apa, két fia, meg egy nagyapa és egy unoka az három ember. Túl hamar rávezetne a megoldásra.

Amit viszont itt megoldásnak lehet tekinteni az nem egy valószínűség, hanem a relációk konkrét leírása, és az egyes személyek a különböző relációkban belül betöltött szerepének a megadása.

> Valamiért az apa-fia kapcsolatban kevésbé gondolunk erre az eshetőségre.

Kiegészítés: Itt nem is annyira matematika természetű a logikai feladvány, hanem nyelvi természetű. Ha van három generáció, és mi kívülről nézve beszélünk róla, akkor a nagyapát nagyapának nevezzük. Nyilván ebből fakadónak van neki fia, tehát apa is, de mégsem apának fogjuk hívni, hanem nagyapának. Ugyanígy az apát apának nevezzük. Nyilvánvaló, hogy ő egyben fia is valakinek, de mégis ebben az esetben az apa megnevezést fogjuk rá használni. Így a nagyapa, az apa, és a fiú megnevezés egyértelműen beazonosítja, hogy kiről van szó. Emiatt a nyelvhasználati szokás miatt jut kevésbé az eszünkbe, hogy attól, hogy három emberből valaki apa, egyben lehet fiú is, illetve attól, hogy valaki fiú is, lehet apa is.

> És ebbe a körbe beletartozik a mérleg rejtvény is amikor 59049 aranypénzünk van, de az egyik hamis és könnyebb?

Nem, ez még csak annyira sem hasonlít az előző kettőre, mint amennyire az előző kettő hasonlít egymáshoz. Itt már nem csak egyed-egyed relációkat vizsgálunk. Itt egy halmazt harmadolunk, és minden lépésben kizárjuk az érmék 2/3-át. Így aztán közelítő módszerrel jutunk el végül a megoldásig. Maximum olyan szempontból lehet ráhúzni a relációt, hogy a még gyanús érméket osztjuk három részhalmazra, aminél ismertek a részhalmazok közötti relációk:

hamis érmét tartalmazó kupac súlya < az egyik csak valódi érmét tartalmazó kupac súlya

hamis érmét tartalmazó kupac súlya < a másik csak valódi érmét tartalmazó kupac súlya

az egyik csak valódi érmét tartalmazó kupac súlya = a másik csak valódi érmét tartalmazó kupac súlya

A méréssel döntjük el, hogy a három közül a mérleg melyik relációt mutatja, és ebből egyértelműen meghatározható, hogy melyik a hamis érmét tartalmazó kupac. (A mérleg bal, vagy a jobb oldalán található kupac, illetve a mérlegre nem tett kupac.)

De itt már nem egyed-egyed, hanem halmaz-halmaz relációról van szó. A feladvány pontosan meghatározza az egyed-egyed relációkat, a megoldás meg nem is egy valószínűség, nem is a pontos relációk megadása, hanem egy módszer, egy algoritmus, amivel megtalálható a hamis érme, és közbenső lépés az, hogy az egyed-egyed relációból úgy alkotunk halmaz-halmaz relációkat, hogy maximalizáljuk az egy lépésben kizárt – gyanú felett álló – halmazok elemeinek a számát. (Pontosabban a lépések számát kell minimalizálni, de most fogadjuk el ezt a pontatlan megfogalmazást.)

~ ~ ~

Tehát röviden:

Születésnap paradoxon

Adott: az elemek száma, a kritériumoknak megfelelő relációk valószínűsége.

Amit kapsz: Egy valószínűséget, annak a valószínűségét, hogy van legalább egy a kritériumnak megfelelő reláció.

Apa-fia feladvány

Adott: Az elemek száma, az összes relációban bizonyos szerepet betöltők száma.

Amit kapsz, ami a megoldás: A pontos relációk meghatározása, illetve az, hogy az egyes elemek a különböző relációban milyen szerepet töltenek be.

Mérleg feladvány

Adott: Az elemek száma, közvetett módon az összes reláció jellegének meghatározása, bizonyos részhalmaz-részhalmaz relációk meghatározására alkalmas mérőeszköz és egy elvárt limit a mérések számára nézve.

Amit kapsz, ami a megoldás: Egy módszer, egy algoritmus, hogy milyen módon kell részhalmazokat képzeni ahhoz, hogy a részhalmazok közötti relációk meghatározásához szükséges mérések száma minimális, illetve a limiten belül maradjon.

Mondjuk ez már megért volna egy másik kérdést.

Ugye önmagában az, hogy a képek helyett a hash-eket hasonlítod össze, az nem csökkenti a vizsgálandó relációk számát. Pusztán az összehasonlításhoz szükséges időt rövidíti le jelentősen. Néha ez is pont elég. Viszont a hash generálásához le kell darálni az összes képet, így nyilván ennek nagyszámú kép esetén van optimalizáló hatása. Nyilván a relációk kb. a képek számának négyzetével arányosan nő, míg a hash generálás a képek számával arányos (átlagosan, hasonló képméretet alapul véve). Tehát minél több képről van szó, a hash generáláson elveszített idő annyival jobban megtérül az összehasonlításoknál.

Tehát a hash generálás jó, tényleg jelentősen gyorsítja a dolgot, de a relációk számát nem csökkenti.

Viszont lehet a relációk számát is redukálni. Itt kétféle megközelítés lehet:

I. hash alapján történő redukció.

1. Legenerálod az összes fájl hash-ét, és ezt tárolod egy tömbben. (Esetleg hozzá lehet venni a kép méretét is.)

2. Hash alapján sorba rendezed a tömböt, és két ciklussal úgy mész végig, hogy csak az azonos hash-el rendelkező képeket hasonlítod össze. A képméret egy opcionális közbenső lépés, hiszen ha a képek mérete eltér, akkor biztos, hogy a tartalmuk is. Ha a képméret is azonos, akkor válhat szükségessé a tényleges tartalom összehasonlítása. Bár ez kihagyható, szinte elhanyagolható az esélye annak, hogy két kép mérete is, és hash-e is azonos legyen. De ha nagyon biztonságosra akarsz menni, és a képek tényleges összehasonlítását el akarod kerülni, akkor lehet megoldás két különböző hash generálása (mondjuk egy SHA-256 és egy MD5). Vagy ha magad írod meg a hash generálást, akkor lehet venni a bájtokból származó hash-t, meg a bájtokból, meg még plusz egy konstans bájtból, vagy bájtsorozatból származó hasht. Vagy lehet venni a bájtokból származó hash-t, meg az első x darab bájtból származó hasht. De félmillió kép esetén ezzel nem foglalkoznék egy 32 bites hash esetén.

~ ~ ~

II. Méret alapján történő redukció.

1. Itt végigmész a fájlokon és veszed a képméretüket, ebből csinálsz tömböt.

2. Méret alapján rendezed sorba a tömböt.

3. Végigmész két ciklussal a tömbön, és csak az azonos méretűek esetén vizsgálódsz. Ott legenerálod a fájlok hash-ét, és elsőnek azt hasonlítod össze. Innen ugyanaz a történet.

Ennek az az előnye, hogy ha sok olyan fájlod van, amiből csak egy van, akkor elég sok olyan fájl is lesz, aminek a mérete is csak egyszer fordul elő, és ezeknél meg lehet spórolni a hash generálást is, ezzel további számítási kapacitást spórolva.