Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9. fejezet - 9. KOMBINATORIKAI ALKALMAZÁSOK

9. fejezet - 9. KOMBINATORIKAI ALKALMAZÁSOK

A lineáris algebra alkalmazási területei igen szerteágazóak. Sokan azonban úgy vélik, hogy meglehetősen sok előismeretre van szükség mind lineáris algebrából, mind pedig az alkalmazási területről ahhoz, hogy az alkalmazásokhoz valóban el lehessen jutni. Ebben a fejezetben megmutatjuk, hogy számos kombinatorikai alkalmazás szinte semmilyen előismeretet sem igényel, és mégis komoly és meglepő eredményeket tudunk így elérni. Látni fogjuk, hogy sokszor csak az egyenletrendszerekre vonatkozó legalapvetőbb összefüggéseket kell felhasználni (Gauss-kiküszöbölés és következményei, 3.1 pont). Lesznek természetesen olyan részek is, amikor ennél jóval mélyebb dolgokra támaszkodunk (beleértve pl. még a véges testek szerkezetét is).

Az alkalmazásokat nemcsak a szoros értelemben vett kombinatorika és gráfelmélet területéről választottuk, hanem jónéhány számelméleti és geometriai problémát is tárgyalunk. A fejezet címében szereplő „kombinatorikai” jelző ennek megfelelően inkább az alkalmazások (nagyon tágan értelmezett) kombinatorikai jellegére utal. (A lineáris algebra más „típusú”, de ugyancsak alapvetően fontos alkalmazásai leginkább az analízis különböző területeihez, pl. a differenciálegyenletek elméletéhez kapcsolódnak, ilyenekkel azonban ennek a könyvnek a keretein belül nem foglalkozunk.) A problémák válogatása és rendszerezése önkényesen történt, igyekeztünk sokféle témát és módszert bemutatni. Előnyben részesítettük az olyan kérdéseket, amelyek más érdekes — nem feltétlenül lineáris algebrai — összefüggésekhez is elvezetnek.

9.1. Szép polinomok

Bevezetésül egy polinomokra vonatkozó feladatot tárgyalunk, amelyről ránézésre egyáltalán nem látszik a lineáris algebrai kapcsolat.

9.1.1 Tétel

Minden nemnulla f polinomnak van olyan nemnulla g=fh polinomszorosa, hogy g-ben minden tag kitevője prímszám.❶

A tétel bármilyen test feletti polinomokra érvényes, de fennáll pl. egész együtthatós polinomokra is. Ez utóbbi a racionális együtthatós esetből azonnal következik: az (egész együtthatós) f-et racionális együtthatósként tekintve, az így kapott h-t végig kell szorozni az együtthatók nevezőinek a legkisebb közös többszörösével.

A tételre három különböző lineáris algebrai megoldást adunk egyenletrendszerek, alterek dimenziója, illetve a leképezések dimenziótétele segítségével.

A bizonyításokból látni fogjuk, hogy a tétel ugyanúgy igaz, ha a prímszámok helyett pozitív egészek tetszőleges végtelen sorozatát vesszük, és azt írjuk elő, hogy csak ilyen kitevőjű tagok forduljanak elő g-ben. (Az állítás nyilván akkor „mutatós”, ha valamilyen érdekes sorozatot választunk, ki-ki ízlése szerint a prímeket, a Fibonacci-számokat, a kettőhatványokat stb., közben persze ügyelni kell arra, nehogy véletlenül az adott speciális sorozatra az állítás triviálisan adódjon.)

Első bizonyítás: Legyen f01x+…+αtxt, αt≠0, és keressük h-t h01x+…+βnxn alakban, ahol n-et is később fogjuk alkalmasan megválasztani. Az fh szorzást elvégezve a nem prím kitevőjű tagok együtthatóira 0-t kell kapnunk; ez egy olyan homogén lineáris egyenletrendszert jelent a βj-kre, ahol az együtthatók az α-k közül kerülnek ki. (Az első néhány egyenlet: α0β0=0, α0β11β0=0, α0β4+…+α4β0=0 stb.) Itt az ismeretlenek száma n+1, az egyenletek száma pedig a 0,1,2,…,n+t közül a nemprímek száma, azaz n+t+1–π(n+t), ahol π(s) az s-nél nem nagyobb (pozitív) prímek számát jelöli. Ha több az ismeretlen, mint az egyenlet, akkor a homogén lineáris egyenletrendszernek biztosan van nemtriviális megoldása, ami éppen egy megfelelő h polinomot ad. Ez az n+1>n+t+1–π(n+t) egyenlőtlenség pontosan akkor teljesül, ha π(n+t)>t=deg f. Ha tehát n-et ennek megfelelően választjuk, akkor ebből a kívánt tulajdonságú g létezése következik.❷

Második bizonyítás: Legyen s később alkalmasan megválasztandó pozitív egész és V a legfeljebb s-edfokú polinomok szokásos vektortere (beleértve a nulla polinomot is). Tekintsük V alábbi két részhalmazát: W1 álljon azokból a (legfeljebb s-edfokú) polinomokból, amelyekben minden tag kitevője prímszám, W2 pedig azokból, amelyek oszthatók f-fel. Nyilván W1 és W2 altér V-ben, továbbá dim V=s+1, dim W1=π(s), dim W2=st+1. Ha dim W1+dim W2>dim V, akkor W1W20_ (lásd a 4.6.6 feladatot), és W1W2 bármely nemnulla eleme megfelel g-nek. A dim W1+dim W2>dim V feltétel pedig pontosan akkor teljesül, ha π(s)>t=deg f (ami megegyezik az első bizonyításban kapott előírással).❷

Harmadik bizonyítás: Legyen W1 és V ugyanaz, mint a második bizonyításban, és tekintsük azt az A:W1V lineáris leképezést, amely minden polinomnak megfelelteti az f polinommal történő maradékos osztásnál keletkező maradékot. Ekkor Ker A éppen az f-fel osztható és csupa prím kitevőjű tagból álló (legfeljebb s-edfokú) polinomok halmaza. Ha dimImA<dimW1 akkor a dimenziótétel szerint Ker A0_ és így Ker A bármely nemnulla eleme megfelel g-nek. Nyilván Im A a legfeljebb t–1-edfokú polinomok vektortere, tehát dimImA=t, továbbá dim W1=π(s). Így dimIm A<dimW1 a (korábbi bizonyításoknál is látott) π(s)>t=deg f feltételt jelenti.❷

Feladatok

M9.1.1 Számkitalálás.

a) Micimackó gondolt húsz egész számot, ezek x1, x2, …, x20. Malacka megkérdezheti tőle bármely olyan kifejezés értékét, amelyet ezekből az összeadás és kivonás segítségével képezünk, pl. mennyi x1+8x2–7x3. A következő kérdés mindig függhet az előzőre kapott választól. Legkevesebb hány kérdéssel tudja Malacka kitalálni a húsz számot?

*b) Mennyiben változik a helyzet, ha Micimackó elárulta, hogy pozitív egészekre gondolt?

*c) És ha szorozni is lehet (azaz Malacka az xi-kből képezett bármilyen egész együtthatós polinom értékét is megkérdezheti, pl. mennyi x1+8x23x5)?

M9.1.2 Súlyok. Adott 13 súly. Akármelyiket is hagyjuk el, a maradék 12 darab beosztható két hatos csoportba úgy, hogy az egyes csoportokban levő súlyok összege megegyezik. Bizonyítsuk be, hogy mind a 13 súly egyenlő.

9.1.3 Igaz marad-e az előző feladat állítása akkor is, ha nem követeljük meg, hogy a két egyenlő súlyú csoportban azonos számú súly szerepeljen?

M*9.1.4 Unalmas vektorok.

a) Nevezzünk egy Rm-beli vektort unalmasnak, ha a koordinátái között legfeljebb két különböző érték fordul elő (azaz például minden koordinátája –1 vagy 2). Legkevesebb hány unalmas vektor összegeként állítható elő (i) 12m (ii) egy tetszőleges Rm-beli vektor?

b) Mi a helyzet, ha az unalmas vektor definícióját arra módosítjuk, hogy a koordinátái között legfeljebb k különböző érték fordulhat elő?

c) Megváltoznak-e az előzőkben kapott eredmények, ha a valós számok helyett az Fp modulo p testet vesszük?

Megjegyzés: a c) részben azért fogalmaztunk csak ilyen óvatosan, mert a (ii) kérdésnél nem látjuk, hogy az Fp testre vonatkozó minimumot hogyan lehetne minden esetre (azaz m és p bármely értékére) pontosan megadni.

M9.1.5 Vetélkedő.

a) Egy 32 fős osztály vetélkedősorozatot szervez. Minden fordulóban két csapat vetélkedik, tetszőleges létszámmal. Egy csapat állhat akár egy főből is, és nem szükséges, hogy minden diák minden fordulóban résztvegyen. Csak annyit követelünk meg, hogy a vetélkedősorozat folyamán bármely két diák legalább egyszer egymás ellenfele legyen (azaz legyen olyan forduló, amikor különböző csapatban szerepelnek). Legkevesebb hány fordulóban lehet a versenyt lebonyolítani?

*b) Mennyi a fordulók minimális száma, ha a versenyt úgy kell megrendezni, hogy bármely két diák pontosan egy alkalommal legyen egymás ellenfele?