Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9.4. Páratlanváros és Párosváros

9.4. Páratlanváros és Párosváros

Ebben a pontban azt vizsgáljuk, hogy egy k elemű halmaznak maximálisan hány olyan részhalmaza lehet, ahol az elemszámokra és a páronkénti metszetek elemszámára különféle feltételeket szabunk. Meglepő módon a feltételek minimális megváltoztatása az eredmény drámai megváltozását vonhatja maga után. Bevezetőként ezt az alábbi kis mesével illusztráljuk.

Hol volt, hol nem volt, az Óperenciás (Operációs?) tengeren túl, de a Nagy Prímszámtételen innen, Kombinatória kellős közepén volt egyszer egy icipici, 32 lakosú városka, amelynek a lakói imádtak egyesületeket alapítani. Kezdetben mindössze annyit kötöttek ki, hogy két egyesületnek nem lehet teljesen azonos a tagsága (hiszen akkor ez a kettő tulajdonképpen ugyanaz az egyesület, csak más néven). Még a „tagnélküli” egyesületet is bejegyezték, amelynek tehát senki sem tagja. (Ebben az egyesületben biztosan nem kerül sor éles vitákra!)

Szépen szaporodtak az egyesületek, mindenkinek több talicskányi tagkönyve volt már, azonban ettől a helyi nyomda kapacitása teljesen kimerült, és a polgárok rájöttek, hogy az egyesületek túlburjánzásának megakadályozására némi korlátozó intézkedéseket kell bevezetni. Két javaslat feküdt a nagytekintélyű szenátus előtt (amelynek természetesen mindenki tagja volt). Mindkét javaslat egyformán előírta, hogy ezentúl bármely két egyesületnek csak páros számú közös tagja lehet, és mindössze abban az apróságban mutatkozott eltérés, hogy emellett a Párosváros-pártiak azt akarták, hogy az egyesületek taglétszáma páros legyen, míg a Páratlanváros-pártiak a páratlan taglétszám mellett kardoskodtak. Mivel mindkét pártnak pontosan 16 képviselője volt a szenátusban, ezért nem tudván szavazással dönteni, segítségül hívták a szomszéd faluból a köztiszteletnek örvendő Lineáris Algebra apót, hogy mondjon véleményt. Az ő szavai most alább következnek.

9.4.1 Tétel (Páratlanváros)

Legyen |X|=k és H1,…, Hn olyan (különböző) részhalmazok X-ben, amelyekre mindegyik |Hj| páratlan és |HtHj| páros, ha tj. Ekkor max n=k.❶

9.4.2 Tétel (Párosváros)

Legyen |X|=k és H1,…, Hn olyan (különböző) részhalmazok X-ben, amelyekre mindegyik |Hj| páros és |HtHj| páros, ha tj. Ekkor maxn=2k/2

Eszerint a mesebeli Párosvárosban 216=65536 egyesület alapítható, míg Páratlanvárosban mindössze 32.

A két tétel bizonyítása közös alapelven működik: a valósban megismert skalárszorzat és merőlegesség fogalmát kiterjesztjük a modulo 2 test feletti vektorterekre, és a részhalmazoknak, valamint a metszeteiknek az elemszámát ennek segítségével fogjuk jellemezni.

Bizonyítás: Legyenek X elemei x1,…, xk és H tetszőleges részhalmaz X-ben. Feleltessünk meg H-nak egy k hosszúságú h_ vektort a következőképpen: h_-ban az i-edik komponens 1, ha xiH  és 0, ha xiH 

Legyen T=F2, ekkor h_-t tekinthetjük Tk-beli vektornak.

Definiáljuk Tk-ban a skalárszorzatot mint a koordináták szorzatösszegét (ugyanúgy, ahogy a valós test felett). Ez most is szimmetrikus bilineáris függvény lesz, csak a „pozitív definitségnek” persze nincs értelme, továbbá egy nemnulla vektor is lehet önmagára merőleges (lásd a 9.4.13–9.4.14 feladatokat).

Ha a H és H’ részhalmazoknak a h_ illetve h_' vektorok felelnek meg, akkor a h_h_' skalárszorzat HH’ elemszámát méri: annyi darab 1-est kell összeadni, ahány közös elem van H-ban és H’-ben. Ennélfogva h_h_' aszerint 0, illetve 1, hogy |HH’| páros, illetve páratlan. Ez speciálisan H=H’ esetén is igaz, azaz h_h_ aszerint 0, illetve 1, hogy |H| páros, illetve páratlan.

Térjünk most rá a Páratlanváros-tétel bizonyítására. Világos, hogy k darab ilyen Hj megadható, például az egyelemű részhalmazok megfelelnek a feltételnek. Most azt igazoljuk, hogy ennél több Hj már nem létezik. Ezt úgy látjuk be, hogy a Hj-knek megfeleltetett h_1,. . .,h_n vektorokról kimutatjuk, hogy lineárisan függetlenek. Mivel Tk-ban legfeljebb k darab lineárisan független vektor létezik, így valóban a kívánt nk egyenlőtlenséget kapjuk.

Vegyünk egy δ1h_1+. . . +δnh_n=0_ lineáris kombinációt. Ha mindkét oldalt skalárisan megszorozzuk h_j-vel, akkor δ1h_1h_j+. . .+δjh_jh_j+. . . +δnh_nh_j=0 adódik. Mivel |Hj| páratlan, de minden tj-re |HtHj| páros, ezért itt minden h_th_j skalárszorzat 0, kivéve h_jh_j-t, ami 1. Innen azonnal kapjuk, hogy δj=0. Mivel ez tetszőleges j-re teljesül, ezért a h_j vektorok valóban lineárisan függetlenek.

Rátérve a Párosváros-tétel bizonyítására, először lássuk be, hogy 2k/2 ilyen részhalmaz megadható. Megfelelő, ha k/2 darab (diszjunkt) elempárt veszünk, és az ezekből képezhető összes lehetséges halmazt tekintjük. (A mesebeli megfogalmazással, ha Párosvárosban 16 házaspár lakik, akkor bármely férj és feleség közösen lép vagy nem lép be egy egyesületbe.) Annak igazolása, hogy ez a maximum, további előkészületeket igényel.

Két V=Tk-beli vektor, a_ és b_ merőlegessége most is jelentse azt, hogy a skalárszorzatuk a_b_=0  továbbá egy U altérre legyen U az U összes elemére merőleges vektorok halmaza: U=x_Vu_Uu_x_=0

Könnyen adódik, hogy U altér, azonban a 8.1.7 Tétel megfelelője általában már nem igaz: előfordulhat, hogy UU0_ és U,UV  A dimU+dimU=dimV összefüggés viszont továbbra is érvényes. Mindezt a 9.4.15 feladatban tárgyaljuk.

Visszatérve Párosvárosba, legyenek H1,…, Hn olyan részhalmazok X-ben, amelyekre minden |Hj| és |HtHj| páros. Ez azt jelenti, hogy a Hj-knek megfelelő h_j vektorok ekkor önmagukra és egymásra is merőlegesek. Mivel (F2 felett) a_+b_a_+b_=a_a_+2a_b_+b_b_=a_a_+b_b_ így a h_j vektorok által generált U altérben bármely két vektor merőleges egymásra. Emiatt UU  tehát UU  és így a dimU+dimU=dimV összefüggésből dimUdimV/2=k/2 következik. Azaz valóban nU=2dimU2k/2  amint állítottuk.❷

Feladatok

9.4.1 Egy k elemű halmaznak hány olyan (különböző) részhalmaza van, amelyek elemszáma a) páros; b) 3-mal osztható?

9.4.2 Tekintsük a 9.4.1–9.4.2 Tételek bizonyításában bevezetett Hh_ megfeleltetést.

a) A H és H’ halmazok között milyen kapcsolat áll fenn, ha a h_ és h_' vektorok minden komponensükben különböznek?

b) A H és H’ halmazok között milyen műveletet kell elvégezni, hogy az így kapott halmaznak éppen a h_ és h_' vektorok (F2 feletti) összege feleljen meg?

9.4.3 Adjunk új bizonyítást a Páratlanváros-tételre az F2 test feletti függetlenség helyett a Q feletti függetlenségre támaszkodva.

9.4.4 Legyen |X|=k, H1,…, Hn (különböző) részhalmazok X-ben, és feleltessük meg a Hj-knek a h_1,. . .,h_n vektorokat a 9.4.1–9.4.2 Tételek bizonyításában látott módon. Ekkor azt a k×n-es A mátrixot, amelynek az oszlopai éppen a h_1,. . .,h_n vektorok, a H1,…, Hn halmazrendszer illeszkedési mátrixának (vagy incidenciamátrixának) nevezzük.

a) Mik lesznek a B=ATA szorzatmátrix elemei?

b) A fentiek felhasználásával adjunk még egy bizonyítást a Páratlanváros-tételre.

9.4.5 A k lakosú Páratlanvárosban a 9.4.1 Tétel feltételei szerint alapítanak k egyesületet. A lehetőségek számát jelöljük ξk-val. Lássuk be, hogy

a) ξk>1, ha k>3; b) ξk→∞, ha k→∞; *c) 2k2/8/k!<ξk<2k2/k! . 

9.4.6 Fordított Páratlanváros. Maximálisan hány egyesület alapítható a k lakosú Anti-Páratlanvárosban, ha itt bármely két egyesület közös tagjainak a száma páratlan, az egyesületek taglétszáma pedig páros?

9.4.7 Kalandozások Számországban.

a) Hármashatárnak k lakója van, az egyesületek taglétszáma nem osztható 3-mal, bármely két egyesület közös tagjainak a száma viszont igen. Maximálisan hány egyesület létezhet Hármashatárban?

b) Mi a helyzet Négyesföldön?

c) Mutassuk meg, hogy Hatfaluban nem alapítható 2k-nál több egyesület. Megjegyzés: Megoldatlan probléma, hogy egyáltalán k-nál több alapítható-e.

9.4.8

a) Legyen |X|=k, ahol 3|k. Maximálisan hány olyan Hj részhalmaz adható meg X-ben, amelyekre |Hj|≡2 (mod 3) és |HtHj|≡1 (mod 3), ha tj?

b) Oldjuk meg ugyanezt a feladatot 3  k esetén.

9.4.9 Színes Páratlanváros.

a) A k lakosú Piros-Kék Páratlanvárosban n darab Pj piros és ugyanannyi Kj kék egyesületet alapítanak az alábbi feltételekkel: |PjKj| páratlan minden j-re és |PtKj| páros, ha tj. Határozzuk meg n maximumát.

b) Mutassuk meg, hogy az eredmény akkor sem változik, ha |PtKj| párosságát (tj helyett) csak t<j-re követeljük meg.

M*9.4.10 Egyforma metszetek. Egy k elemű halmaznak maximálisan hány olyan részhalmaza lehet, amelyek közül bármelyik kettőnek pontosan egy közös eleme van?

9.4.11 Szigorú szabályok. Álszabadiban az egyesületalapítási szabályok a következők: (i) Kevesebb egyesület van, mint ahány lakos; (ii) bármely két lakos ugyanannyi (éspedig pozitív számú) egyesületnek közös tagja; (iii) minden egyesületnek legalább két tagja van, és két egyesületnek nem lehet teljesen azonos a tagsága. Hány egyesület működik Álszabadiban?

M**9.4.12 Korlátozott metszetek. Egy k elemű halmazban maximálisan hány olyan részhalmaz adható meg, amelyek páronkénti metszeteinek az elemszáma legfeljebb m-féle lehet (azaz tj-re a |HtHj| értékek között legfeljebb m különböző fordul elő, ahol mk egy rögzített nemnegatív egész)?

A 9.4.13–9.4.16 feladatokban legyen p egy pozitív prím, T=Fp, V=Tk és U altér V-ben. A V-beli skalárszorzatot, merőlegességet és U-t ugyanúgy definiáljuk, mint a p=2 esetben.

9.4.13 Kicsi alterek.

a) Legyen T=F2 és U olyan altér V-ben, amelyben csak a nullvektor merőleges önmagára. Bizonyítsuk be, hogy |U|≤2.

*b) Legyen p páratlan prím és T=Fp. Maximálisan hány eleme lehet V-ben egy olyan U altérnek, amelyben csak a nullvektor merőleges önmagára?

9.4.14 Izotrop vektorok.

a) Milyen p és k esetén létezik V-ben önmagára merőleges nemnulla vektor?

b) Milyen p és k esetén alkotnak az önmagukra merőleges vektorok alteret V-ben? Hány dimenziós ez az altér?

9.4.15 U és U 

a) Mutassunk példát arra, amikor U és U  illetve U,UV 

b) Bizonyítsuk be, hogy dimU+dimU=dimV

c) Igazoljuk, hogy UU=0_U,U=V

9.4.16 Belterjes merőlegesség. Vizsgáljuk meg, hogy létezik-e V-ben olyan U altér, amelyre U=U ha

a) p=2, k=10; b) p=5, k=11; c) p=13, k=30; d) p=23, k=2; e) p=43, k=20.

9.4.17 Új egyesületek.

a) A k lakosú Páratlanvárosban a 9.4.1 Tétel feltételei szerint n egyesület működik. Igaz-e, hogy ha az egyesületek száma nem maximális (vagyis n<k), akkor a rendszer bővíthető, azaz a meglevők mellé további egyesület is alapítható?

b) Mi a helyzet Párosvárosban?

M*9.4.18 Liberalizált Párosváros. Mutassuk meg, hogy páros k esetén akkor sem alapítható több egyesület Párosvárosban, ha a 9.4.2 Tétel feltételei közül a |Hj| párosságára vonatkozót elejtjük, és páratlan k esetén is mindössze eggyel növelhető ekkor az egyesületek száma.

9.4.19 Csupa Három. Egy 9 elemű halmazban maximálisan hány olyan Hj részhalmaz van, amelyekre mindegyik|Hj|és mindegyik |HtHj| is osztható 3-mal?