Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9. Kombinatorikai alkalmazások

9. Kombinatorikai alkalmazások

• 9.1.1 a) 20 kérdés nyilván elég, kevesebb viszont nem, még akkor sem, ha Micimackó előre elhatározza, hogy mindig 0-t fog válaszolni. Ekkor ugyanis egy 20 ismeretlenes, 19 egyenletből álló homogén lineáris egyenletrendszert kapunk. Ennek a csupa nulla megoldáson kívül van nemtriviális (racionális, és így egész számokból álló) megoldása is, tehát az xi-k nem határozhatók meg egyértelműen.

b) Két kérdés elég: (i) x1+x2+…+x20 , és ha erre a válasz N, akkor (ii) x1+x2(N+1)+x3(N+1)2+…+x20(N+1)19. Egy kérdés nem elég: legyen ez c1x1+c2x2+…+c20x20 , ahol pl. c1 és c2 mondjuk pozitív; ekkor x1=2c2 , x2=c1 , x3=…=1 és x1=c2 , x2=2c1 , x3=…=1 esetén ugyanazt a választ kapjuk.

c) Itt már egyetlen kérdés is elég. Tegyük fel először, hogy az xi-k pozitívak. Ekkor megfelel U=x1+(x1+x2)2+…+(x1+x2+…+x20)20. Ugyanis (x1+x2+…+x20)20<U<(1+x1+x2+…+x20)20 , ahonnan U huszadik gyökének egész része x1+…+x20 , ami ezzel ismertté vált és leválasztható. Az eljárást folytatva megkapjuk az x1+…+x19 stb. értékeket, és innen minden xi meghatározható. Ha xi negatív is lehet, akkor megfelel, ha az U-ra megadott fenti képletben xi helyére (3xi+1)2-t írunk.

• 9.1.2 Első bizonyítás:

(i) Először racionális számokra igazoljuk az állítást. Vegyük észre, hogy a számokat egy konstanssal beszorozva, vagy egy konstanst hozzájuk adva a feltételek nem változnak meg. Ezt felhasználva, pozitív egészekre a számok összege (vagy legnagyobbika) szerinti teljes indukcióval könnyen célhoz érünk. Ezután a racionális számok esetét beszorzással, majd eltolással a pozitív egészekre vezethetjük vissza.

(ii) Az általános esetre rátérve, tekintsük az adott 13 valós számot. Ezeknek a racionális számokkal képezett összes lineáris kombinációi egy legfeljebb 13-dimenziós vektorteret alkotnak a racionális számok felett a szokásos műveletekre. Vegyünk ebben egy bázist, és írjuk fel az eredetileg adott számainkat mint a báziselemek racionális együtthatós lineáris kombinációit. A feladat feltételei így azt jelentik, hogy ugyanezek a feltételek valamennyi komponensben teljesülnek. Mivel a báziselemek együtthatói már racionális számok, ezért az (i) rész alapján azt kapjuk, hogy a számaink valamennyi komponensben megegyeznek, azaz maguk is egyenlők.

Második bizonyítás: Legyenek a számok x1,x2,…,x13 . Alkalmas eltolás után feltehető, hogy x1=0. A feladat feltétele azt jelenti, hogy az xi-kből képezett bizonyos összegek megegyeznek. Ezeket felírva és átrendezve egy homogén lineáris egyenletrendszert kapunk, 13 egyenlettel és (x1=0 miatt csak) 12 ismeretlennel. A feladathoz azt kell megmutatnunk, hogy az egyenletrendszernek csak triviális megoldása létezik.

Az első bizonyítás (i) része alapján ez racionális számokra igaz. Belátjuk, hogy a valós számok körében sem kaphatunk más megoldást. Mivel az egyenletrendszer megoldása (Gauss-féle kiküszöbölés) során mindvégig az együtthatókkal csak a négy alapműveletet végezzük, tehát ugyanahhoz az eredményhez jutunk, akár a racionális, akár a valós számok körében keressük a megoldásokat, hiszen a kiindulási együtthatók racionálisak voltak (±1 és 0). (Vö. a 3.4.8, 4.4.11 és 4.6.16 feladatokkal.)

Harmadik bizonyítás: A 3.4.8, illetve 4.4.11 feladatok alapján elég azt igazolni, hogy a második bizonyításban leírt egyenletrendszernek a modulo 2 testben csak a triviális megoldása létezik. (Ebből ugyanis az említett feladatok bármelyike szerint már következik, hogy a valós számok körében sincs más megoldás.) Modulo 2 viszont az igazolandó állítás csak annyit mond ki, hogy ha a megfelelő hatos összegek paritása megegyezik, akkor mind a 13 szám azonos paritású, ez pedig nyilvánvaló.

Negyedik bizonyítás: A racionálisról a valósra történő átmenet eszköze most nem a(z elemi) lineáris algebra, hanem az elemi számelmélet lesz. Az adott valós számokat nagyon jól közelítjük majd racionálisokkal, és arra fogunk támaszkodni, hogy ezekre a közelítő törtekre már igaz az állítás.

Lemma: Tetszőleges x1,x2,…,xm valós számokhoz és N pozitív egészhez léteznek olyan a1,a2,…,am egészek és bNm természetes szám, amelyekre

A lemma bizonyítása: Minden 1≤tNm+1 egész számra készítsük el a v_t=tx1, . . . ,txm vektorokat, ahol * y=y-y  tehát {y} az y szám ún. törtrésze, azaz a hozzá balról legközelebbi egésztől mért távolsága. A skatulyaelv alapján lesz olyan ts, hogy a v_t és v_s vektorok bármely komponensében az eltérés legfeljebb 1/N. Beírva (*)-ot, így azt kapjuk, hogy valamilyen ai egészekkel és b=|s-t|-vel | bxi-ai|≤1/N teljesül minden i-re. Ez pedig éppen a lemma állítása.

A feladat bizonyításához alkalmazzuk a lemmát az adott xi valós számokra és N≥13-ra. A feladat feltételeiben szereplő egyenlőségekben az xi-k helyett a közelítő ai/b-ket írva, a két oldal eltérése a lemma alapján legfeljebb 12/(Nb)<1/b, de mivel mindkét oldalon b nevezőjű törtek állnak, így a két oldal csak egyenlő lehet. Vagyis a közelítő törtekre is teljesülnek a feladat feltételei. Ekkor tudjuk, hogy a közelítő törtek szükségképpen valamennyien egyenlők. Ugyanezt tetszőlegesen nagy N-ekre elvégezve adódik, hogy a valós számok is mind meg kell hogy egyezzenek.

• 9.1.4 a)/(i) Válasz: log2m Először megmutatjuk, hogy ennyi alkalmas összeadandó elég. Ha m nem kettőhatvány, akkor az i-edik összeadandó vektor j-edik koordinátája legyen rij2i-1 , ahol rij a j szám kettes számrendszerbeli felírásában hátulról az i-edik jegy 1ilog2m , 1jm  Ekkor mindegyik vektorban csak kétféle koordináta-érték fordul elő (hiszen rij=0 vagy 1). A vektorok összege valóban a kívánt vektor, ugyanis a j-edik koordináták összege éppen a j szám kettes számrendszer szerinti előállítása. Ha az m kettőhatvány, akkor a megadott z_=12m vektor helyett a 01m-1 vektorra készítsük el a fenti konstrukciót, majd valamelyik összeadandó vektor mindegyik komponenséhez adjunk hozzá 1-et.

Most belátjuk, hogy log2m -nél kevesebb összeadandó nem elég. Ha összeadunk t darab unalmas vektort, akkor az összegvektor minden koordinátája egy olyan t-tagú összeg, ahol minden tag (legfeljebb) kétféle értéket vehet fel. Ennélfogva egy ilyen összeg legfeljebb 2t-féle lehet, tehát az összegvektor koordinátái között legfeljebb ennyi különböző érték szerepel. A z_ vektorunknak mind az m koordinátája különböző, ezért ha t darab unalmas vektor összegeként előállítható, akkor szükségképpen 2tm, azaz tlog2m 

• a)/(ii) Válasz: m-1. Először megmutatjuk, hogy ennyi alkalmas összeadandó elég:

Most belátjuk, hogy m-1-nél kevesebb összeadandó nem elég. Ha egy vektor minden koordinátájához ugyanazt a számot hozzáadjuk, akkor nyilván mindkét vektor ugyanannyi unalmas vektor összegeként írható fel. Ezért elegendő olyan vektorok előállítását vizsgálni, amelyeknek az első koordinátája 0. Ezután hasonlóan igazolható, hogy az összeadandóként szereplő unalmas vektorokról is feltehetjük, hogy az első koordinátájuk 0. Tegyük fel, hogy minden v_=0β2β3βm vektor előáll t darab olyan u_j unalmas vektor összegeként, amelyek első koordinátája 0. A j-edik összeadandó többi koordinátája ekkor 0 vagy valamilyen xj valós szám. Az összegelőállítást koordinátánként felírva és az első koordinátára vonatkozó semmitmondó 0+0+…+0=0 azonosságot elhagyva, a többi m-1 koordinátára olyan t ismeretlenes, m-1 egyenletből álló egyenletrendszereket kapunk, amelyeknél (a „bal oldalon”) minden együttható 0 vagy 1 aszerint, hogy az illető u_j unalmas vektor adott koordinátája 0 vagy xj . (Az összes lehetséges együtthatóválasztásnak megfelelően az ilyen egyenletrendszerek száma 2t(m-1), illetve 2m-1+t-1t  ha az összeadandó vektorok sorrendje közömbös.) Ha minden v_ vektor előáll a kívánt módon, ez azt jelenti, hogy bármilyen β23,…,βm „jobb oldal” esetén legalább az egyik ilyen típusú egyenletrendszer megoldható. Ha t<m-1, azaz az ismeretlenek száma kisebb az egyenletek számánál, akkor egy ilyen egyenletrendszer nem lehet tetszőleges jobb oldal esetén megoldható, ezért azok a v_'=β2β3βm jobb oldalak, amelyekre megoldható, egy valódi alteret alkotnak Rm-1-ben. Véges sok valódi altér egyesítése nem adhatja ki a vektorteret (4.2.12e feladat), így azok a v_' jobb oldalak, amelyekre legalább az egyik ilyen egyenletrendszer megoldható, együttesen sem merítik ki Rm-1-et, azaz van olyan vektor, amely nem áll elő t darab unalmas vektor összegeként.

b) Válasz: (i): logkm (ii): m-1/k-1 (ha mk). A bizonyítás az imént látott k=2 eset mintájára történhet. Az (i) résznél k alapú számrendszert kell használni. A (ii) résznél az összeadandó unalmas vektorok mindegyikéhez nem 1, hanem k-1 ismeretlen tartozik, hiszen a 0-n kívül ennyiféle koordinátájuk lehet.

• c)/(i) Válasz: logks ahol s=min(m,p). Ez a korábbi meggondolásokhoz hasonlóan adódik, azzal a kiegészítéssel, hogy az ismétlődő koordináta-értékek nyilván nem számítanak.

• c)/(ii) A korábban látott gondolatmenet akkor alkalmazható, ha p ele-

gendően nagy m-hez képest (4.2.12f feladat). Kis p esetén azonban nem-

csak a módszerrel van baj, hanem a válasz is módosul: mivel logkp unalmas

vektor az (i)-beli konstrukció alapján mindenképpen elegendő, ezért

pk(m-k)/(k-1) esetén a keresett minimum biztosan kisebb lesz a valós számokra kapott m-1/k-1 értéknél.

• 9.1.5 a) Válasz: 5. Először megmutatjuk, hogy 5 forduló elég. Számozzuk meg a gyerekeket 0-tól 31-ig, és írjuk fel a sorszámokat kettes számrendszerben. Megfelelő lesz, ha az egyes fordulókban aszerint képezzük a (16 fős) csapatokat, hogy az 1.,2.,…,5. számjegy 0 vagy 1.

Most belátjuk, hogy kevesebb forduló nem elég. Feltehetjük, hogy minden fordulóban minden diák játszik (a pihenőket berakjuk akármelyik csapatba). Az első fordulóban valamelyik csapatban legalább 16-an vannak. Közülük a második fordulóban legalább 8-an ugyanabban a csapatban szerepelnek. Ezek közül a harmadik fordulóban legalább 4-en csapattársak, a negyedik fordulóban pedig legalább ketten, ők tehát egyszer sem voltak ellenfelek.

b) Könnyen látható, hogy 31 forduló elegendő; egy lehetséges lebonyolítás a következő. Az első fordulóban az egyik csapat egyetlen diákból áll, a másik csapat a többi 31-ből. A második fordulóban a 31 diákból egy alkotja az egyik csapatot, a többi 30 a másikat stb.

Most megmutatjuk, hogy 30 vagy kevesebb fordulóval a feltételeket nem lehet teljesíteni. Készítsünk egy 32 szögpontú teljes gráfot. A csúcsokat feleltessük meg a diákoknak, az i-edik csúcs mellé írjunk egy később alkalmasan megválasztandó xi valós számot, i=1,2,3,…,32, az i-edik és a j-edik csúcsot összekötő élre pedig írjuk az xixj szorzatot.

Tegyük fel indirekt, hogy 30 vagy kevesebb fordulóban lebonyolítható a verseny. Azt, hogy az i-edik és a j-edik tanuló (valamikor) egymás ellenfele, az őket összekötő élen levő xixj szorzattal hozzuk kapcsolatba.

Tekintsük az összes élen levő szorzatok S összegét.

Számoljuk most meg, hogy egy-egy fordulóban a szembenálló csapatok „mennyivel járulnak hozzá” az S összeghez: legyen St a t-edik fordulóban az „ellenfél” diákokat összekötő élekre írt xixj szorzatok összege. Mivel a verseny során bármely két diák pontosan egyszer lesz egymás ellenfele, így

ahol r a fordulók számát jelöli. Másrészt

ahol C1t , illetve C2t jelöli a t-edik forduló két csapatát, ugyanis egy adott fordulóban az egyik csapat minden tagja a másik csapat minden tagjának ellenfele, tehát minden olyan xkxl szorzatot össze kell adni, ahol k az első, l pedig a második csapatban szerepel.

Az (1), (2) és (3) képletek alapján az alábbi egyenlőséget kapjuk:

A (4) egyenlőség egy azonosság: az x1,x2,…,x32 értékek tetszőleges megválasztása mellett fenn kell állnia. Válasszuk most meg ezeket úgy, hogy

teljesüljön. Az (5) homogén egyenletrendszerben az ismeretlenek száma 32, az egyenleteké r+1, ami az indirekt feltevés szerint legfeljebb 31. Így az egyenletrendszernek van nemtriviális (valós) megoldása. Egy ilyen megoldást (4)-be behelyettesítve

adódik, ami ellentmondás, hiszen valós számok négyzetösszege csak akkor lehet 0, ha mindegyikük 0 volt.

Megjegyzés: Tulajdonképpen azt láttuk be, hogy ha egy n csúcsú teljes gráfot éldiszjunkt teljes páros gráfok uniójára bontunk, akkor minimálisan n-1 páros gráf szükséges ehhez. Ha azonban az élidegenség feltételét elejtjük, akkor ez a szám az a) rész gondolatmenete szerint log2n -re csökken.

• 9.2.16 Első megoldás: Az útmutatást követve, az olyan, n darab +1-ből és n-1 darab -1-ből álló sorozatok számát kell meghatároznunk, amelyekben az elejétől számítva akárhány tag összege pozitív. Ebből a szempontból nyilván rosszak a -1-gyel kezdődő sorozatok. A+1-gyel kezdődő rossz sorozatoknál keressük meg az első 0 részösszeget, és a sorozat addig terjedő elemeit szorozzuk meg -1-gyel. Ekkor egy -1-gyel kezdődő sorozatot kapunk. Megfordítva, bármely -1-gyel kezdődő sorozatnál keressük meg az első 0 részösszeget (ilyen biztosan van, hiszen a +1-ek száma nagyobb a -1-ek számánál), és a sorozat addig terjedő elemeit -1-gyel megszorozva egy +1-gyel kezdődő rossz sorozathoz jutunk. Ily módon tehát kölcsönösen egyértelmű megfeleltetést létesítettünk a +1-gyel kezdődő rossz sorozatok és a -1-gyel kezdődő („automatikusan” rossz) sorozatok között. Az összes rossz sorozatok száma ennélfogva a -1-gyel kezdődő sorozatok számának a duplája, azaz 22n-2n-2  Ezt az összes sorozatok számából levonva megkapjuk a „jó” sorozatok számát: 2n-1n-1-22n-2n-2=22n-2n-1/n 

Második megoldás: Az útmutatást követve, az Az=n=1αnzn hatványsorra az A2(z)=A(z)-z egyenletet kapjuk. Célunk az αn együtthatók meghatározása. Az A(z)-re vonatkozó egyenletet megoldva Az=-1±1-4z/2  Itt az (1-4z )1/2 kifejezést binomális sorba fejtve az Az=1±n=01/2n-4zn/2 összefüggés adódik. Itt a ∑ előtt a negatív előjelet kell venni (ez onnan látszik, hogy A(z) hatványsorában pl. a konstans tag 0, vagy onnan, hogy minden további αn együttható pozitív). A kétféle hatványsoralak összehasonlításából αn=1/2n4n-1n+1/2  amiből némi technikai átalakítás után αn=2n-2n-1/n  adódik.

Harmadik megoldás: Legyen βn az n szám lehetséges szorzatainak a száma, ha még a tényezők sorrendje is cserélődhet, ekkor βn=nn. Megmutatjuk, hogy (*) βn=(4n-6)βn-1 . Nézzünk az a1,a2,…, an-1 számokból egy tetszőleges szorzatot. Ez n-2 szorzást jelent. Az an számot megszorozhatjuk az első szorzás bármelyik tényezőjével balról vagy jobbról, a második szorzás bármelyik tényezőjével balról vagy jobbról stb., végül a kész szorzattal balról vagy jobbról, ez tehát 4(n-2)+2=4n-6 lehetőség az an+1 beillesztésére. Ezzel a (*) rekurziót beláttuk. Ennek ismételt alkalmazásával βn=2n-1(2n-3)!! adódik, ahonnan αn=2n-2n-1/n 

• 9.3.2 Tegyük fel indirekt, hogy a kongruenciarendszernek csak triviális megoldása van. Ekkor az

kongruencia azonosságként teljesül, ugyanis ha mindegyik xi≡0 (mod p), akkor mindkét oldal 1-gyel kongruens, minden más esetben pedig van olyan i, illetve j, hogy fi0,   xj0 azaz a kis-Fermat-tétel alapján fip-11,   xjp-11 vagyis mindkét oldalon szerepel egy 0 tényező, és így mindkét oldal 0-val kongruens. A két oldalon álló (a modulo p test feletti) F és G polinomnak tehát minden helyettesítési értéke megegyezik.

Nevezzük egy H polinom redukált alakjának azt a H* polinomot, amelyet H-ból úgy kapunk, hogy H-ban mindenhol xip helyére xi-t írunk, ameddig csak lehetséges. Nyilván H* minden tagjában bármelyik xi kitevője legfeljebb p-1, továbbá H és H* minden helyettesítési értéke megegyezik. A változók száma szerinti teljes indukcióval könnyen megmutatható, hogy ha a H* és K* polinomok minden helyettesítési értéke megegyezik, akkor a H* és K* polinomok (formálisan is) egyenlők.

Láttuk, hogy az F és G polinomok minden helyettesítési értéke megegyezik, ezért ugyanez érvényes az F* és G* polinomokra is. Az előzőek szerint ekkor az F* és G* polinomok meg kell hogy egyezzenek. Ez azonban lehetetlen, ugyanis G= G* és a i=1kdegfi<t feltétel miatt degG*=t(p-1)>

>degF≥degF* .

• 9.4.10 A keresett maximum értéke k. Többféleképpen is megadható k ilyen részhalmaz: Jelöljük a halmaz egyik elemét x1-gyel, ekkor megfelelnek pl. az x1-et tartalmazó egy- és kételemű részhalmazok, vagy itt az {x1} részhalmaz kicserélhető a komplementerére. Bizonyos k-kra további lehetőséget jelentenek az ún. (nem elfajuló) véges projektív síkok (lásd a Megjegyzést a megoldás végén). Arra, hogy k-nál több ilyen részhalmaz már nem adható meg, két bizonyítást mutatunk.

Első bizonyítás: Az útmutatást követve belátjuk, hogy a H1,…,Hn halmazoknak megfelelő h_1, . . . ,h_n szokásos 0-1 vektorok lineárisan függetlenek a valós test felett. A δ1h_1+ . . . +δ1h_n=0_ valós együtthatós lineáris kombinációnak önmagával való skalárszorzata átrendezés után a

összefüggést adja. Nemnegatív számok összege csak úgy lehet 0, ha minden összeadandó 0, továbbá a feltételek szerint legfeljebb egy kivétellel minden |Hj|>1. Innen kapjuk, hogy valóban mindegyik δj=0.

Második bizonyítás: Legyenek az X halmaz elemei az x1,x2,…,xk „pontok”. Egy xX pont fok án az őt tartalmazó Hj részhalmazok számát értjük: dx=jxHj 

Megmutatjuk, hogy xHjdxHj  Ha ugyanis xHt és xHi (ahol ti), akkor HtHjHiHj , ugyanis HtHi-nek x az egyetlen közös eleme. Ezért az x-et tartalmazó Ht-k mindegyike más pontot metsz ki Hj-ből, vagyis valóban d(x)≤|Hj|.

Ha indirekt feltesszük, hogy k<n, akkor bármely xHj -re a d(x)≤|Hj| egyenlőtlenségből

következik. Ezt az összes xHj párra összegezve xXdx<j=1nHj adódik, ami ellentmondás, hiszen itt a fokszám definíciója alapján nyilván egyenlőségnek kell állnia.

Megjegyzés: Mindkét bizonyításból (egymástól eltérő) további információkat is leolvashatunk. Az első bizonyítás átvihető arra az esetre is, ha bármely két részhalmaznak ugyanannyi (pozitív számú, de nem feltétlenül egyetlen) közös eleme van (ezt a gondolatmenetet kell a 9.4.11 feladat megoldásában felhasználni). A második bizonyításból pedig kiderül, hogyan kapjuk meg az n=k esetben a megfelelő halmazokat. Az (1)-beli bal oldali tört nevezője 0, ha x mind a k részhalmaznak közös eleme, ekkor az x-et tartalmazó egy- és kételemű részhalmazokról van szó (ez volt a megoldás elején felsorolt első példa). Ettől a triviális esettől eltekintve a törtek értelmesek, és ugyanúgy ellentmondásra jutunk, kivéve ha minden xHj párra d(x)=|Hj| teljesül. A Hj halmazokat egyeneseknek (az x elemeket pedig továbbra is pontoknak) nevezve ez azt jelenti, hogy bármely két ponton egy egyenes megy át, és bármely két egyenesnek egy közös pontja van. Ezek pedig éppen a véges projektív síkok (a megoldás elején felsorolt második példa egy elfajuló projektív síkot jelent, amikor a pontok egy kivételével egy egyenesre esnek).

• 9.4.12 Megfelel, ha vesszük az összes legfeljebb m elemű részhalmazt, ezek száma i=0mki  Belátjuk, hogy ez a maximum. Tekintsük a H1,…,Hn halmazoknak megfelelő h_1, . . . ,h_n szokásos 0-1 vektorokat, és legyen a tj párokhoz tartozó összes |HtHj|érték β1,…,βm .

Vegyük észre, hogy a feltétel alapján bármely tj-re a u=1mh_th_j-βu szorzat szükségképpen nulla. Definiáljuk ennek megfelelően a k-változós f1,…,fn valós együtthatós polinomokat a következőképpen: fjx_=u=1mx_h_j-βu  Ekkor fjh_t=0  ha tj, és így az fj-k lineáris függetlenségét kényelmesen be tudnánk látni, ha fjh_j0 is teljesülne. Ez azonban sajnos nem feltétlenül igaz, ezért a konstrukciót egy kicsit finomítani kell.

A problematikus fjh_j=0 feltétel azt jelenti, hogy |Hj| megegyezik valamelyik βu-val. Ezért ezt a(z esetleges) tényezőt hagyjuk ki, vagyis legyen gj azoknak az x_h_j-βu tényezőknek a szorzata, ahol βu≠|Hj|. Feltehetjük, hogy |H1|≤|H2|≤…≤|Hn|, ekkor nyilván

A gj-k lineárisan függetlenek a valós test felett, mert a j=1nλjgj=0 polinom egyenlőségbe h_1, . . . ,h_n -et ebben a sorrendben egymás után behelyettesítve rendre kapjuk, hogy λ1=…=λn=0.

Valamennyi gj egy k-változós legfeljebb m-edfokú polinom, így a függetlenség miatt számuk legfeljebb annyi, mint ennek a térnek a dimenziója. Ez sajnos még mindig nem adja ki a kívánt becslést, azonban a következő észrevétellel ezen is segíteni tudunk. A polinomokba csak a h_j vektorokat kellett behelyettesíteni, és ezek minden koordinátája 0 vagy 1. Mivel 02=0,12=1, ezért a helyettesítési értékek ugyanazok maradnak, ha a változók magasabb hatványait az első hatványra redukáljuk, azaz elég, ha minden változó csak az első hatványon szerepel.

Legyen ennek megfelelően (j=1,2,…,n-re) Gj az a polinom , amelyet gj-ből úgy kapunk, hogy minden egyes xs változónál xs2 helyére xs-et írunk, amíg ez csak lehetséges. Ekkor az előbbiek szerint Gjh_t=gjh_t minden t,j-re. Ennélfogva a fenti gondolatmenetet a gj-k helyett a Gj-kre alkalmazva kapjuk, hogy a Gj-k is függetlenek. Másrészt a Gj-k benne vannak az 1,x1,…,xk,x1x2,…,xk-1xk,x1x2x3,…,x1x2xm,… polinomok által generált altérben. A generátorelemek száma i=0mki  tehát a dimenzió, és így (a lineáris függetlenség miatt) a Gj-k száma is legfeljebb ennyi.

• 9.4.18 Legyenek S1,…,Sb, illetve T1,…,Tc a páros, illetve páratlan elemszámú részhalmazok (b+c=n). A feltétel szerint bármely két (különböző) részhalmaz metszete páros elemszámú. Ekkor az Sj, illetve Ti halmazoknak megfelelő s_j  illetve t_i szokásos 0-1 vektorok páronként merőlegesek, sőt az s_j -k önmagukra is merőlegesek (az F2 testet használjuk). Legyen az s_j -k, illetve a t_i -k által generált altér Us, illetve Ut, és ezek dimenziója s, illetve t. A Páratlanváros-tétel bizonyítása szerint a t_i vektorok függetlenek, ezért t=c, továbbá nyilván b≤ 2s, tehát n=b+ct+ 2s.

Megmutatjuk, hogy UsUt=0_  Legyen x_ UsUt  azaz x_=j=1bλjs_j=i=1cμit_i  Vegyük mindkét oldalnak a skalárszorzatát

t m -mel, ekkor μm=0 adódik. Mivel ez minden m-re igaz, ezért valóban x_=0_ 

A feltételek szerint Us,UtUs  így s+t=dimUs,Utk-s  azaz sk-t/2  Innen

Végül, a felső korlát megvalósulását páros k-ra a 9.4.2 Tétel bizonyításában látott „házaspáros” konstrukció biztosítja, páratlan k-ra pedig a hasonlóan adódó részhalmazok mellé hozzávehetjük pl. magát az egész X-et (azaz az összes lakost magában foglaló egyesületet).

• 9.5.5 I. Az útmutatást követve először azt igazoljuk, hogy ha f(A)=J, akkor A minden sajátvektora J-nek is sajátvektora. Ez azonnal adódik a sajátvektor definíciójából.

II. Tegyük most fel, hogy A minden sajátvektora J-nek is sajátvektora. Megmutatjuk, hogy ekkor G reguláris és összefüggő. Mivel A sajátvektorai kifeszítik a teret, ezért az A egyik sajátvektora a j_ kell hogy legyen. Ha az ehhez tartozó sajátérték d, akkor G minden csúcsa d-ed fokú, tehát G reguláris.

Ha G nem lenne összefüggő, akkor jelöljük az egyik komponensét G1-gyel, és legyen u_ az a vektor, amelynek az i-edik koordinátája ui=1, illetve 0 aszerint, hogy az i-edik csúcs benne van-e a G1 komponensben vagy sem. Ekkor u_ sajátvektora A-nak (ugyancsak d sajátértékkel), azonban nem sajátvektora J-nek. Ezzel beláttuk, hogy G valóban összefüggő is.

III. Végül tegyük fel, hogy G reguláris és összefüggő, ekkor meg kell adnunk olyan f polinomot, amelyre f(A)=J. A regularitás miatt j_ sajátvektora az A-nak d sajátértékkel. Legyen j_ , v_2, . . . ,v_n az A ortogonális sajátvektoraiból álló bázis és d2,…,λn a megfelelő sajátértékek. Ekkor v_ij_  és így Jv_i=0_ minden 2≤in esetén.

Megmutatjuk, hogy a d csak egyszeres sajátértéke az A-nak. Tekintsünk egy d-hez tartozó x_ sajátvektort és ebben a(z egyik) legnagyobb komponenst. Vizsgáljuk az ehhez tartozó csúcsot és annak a d darab szomszédját; az egyszerűbb jelölés kedvéért tegyük fel, hogy ezek éppen az első d+1 csúcs. Ekkor (amint a 9.5.2 feladatban láttuk) d·x1=x2+…+xd+1d·x1, ahonnan kapjuk, hogy x1=x2=…= xd+1. Ugyanezt a gondolatmenetet most az x1 helyett az x2,…,xd+1-vel megismételve stb., a gráf összefüggőségét kihasználva adódik, hogy minden xi egyenlő, tehát az x_ valóban csak a j_ skalárszorosa lehet.

Legyen f olyan (interpolációs) polinom, amelyre f(d)=n és f2)=

=…=fn)=0 (itt felhasználjuk, hogy d≠ λi). Ekkor fAj_=fdj_=nj_   és   fAv_i=fλiv_i=0_  tehát fA  a  j_ , v_2, . . . ,v_n báziselemeket ugyanoda képezi, mint a J, ennélfogva valóban f(A)=J.

• 9.5.10 Az útmutatást követve először az (i) állítást igazoljuk. Legyen A nemnegatív elemű szimmetrikus mátrix, Λ a legnagyobb sajátértéke, x_0_ ,x_0_  és Ax_τx_  Legyen továbbá b_1, . . . ,b_n ortonormált sajátbázis, λ1,…,λn a megfelelő sajátértékek és x_=i=1nξib_i  Feltehetjük, hogy x_ normált, azaz x_ x_=i=1nξi2=1  Ekkor

Ezzel (i)-et beláttuk. Ennek felhasználásával (ii) a következőképpen igazolható. Legyen z_ az A’ mátrixnak egy, a Λ’ maximális sajátértékhez tartozó sajátvektora, A'z_=Λ'z_  Feltehetjük, hogy z_ -nek pl. az első koordinátája pozitív. Hagyjuk meg z_ nemnegatív koordinátáit, és a(z esetleges) negatív koordináták helyére írjunk 0-t, az így kapott (nemnegatív) vektor legyen x_  Könnyen láthatóan Ax_A'x_Λ'x_   és így (i) alapján valóban Λ≥Λ’.

Rátérünk a(z eredeti) feladatnak a csúcsok száma szerinti teljes indukciós bizonyítására. Legyen k=Λ+1, meg kell mutatnunk, hogy a gráf k színnel kiszínezhető. Ha csak egy csúcs van, akkor az egyetlen sajátérték a Λ=0, tehát k=Λ+1=1, és egy szín nyilván elég. Vegyünk most egy n csúcsú G gráfot, és hagyjuk el a(z egyik) legkisebb fokszámú csúcsot a hozzá tartozó élekkel. Az elhagyott csúcs foka a 9.5.9 feladat szerint ≤Λ=k-1. A megmaradó G1 gráfhoz vegyük hozzá az elhagyott csúcsot izolált pontként, az élek nélkül, az így kapott gráfot jelöljük G’-vel. Könnyen adódik, hogy a G1 és G’ gráfok maximális sajátértéke ugyanaz (sőt a 0 sajátértéktől, illetve annak multiplicitásától eltekintve valamennyi sajátérték azonos). A G’ gráf maximális sajátértékét Λ’-vel jelölve a (ii) állítás alapján kapjuk, hogy Λ’≤Λ, ezért az indukciós feltétel szerint G1 kiszínezhető legfeljebb Λ’+1≤Λ+1=k színnel. Mivel az elhagyott csúcsnak legfeljebb k-1 szomszédja volt, ezért a k szín között biztosan van olyan, amelyet ezeknek a szomszédoknak a színezésére nem használtunk fel, tehát a G1-nek ez a színezése kiterjeszthető G megfelelő színezésévé.

• 9.6.3 Tekintsük a p2 elemű T2 véges testet és ebben a p elemű T1 résztestet. Mivel egy véges test multiplikatív csoportja ciklikus, így van T2-nek olyan Δ eleme, amelynek a hatványai T2 minden nemnulla elemét előállítják.

Vegyünk egy tetszőleges T2 \ T1 elemet, és legyenek T1 elemei

γ1,…,γp. Írjuk fel a Θ+γi elemeket Θ+γiai alakban, ezzel kijelöltünk p darab ai egész számot 1 és p2-1 között.

Megmutatjuk, hogy ezek eleget tesznek a feltételnek, azaz az ai+aj összegek páronként különböző maradékot adnak modulo p2-1.

Tegyük fel, hogy ai+ajak+al (mod p2-1). Ekkor az ai-k definíciója alapján (Θ+γi)(Θ+γj)-(Θ+γk)(Θ+γl)=0 adódik.A bal oldal Θ-nak legfeljebb elsőfokú polinomja T1-beli együtthatókkal, hiszen Θ2 kiesik. Elsőfokú azonban nem lehet, mert akkor ΘT1 következne, így — mivel a Θ gyöke — csak az azonosan nulla polinom lehet. Ekkor azonban pl. a polinomok gyöktényezős alakjának az egyértelműsége miatt {γij}={γkl}, és így ugyanez áll az ai-kre is, ami éppen a bizonyítandó állítás volt.

• 9.6.4 Az útmutatást követve vegyünk egy g primitív gyököt modulo p, és legyen ai az x≡i (mod p-1), xgi (mod p) szimultán kongruenciarendszer megoldása modulo p(p-1),i=1,2,…,p-1. Nyilván elég azt megmutatnunk, hogy bármely c-re a c≡ai+aj ( mod p(p-1) )kongruencia legfeljebb egyetlen {i,j}-vel teljesülhet. Az ai definíciója alapján ez a kongruencia a ci+j (mod p-1), cgi+gj (mod p) szimultán kongruenciarendszerrel ekvivalens. Itt az első kongruencia átírható a gcgigj (mod p) alakba, vagyis a gi és gj számok összegét és szorzatát is ismerjük modulo p. A gyökök és együtthatók közötti összefüggés alapján a gi és gj maradékosztályok a z2-cz+gc≡0 (mod p) másodfokú kongruencia egyértelműen meghatározott gyökei (p prím), és így i és j is egyértelmű.

• 9.6.7 c) Legyen Z=i=1sai és tekintsük azt az η valószínűségi változót, amely a (különböző) ai-kből képezett 2s darab ui összeg mindegyikét 2-s valószínűséggel veszi fel (az ui-k között szerepel a 0 és a Z is). A várható érték E(η)=Z/2, ugyanis az ui-k összepárosíthatók úgy, hogy az egy párban levő ui-k összege Z legyen. A szórás kiszámításához vezessük be a ξi,i=1,2,…,s valószínűségi változókat: ξi az ai, illetve 0 értéket 1/2-1/2 valószínűséggel veszi fel. Ekkor a ξi változók függetlenek és összegük éppen η, tehát a szórásnégyzetre

adódik. Alkalmazzuk most a Valószínűség (|η-E(η)|≥cD(η))≤c-2Csebisev-egyenlőtlenséget az E-re és D-re kapott fenti értékekkel és c=2-vel. A számolást elvégezve azt kapjuk, hogy a 2s darab (csupa különböző) ui összeg legalább háromnegyed része a Z/2-re szimmetrikus 2ns hosszúságú intervallumba esik. Ezért szükségképpen 32s/4<2ns [tehát a b)-beli hasonló becsléshez képest lényegében a jobb oldal változott s helyett s-re]. A kapott egyenlőtlenséget egymás után kétszer logaritmálva

illetve log2s≤1+log2log2n adódik. Írjuk be ez utóbbit (1)-be log2s helyére, ekkor a feladat állításához jutunk.

• 9.6.9 Az útmutatást követve tekintsük azokat a számokat n-ig, amelyeket a d alapú számrendszerben felírva minden számjegy <d/2 és a számjegyek négyzetösszege egy adott q érték. Ha három ilyen szám számtani sorozatot alkot, akkor minden számjegyükre ugyanez áll fenn, mert a jegyekre adott korlátozás miatt két szám összeadása során sohasem képződik átvitel a következő helyiértékre. Így a középső szám valamennyi jegye a másik két szám megfelelő jegyeinek számtani közepe. Felírva, hogy mindhárom szám jegyeinek négyzetösszege q, egyszerű számolással adódik, hogy a számok szükségképpen egyenlők. (Más megfogalmazásban: ha a három számot a számjegyeikből alkotott vektoroknak tekintjük, akkor a harmadik vektor az első kettő összegének a fele, továbbá mindhárom vektor euklideszi normája egyenlő. Ez csak úgy lehet, ha maguk a vektorok is megegyeznek.)

Adott d mellett a felírásban szereplő számjegyek száma u≈(logn)/(logd), és q-nak legfeljebb ud2/4-féle értéke lehet. Ha a halmazainkat minden lehetséges q-ra egyesítjük, akkor az összes olyan számot megkapjuk, amelyek valamennyi jegye d/2-nél kisebb. Ez összesen kb. n/2u szám. Ezért biztosan van olyan q, amelynek megfelelő halmaz elemszáma legalább n/(2u-2ud2). Ez akkor veszi fel a maximumát ha logdlogn  és ez a maximum éppen a tétel állításában előírt érték.

• 9.6.10 Első megoldás: Legyen h tetszőleges. Egy adott n-re az 1,2,…,n számokat 2n-féleképpen színezhetjük ki két színnel. Számoljuk most meg azokat a színezéseket, amelyeknél előfordul h-tagú egyszínű számtani sorozat (h-ESZ). Ha egy h-ESZ kezdőtagja j, akkor a differenciája legfeljebb n-j/h-1  azaz az ilyen sorozatok száma legfeljebb

Egy h-ESZ színe kétféle lehet, a többi szám színezése pedig 2n-h-féle. Ennélfogva összesen legfeljebb n22n-h/(h-1) színezésnél fordulhat elő h-ESZ (persze így számos rossz színezést többszörösen is megszámoltunk). Ezért, ha n22n-h/(h-1)<2n, azaz n<2h/2h-1  akkor biztosan van olyan színezés, amelyben nem fordul elő h-ESZ.

Második megoldás: Az útmutatást követve tekintsük a p prímmel a 2p elemű T véges testet, legyen Δ a multiplikatív csoport generátoreleme és W egy p-1-dimenziós altér T-ben (mint F2 feletti vektortérben). A színezés: k akkor piros, ha ΔkW  Megmutatjuk, hogy az1,2,…,p(2p-1) számokat ily módon kiszínezve nem fordul elő p+1-tagú egyszínű számtani sorozat.

Tegyük fel indirekt, hogy az 1≤b<b+d<b+2d<…<b+pd

p(2p-1) számok mind azonos színűek. Legyen Θ=Δb,Ψ=Δd A feltétel szerint ekkor a Θ,ΘΨ,…,ΘΨp „vektorok” vagy valamennyien a W altérbe esnek, vagy pedig egyikük sem esik W-be.

Ha a számtani sorozat piros, akkor tehát ezek a vektorok egy p-1-dimenziós altér elemei. Ezért közülük már az első p darab is lineárisan összefüggő, azaz alkalmas γiF2 együtthatókkal i=0p-1γii=0 nemtriviálisan teljesül. Az egyenlőséget Θ-val elosztva azt kapjuk, hogy Ψ gyöke egy p-nél alacsonyabb fokú F2 feletti polinomnak. Mivel Ψ foka osztója T fokának, vagyis p-nek, ezért Ψ foka csak 1 lehet, azaz F2  Ez azonban ellentmondás, hiszen nyilván Ψ≠0 és d<2p-1 miatt Ψ≠1.

Ha a számtani sorozat kék, akkor a ΘΨ-Θ,ΘΨ2-ΘΨ,…,Θ Ψp-Θ Ψp-1

vektorokra kell megismételni az előző gondolatmenetet (csak Θ helyett most

Θ(Ψ-1)-gyel kell a megfelelő egyenlőséget elosztani).

További megoldások: Közvetlen számolással igazolható, hogy az útmutatásoknál jelzett további három konstrukció is megfelel a feladat feltételeinek.

Megjegyzés: Az egyes megoldások „hatékonyságát” összevetve a következőket állapíthatjuk meg. Az első megoldás semmilyen értelemben nem ad konstrukciót, a számtani sorozat tagszáma tetszőleges h lehet, és durván az n<2h/2h korlátig alkalmazható. A második megoldás sem „igazi” konstrukció, továbbá itt a h speciálisan csak p+1 lehet (természetesen a prímek sűrű elhelyezkedése alapján valamivel gyengébb eredmény a többi h-ra is nyerhető), az n-re kapott korlát viszont jobb, az előzőnek durván a négyzete. A további három megoldás „igazi” konstrukciót biztosít, ugyanakkor nagy h esetén kisebb n-ig lesz használható. A harmadik megoldás a következőképpen általánosítható: a 7 és a 17 helyett egy h, illetve h/2 körüli prímet prímet kell venni, és ekkor kb. n=h3/2-ig jó a színezés. A negyedik megoldás nagy h-ra történő általánosításánál a h és 2h prímekkel dolgozhatunk, és kb. n=eh -ig jó a színezés. Az ötödik megoldásnál az általános esetben 2h3 körüli korlát adódik n-re. Ebből látszik, hogy nagy h esetén az első két megoldás lényegesen nagyobb n-ekre biztosítja a megfelelő színezés létezését, mint a másik három konstrukció.

• 9.7.7 a) Utalunk az útmutatásra és csak az ott „észrevételnek” nevezett állítás bizonyítását részletezzük. Legyenek tehát egy H háromszög szögei a racionális test felett lineárisan függetlenek. Azt kell igazolnunk, hogy H csak úgy bontható fel hasonló háromszögekre, ha azok H-hoz is hasonlók, továbbá ekkor H felbontásánál a kis háromszögek H szögeit nem vághatják el. Legyenek a kis háromszögek szögei α123, ekkor H szögei i=13kiαi alakúak valamilyen nemnegatív egész ki-kkel. Összeadva H szögeit π=i=13miαi adódik. Ha itt pl. m1=0, akkor H mindhárom szöge kifejezhető α2 és α3 lineáris kombinációjaként, ami ellentmond annak, hogy H szögei lineárisan függetlenek. Ha mindegyik mi≥1, akkor π=i=13αi miatt csak mi=1 lehetséges, vagyis H szögei is α123, tehát H valóban hasonló a kis háromszögekhez. Azt is kaptuk, hogy H felbontásánál a kis háromszögek H szögeit nem vághatják el.

• b) Az útmutatásban jelzett állításokat igazoljuk. Legyen H olyan háromszög, amelyben mind a szögek, mind pedig az oldalak lineárisan függetlenek a racionális test felett. Tegyük fel, hogy n nem négyzetszám, azaz n irracionális, és H-t mégis fel lehet bontani n egybevágó K kis háromszögre.

Az a) részben láttuk, hogy ekkor a szögek függetlensége miatt K szükségképpen hasonló H-hoz. Legyenek a K, illetve H háromszögek oldalai a1,a2,a3, illetve A1,A2,A3. Ekkor egyrészt Ai=ain  másrészt Ai=j=13kijaj  ahol a kij-k nemnegatív egészek. Ez azt jelenti, hogy a1,a2,a3 egy nemtriviális megoldása a

homogén lineáris egyenletrendszernek. Ezért az

együtthatómátrix rangja r(A)<3. Továbbá n irracionalitása miatt az első két sor csak úgy lehet egymás skalárszorosa, ha k13=k23=0, ekkor viszont a harmadik sor és az első sor nem skalárszorosok, tehát r(A)>1. Emiatt r(A)=2, tehát az egyenletrendszer megoldásában egyetlen szabad paraméter van. Legyen ez pl. a3 és válasszuk a3 értékét 1-nek. Ekkor a1 és a2 is c+dn alakú lesz, ahol c és d alkalmas racionális számok. Így mindhárom ai benne van az 1, n kétdimenziós altérben, ami ellentmond annak, hogy az ai oldalak lineárisan függetlenek voltak.

Meg kell még mutatnunk, hogy valóban létezik olyan háromszög, amelyben mind a szögek, mind pedig az oldalak lineárisan függetlenek. Az utóbbi feltétel a szinusztétel alapján ekvivalens azzal, hogy a szögek szinuszai függetlenek. Belátjuk, hogy ha egy háromszögben az egyik szög szinusza egy 0,±1/2,±1-től különböző racionális szám, egy másik szög szinusza pedig transzcendens, akkor mind a szögek, mind pedig a szinuszaik lineárisan függetlenek a racionális test felett.

Fel fogjuk használni, hogy ha sinγ algebrai, akkor tetszőleges s racionális számra sin(sγ) is algebrai. Valóban, mivel sinγ algebrai, ezért cosγ=±1-sin2γ is az, ennélfogva z =cosγ+isinγ is algebrai. Mivel egy algebrai szám minden racionális kitevőjű hatványa is algebrai, tehát zs és így annak képzetes része, azaz sin(sγ) is algebrai. Hasonlóan adódik, hogy ha sinγ1 és sinγ2 mindketten algebraiak, akkor sin(γ1+ γ2 ) is algebrai. (Összefoglalva, azok a szögek, amelyek szinusza algebrai, alteret alkotnak a valós számoknak a racionális test feletti szokásos vektorterében.)

Ezen előkészületek után tekintsünk egy olyan háromszöget, amelyben sinα1=r,sinα2=t, ahol r egy 0,±1/2,±1-től különböző racionális, t pedig tetszőleges transzcendens szám. Először a szögek függetlenségét igazoljuk. Indirekt tegyük fel, hogy az α12 és α3=π-(α12) szögek egy nemtriviális racionális együtthatós kombinációja nulla. Ezt átrendezve r0π+r1α1=r2α2 adódik, ahol az ri-k racionális számok és nem mindegyik nulla. Itt az előrebocsátott megjegyzés szerint a bal oldal szinusza algebrai, ugyanakkor a jobb oldalé r2≠0esetén transzcendens. Így szükségképpen r2=0. Ez azonban azt jelentené, hogy α1/π racionális, ami a 9.7.2b feladat szerint lehetetlen. Ez az ellentmondás igazolja, hogy az αi szögek valóban függetlenek.

Most rátérünk a szinuszok függetlenségének az igazolására. Indirekt tegyük fel, hogy sinα1,sinα2 és sin α3=sinα1 cosα2+cosα1 sinα2 lineárisan összefüggők. Mivel a feltétel szerint sinα2/sinα1 irracionális (sőt transzcendens), ezért az összefüggőség csak úgy teljesülhet, ha sinα1 cosα2+cosα1 sinα2=r1 sinα1+r2 sin α2, ahol az ri-k racionális számok. Ezt átrendezve sinα1(cosα2-r1)=sinα2(-cosα1+r2) adódik. Emeljük mindkét oldalt négyzetre, írjunk sin2α2 helyére 1-cos2α2-t, és rendezzünk cosα2 hatványai szerint. Itt cos2α2 együtthatója sin2α1+(r2-cosα1)2≠0. Így azt kaptuk, hogy cosα2 gyöke egy olyan másodfokú egyenletnek, amelynek az együtthatói algebrai számok. A másodfokú egyenlet megoldóképletéből ekkor cosα2-re is algebrai szám adódik, így sinα2 is algebrai, ami ellentmond a feltételnek.

• c) Ha n=k2, akkor egy tetszőleges háromszög minden oldalát k egyenlő részre osztva nyilván megfelelő felbontást kapunk. Ha n=k2+m2 (ahol k,m>0), akkor vegyünk egy olyan derékszögű háromszöget, amelynek a befogói k és m, és húzzuk meg az átfogóhoz tartozó magasságot. Ekkor két, az eredetihez hasonló derékszögű háromszöget kapunk, amelyek átfogói k, illetve m. A kapott két háromszög oldalait k, illetve m egyenlő részre osztva fel tudjuk bontani őket k2, illetve m2 olyan, az eredetihez hasonló kis háromszögre, amelyek átfogója egységnyi, és így a kis háromszögek egybevágók. Ezzel az eredeti háromszöget valóban n=k2+m2 megfelelő kis háromszögre bontottuk. (Speciálisan, ha k=m, akkor egyenlő szárú derékszögű háromszöget kell venni.)

Ha n=3k2, akkor a következő konstrukció lesz megfelelő. Húzzuk be egy S szabályos háromszög súlyvonalait, ezek S-et 6 darab egybevágó derékszögű háromszögre bontják, amelyek másik két szöge 30 és 60 fokos. Ugyanilyen az S „egyik felét” alkotó F háromszög is. Ezért F felbontható 3 darab egybevágó és hozzá hasonló háromszögre. Ezután a három háromszög mindegyikét a szokásos eljárással egyenként k2 részre vágva F-et valóban n=3k2 megfelelő kis háromszögre bontottuk.