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

7. A feladatok megoldásvázlatai

7. A feladatok megoldásvázlatai

(2) Az eredmény 2 n , a szavak u k és g u k , ahol 0 ? k //<// n (itt u k azt jelenti, hogy u -t leírjuk k -szor). A bizonyításhoz szabályos n -szöget érdemes tekinteni.

(1.3) Általánosítható megoldást mutatunk! Az egyszerűbb jelölés végett a - helyett egyenlőségjelet írunk a szavak közé, és 1-gyel jelöljük az üres szót. Ekkor g 4 g = 1 , és ezért g 4 -t a g inverzének nevezzük, és g - 1 -et írunk helyette. Hasznos bevezetni tetszőleges p szó esetén az f ( p ) = g - 1 p g jelölést (ezt konjugáltnak szokás hívni). Vegyük észre, hogy f ( p q ) = f ( p ) f ( q ) , mert középen kiesik a g . Ha egy p szót ötször konjugálunk g -vel, akkor p -t kapjuk vissza, mert g 5 = 1 .

Az u g = g u 2 szabály azt fejezi ki, hogy f ( u ) = u 2 . Kétszer konjugálva g -vel az eredmény f ( f ( u ) ) = f ( u 2 ) = f ( u ) f ( u ) = u 4 . Hasonlóan látjuk, hogy ötször konjugálva g -vel u 32 adódik. Vagyis u 32 = u , ahonnan u 2 -tel szorozva u = 1 . Tehát az u minden szóból elhagyható. Így összesen öt szó marad: g hatványai (amik mind különböznek).

(5) Az a , b , c betűket, az u , v , w , s , t szavakat jelöl. Legyen B ( w ) a w szóban előforduló betűk halmaza. Belátjuk, hogy ha B ( w ) ? B ( s ) = B ( t ) , akkor s w t = s t .

Bármilyen u , v , w szavakra

( u v w ) v ( u v w ) = u v w v u ( v w ) ( v w ) = = ( u v w v ) ( u v w v ) w = u ( v w ) ( v w ) = u v w .

Speciálisan ha a b betű szerepel egy s szóban, akkor s b s = s . Ha w = u v , és már tudjuk, hogy s u s = s v s = s , akkor s w s = ( s v s ) w ( s u s ) = s ( v s u ) ( v s u ) s = s v s u s = ( s v s ) ( s u s ) = s . Ezért ( w hossza szerinti indukcióval) látjuk, hogy ha B ( w ) ? B ( s ) , akkor s w s = s . Így pedig ha B ( w ) ? B ( s ) = B ( t ) , akkor az előző miatt t s t = t és s ( w t ) s = s , és ezért s w t = s w ( t s t ) = ( s w t s ) t = s t .

Az állítást a betűk m száma szerinti indukcióval igazoljuk. Tegyük fel, hogy a nyelvben legfeljebb N //<// ? olyan különböző jelentésű szó van, ami legfeljebb m - 1 betűt használ. Nyilván minden w szó felírható w = u b v alakban, ahol u -ban még nincs b betű, de már B ( u b ) = B ( w ) . Ugyanígy w = u ' c v ' , ahol c ? B ( v ' ) , de B ( c v ' ) = B ( w ) (lehet, hogy b = c , vagy u ' = u , vagy v ' = v ). Az imént bizonyított állítás miatt ekkor w = w w = ( u b ) v u ' ( c v ' ) = u b c v ' . Itt az u és a v ' szavakban legfeljebb m - 1 betű van, tehát a szavak száma legfeljebb N 2 m 2 .

(6) Belátjuk, hogy ha u , v , w szavak, akkor ( u 2 w u ) ( v 2 w v ) = ( v 2 w v ) ( u 2 w u ) (azaz w bármely két konjugáltja felcserélhető). Valóban, tetszőleges s és t szavak esetén ( s t 2 ) 3 = 1 , ezt jobbról t s 2 t -vel beszorozva ( s t ) ( t s ) = ( t s ) ( s t ) adódik, tehát s t és t s mindig felcserélhetők. Speciálisan ha s = u 2 v és t = v 2 w u , akkor s t = u 2 w u és t s = v 2 w v , tehát pont az állítást kapjuk.

Most rögzítsünk egy b betűt, és jelölje B a b -t nem tartalmazó szavak halmazát. Tegyük fel, hogy ezek száma legfeljebb N //<// ? . Belátjuk, hogy az összes szavak száma legfeljebb N 3 N . Egy tetszőleges szó u 0 b u 1 b u 2 u k - 1 b u k alakban írható, ahol u 0 , , u k már nem tartalmaz b betűt. A b u = u ( u 2 b u ) azonosságot alkalmazzuk sorban először u = u k -ra, majd u = u k - 1 u k -ra, és így tovább. A végén egy olyan szót kapunk, aminek a baloldala u 0 u k (ami B -beli, és így legfeljebb N -féle lehet), ezután pedig u 2 b u alakú szavak szorzata következik, ahol u ? B . Ezek a tényezők páronként felcserélhetők, ezért összevonhatjuk az egyforma tényezőket. Így a szorzatnak a jobboldala legfeljebb 3 N -féle lehet. Ezzel a bizonyítást befejeztük. Finomabb számolással az is belátható, hogy m darab betű esetén a szavak száma pontosan

3 m + m 2 + m 3 .

(3) Először olyan f függvényt gyártunk, ami egy adott ( a 1 , , a n ) ? J n helyen I , a többi helyen N . Legyen f ( x 1 , , x n ) egy n tagú ÉS, aminek az i -edik tagja x i , ha a i = I és N E M ( x i ) , ha a i = N , ez nyilván jó. Tetszőleges g függvényt úgy kaphatunk, hogy minden olyan J n -beli helyhez, ahol a g értéke I , legyártjuk az iménti függvényt, és ezeket összeVAGYoljuk.

(4) Például a 0 , 1 , 2 , , n - 1 halmazon jó lesz az f ( x , y ) = min ( x , y ) + 1 függvény, ahol az 1 hozzáadását modulo n kell érteni, azaz úgy, hogy n - 1 -hez adva nullát kapunk. Valóban, x = y -t írva megkapjuk x ? x + 1 -et, ezt i -szer önmagába helyettesítve x ? x + i -t, és ezért a min függvényt is (mint f ( x , y ) + ( n - 1 ) ). Az x , x + 1 , x + 2 , , x + ( n - 1 ) minimuma mindig 0, tehát a konstans nulla függvény is kifejezhető, és így minden konstans függvény is. Ha i tetszőleges, akkor f i ( x ) = min ( 1 , x - i ) - 1 értéke i -nél n - 1 , másutt nulla. A 2.3. Feladat megoldásában látott módszerrel haladunk tovább. Ha ( a 1 , , a n ) tetszőleges, akkor az f a i ( x i ) függvények minimuma ( a 1 , , a n ) -nél n - 1 , másutt nulla. Az ilyen függvényeket kell még „összeVAGYolni”, ezt a v ( x , y ) = min ( x - 1 , y - 1 ) + 1 segítségével tehetjük.

(6) A 2.3. Feladat megoldásához hasonlóan járunk el. Legyen g tetszőleges monoton függvény. Minden olyan ( a 1 , , a n ) helyhez, ahol g értéke I , készítünk egy f ( x 1 , , x n ) függvényt, ami az ÉS-e azoknak az x i változóknak, melyekre a i = I . Ezeknek az f függvényeknek az összeVAGYoltja jó lesz.

(8) Először modellt alkotunk a feladatra. Számozzuk meg 1-től n -ig a lakosokat. Ha az i -edik lakos az A i lakosra szavaz, akkor az összesítési eljárás az A 1 , , A n sorozatból (a szavazólapok összességéből) kiszámítja a leendő elnököt, akit f ( A 1 , , A n ) jelöl. Az összesítési eljárás tehát egy n -változós függvény a lakosok halmazán (vagyis az 1 , 2 , , n számok halmazán), aminek a feltétel szerint az a tulajdonsága, hogy A 1 ? B 1 , , A n ? B n esetén f ( A 1 , , A n ) ? f ( B 1 , , B n ) . Azt kell megmutatnunk, hogy f csak egy változójától (a diktátortól) függ.

Tudjuk, hogy f ( 1 , , 1 ) ? f ( 2 , , 2 ) . Változtassuk a behelyettesített értékeket egyenként 1-ről 2-re. Valamelyik lépésnél f értéke biztosan változni fog, azaz

f ( 1 , , 1 , 1 , 2 , , 2 ) ? f ( 1 , , 1 , 2 , 2 , , 2 ) .

A lakosok átszámozásával elérhető, hogy a változás az első lakosnál történjen, vagyis f ( U , A 2 , , A n ) ? f ( V , A 2 , , A n ) alkalmas U , V , A 2 , , A n esetén. Belátjuk, hogy ez az első lakos a diktátor.

Legyen p 1 ( x ) = f ( x , A 2 , , A n ) . Válasszunk tetszőlegesen B 2 ? A 2 , , B n ? A n lakosokat, és legyen p 2 ( x ) = f ( x , B 2 , , B n ) . Most válasszunk egy C 2 lakost, aki A 2 -től és B 2 -től is különbözik. Hasonlóképpen, legyen C 3 olyan, aki A 3 -tól és B 3 -tól is különbözik, és így tovább. Legyen p 3 ( x ) = f ( x , C 2 , , C n ) . Ezt összesen n lépésen át lehet csinálni (és az utolsó lépésben már egyértelmű, kiket is kell választanunk). Így p 1 , , p n függvényeket kaptunk. Ezekre a feltétel miatt teljesül, hogy i ? j és x ? y esetén p i ( x ) ? p j ( y ) .

Tekintsük azt az n × n -es táblázatot, melynek i -edik sora p i ( 1 ) , , p i ( n ) . A táblázat elemei az 1 , , n számok közül kerülnek ki. Tudjuk, hogy ha két számot kiveszünk a táblázatból, amelyek nincsenek sem egy sorban, sem egy oszlopban, akkor azok feltétlenül különbözők. Tehát ha például azokat a helyeket nézzük, ahol az 1 szerepel, akkor ez része kell hogy legyen egy sornak, vagy egy oszlopnak. Tehát legfeljebb n darab 1-es szerepelhet. Mindez a többi számra is elmondható. Mivel n érték van, mindegyiknek pontosan n -szer kell szerepelnie, azaz teljes sort vagy oszlopot kell alkotnia. De akkor vagy minden sor állandó (azaz a p i függvények mindegyike konstans), vagy minden oszlop állandó (vagyis a p i függvények mind egyenlők).

Az f ( U , A 2 , , A n ) ? f ( V , A 2 , , A n ) feltétel azt mondja, hogy p 1 nem konstans. Így tehát p 1 = p 2 teljesül, vagyis f ( x , A 2 , , A n ) = f ( x , B 2 , , B n ) minden x -re. Itt B 2 , , B n már majdnem tetszőleges, csak az a kikötés, hogy B i ? A i teljesüljön.

Mivel p 2 = p 1 , ezért p 2 sem konstans. Ezért az iménti gondolatmenetet az A i helyett a B i -re elmondva azt kapjuk, hogy f ( x , B 2 , , B n ) = f ( x , Y 2 , , Y n ) teljesül, ha B i ? Y i . Mivel legalább három lakos van, az Y i már teljesen tetszőleges. Tehát az f függvény tényleg csak az első változójától függ.

(9) Nem. A felírható függvények a véges sok változós, egész együtthatós polinomok(hoz tartozó polinomfüggvények). Tegyük fel, hogy sikerült összeállítani egy majdnem többségi függvényt. Helyettesítsünk x és y helyébe páros számokat, és vizsgáljuk az eredményt 4-gyel való oszthatóság szempontjából. Ekkor a magasabb fokú tagok oszthatók lesznek néggyel, tehát elég az n 1 x 1 + ? + n k x k + c alakú polinomokra szorítkozni. Csupa nullákat, illetve egy kivétellel csupa nullákat helyettesítve látjuk, hogy 4 | c és 2 | n i minden i -re. Mindenhová 2-t írva ez ellentmondásra vezet.

(4) Könnyű látni, hogy ha a , b és b , c kicserélhetők, akkor a , c is. Ha tehát az 1 , 2 , , n számok közül éllel összekötjük a megadott párokat, akkor pontosan akkor juthatunk el minden sorrendhez, ha a kapott gráf összefüggő.

Ha k + t - 1 //>// n , akkor a behúzott élek száma n - 1 -nél kisebb, ilyen gráf nem lehet összefüggő. Tegyük fel, hogy k + t - 1 ? n , az állítást n szerinti indukcióval bizonyítjuk. Az állítás triviális, ha k = 1 . Ha k //>// 1 , akkor k ? t ; feltehető, hogy k //<// t . Tekintsük 1 ? a ? n - t esetén az a //<// a + t - k //<// a + t hármast. Itt a és a + t valamint a + t - k és a + t között megy él, és így a és a + t - k is cserélhető. Tehát az [ 1 , n - k ] intervallumban a t - k különbségűek cserélhetők. Az indukciós feltevést k , t , n helyett k , t - k , n - k -ra alkalmazva kapjuk, hogy itt minden pár felcserélhető. Szimmetriaokokból ( x - n + 1 - x ) a [ k + 1 , n ] intervallumban is minden felcserélhető. E két intervallum lefedi [ 1 , n ] -et, mert n - k + 1 ? ( k + t - 1 ) - k + 1 = t //>// k (azaz legalább k + 1 ). Mivel van megengedett csere a két intervallum között is (például n - k és n cseréje), ezért a gráf összefüggő.

(6) Rajzoljuk le az f permutációt: ha f ( x ) = y , akkor húzzunk egy nyilat x -ből y -ba (a fixpontoknál hurokélek keletkeznek). Mivel minden pontból egy nyíl indul ki, és egy nyíl érkezik, a gráf diszjunkt irányított körökből áll. Legyen r a kapott körök hosszainak legkisebb közös többszöröse. Ekkor f -et r - 1 -szer alkalmazva az inverzét kapjuk, mert minden körön egyet lépünk visszafelé.

(7) A 3.6. Feladat megoldásában lerajzolt gráf körei pont a ciklusok. Aki már olvasta a 4. Fejezetet, annak érdemes meggondolnia, hogy az f által generált permutációcsoport orbitjai pont az f ciklusait adják.

(10) Ez tipikusan az a feladat, ahol algebrai módszerrel érdemes nekifogni egy látszólag kombinatorika-problémának. Tetszőleges g permutációhoz rendeljük hozzá az ( 1 , 2 ) -szeresét. Ez kölcsönösen egyértelmű megfeleltetést létesít a páros és páratlan permutációk között. Ezért A n elemszáma n ! / 2 .

(3) Legyen Q tetszőleges eleme P orbitjának. Elég megmutatni, hogy P -t pontosan annyi G -beli elem viszi Q -ba, ahány helyben hagyja. Legyen q olyan rögzített G -beli permutáció, mely P -t Q -ba viszi. Mutassuk meg, hogy a P -t Q -ba vivő permutációk pontosan az s q alakú permutációk, ahol s befutja P stabilizátorát, továbbá, hogy s ? s q kölcsönösen egyértelmű megfeleltetés.

(4) 24, 48, 16.

(5) Tekintsük a kocka szimmetriacsoportjának „hatását” a lapok halmazán. Itt egy hatelemű orbit van, tehát a stabilizátor 48 / 6 = 8 elemű (és „ugyanolyan” csoport, mint a négyzet szimmetriacsoportja). Ha a szemköztes lappárokból álló háromelemű halmazon vizsgáljuk a hatást, akkor 16 elemű stabilizátort kapunk.

(1) Fessük be mindegyik élkocka egyik lapját pepitára úgy, hogy a nagy kocka lapjain bármely két szomszédos élkocka-lap közül pontosan az egyik legyen pepita. Állítsunk be 12 lámpát, ami ezeket a pepita mezőket világítja meg. A lámpák helyzete nem változik, de ha a kockát forgatgatjuk, akkor a pepita lapkák helyzete igen. Minden állapotban számoljuk meg, hogy hány pepita lapka van megvilágítva. Mutassuk meg, hogy ennek a számnak a paritása egy elemi elforgatás során nem változik. A kiinduló állapotban ez a szám páros, ha viszont egy élkockát elforgathatnánk a helyén, akkor arra az állapotra nézve nyilván páratlan lenne.