Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

I. rész: Néhány szó a véletlenszámokról

I. rész: Néhány szó a véletlenszámokról

Lovász László előadását lejegyezte Ambrus Gergely

Lovász, László


1. Véletlen számok alkalmazásai

Tekintsük az ( x - y ) ( z - u ) - ( x - z ) ( y - u ) + ( x - u ) ( y - z ) = 0 egyenletet! A kérdés az, hogy ez vajon minden esetben teljesül-e. A zárójeles szorzatok kibontásával

( x - y ) ( z - u ) - ( x - z ) ( y - u ) + ( x - u ) ( y - z ) = = x z - x u - y z + y u - x y + x u + y z - u z + x y - x z - y u - u z = 0 ,

tehát azonossághoz jutunk.

Elvileg ezzel a módszerrel véges idő alatt bármilyen polinomokra vonatkozó azonosságot ellenőrizni tudunk, ám ha csak kéttagú összegeink vannak, de 50 tényező, akkor a szorzat kibontásához 2 50 tagot kellene felírnunk, ez pedig a legfejlettebb számítógépek segítségével is rengeteg időbe tellene. Így más megoldást kell keresnünk a problémára.

Egy konkrét helyettesítésre könnyű az azonosságot ellenőrizni: ehhez ugyanis nem kell a zárójeleket felbontani, hanem elvégezhetjük a kijelölt műveleteket úgy, ahogyan a zárójelezés mutatja. Ha kellően sok különböző, véletlenszerűen választott helyettesítést tekintünk, akkor valószínűleg a polinom értéke csak akkor lesz minden esetben lesz 0, ha azonosságról van szó.

Pontosítsuk ezt a gondolatot. A következőkben tekintsük az f ( x 1 , x 2 , , x n ) polinom minden olyan helyettesítését, ahol x i ? { 0 , 1 , , N - 1 } , és f foka legyen legfeljebb k . Be fogjuk látni, hogy

ha f nem azonosan 0, akkor a tekintett N n helyből legfeljebb k N n - 1 esetben veszi fel a 0 értéket.

Bizonyításunkhoz teljes indukciót alkalmazunk n -re: n = 1 esetén egy k -ad fokú egyváltozós polinomot vizsgálunk, amelynek valóban legfeljebb k db valós gyöke van, így állításunk erre az esetre igaz. Tegyük fel, hogy n //>// 1 , és hogy n - 1 változóra igaz az állítás! Az f polinomot felírhatjuk a következő alakban:

f ( x 1 , , x n ) = f 0 ( x 1 , , x n - 1 ) + x n f 1 ( x 1 , , x n - 1 ) + + x n r f r ( x 1 , , x n - 1 ) ,

és nyilván r ? k , illetve f r ( x 1 , , x n - 1 ) foka legfeljebb k - r . Rögzítsük először x 1 , , x n - 1 értékét! Ekkor f az x n változó legfeljebb r -ed fokú polinomja, amelyben az együtthatók az f i polinomok helyettesítési értékei. Ha f r ( x 1 , , x n - 1 ) ? 0 , akkor ez az összeg x n r -ed fokú polinomja, szükségképp legfeljebb r db egész gyöke van, így a lehetséges N db x n értékből legfeljebb r fogja teljesíteni az egyenletet. Mivel x 1 , , x n - 1 lehetséges különböző értékeinek száma N n - 1 , a polinom legfeljebb r N n - 1 ilyen tulajdonságú helyen tűnhet el. Ha f r ( x 1 , , x n - 1 ) = 0 , akkor akár az összes N db tekintett x n helyen eltűnhet a polinom (ha minden együttható 0); az ilyen esetek száma viszont legfeljebb ( k - r ) N n - 2 lehet indukciós feltevésünk miatt, így legfeljebb ( k - r ) N n - 2 · N = ( k - r ) · N n - 1 ilyen típusú helyen tűnhet el a polinom. A két esetet összegezve kapjuk, hogy az f ( x 1 , , x n ) polinom legfeljebb r N n - 1 + ( k - r ) N n - 1 = k N n - 1 esetben veszi fel a 0 értéket, ezzel állításunkat beláttuk.

Tekintve, hogy összesen N n esetünk van, annak a valószínűsége, hogy egy véletlen helyettesítésre a helyettesítési érték 0 lesz, legfeljebb k / N . Így N = 2 k esetén 1 / 2 valószínűséggel kiderül, ha az adott egyenlet nem azonosság. Ez persze túl nagy esélyt ad a hibának; de megismételhetjük a kísérletet egymás után mondjuk 20-szor, akkor a hiba valószínűsége kisebb lesz, mint 1 / 2 20 , ami már általában teljesen elfogadható.

Így véletlen számokat használva, egy polinomról viszonylag hatékonyan ki tudjuk deríteni, hogy azonosan 0-e vagy sem. Érdekes megjegyezni, hogy véletlen számok használata nélkül nem ismeretes olyan módszer, amely elkerülné a bevezetőben említett „exponenciális robbanást”.