Matematika verseny/2011
Tartalomjegyzék |
Matematika verseny 2011
A 2011. évi BME Matematika versenyt 2011. április 14-én rendezték meg. A verseny általános leírását lásd a Matematika verseny lapon, a feladatsort és eredményeket Horváth Miklós honlapján.
Ez a lap a feladatokat tartalmazza, de ide (vagy allapokra) lehet írni a feladatok megoldását vagy megjegyzéseket hozzájuk.
1. feladat
Adott a,b,c,d oldalhosszúságú síkbeli négyszögek közül melyik lesz maximális területű? Az oldalak ebben a sorrendben csatlakoznak.
2. feladat
Melyek azok a tízes számrendszerben felírt természetes számok, melyek utolsó számjegyét az elejére áthelyezve az eredeti szám 2/3-át kapjuk?
3. feladat
Legyen A invertálható -es mátrix. Tegyük fel, hogy az A és A − 1 mátrixok minden el eme nemnegatív. Bizonyítsuk be, hogy van olyan k > 0 egész, hogy Ak diagonális mátrix.
4. feladat
5. feladat
a. Legyenek egységvektorok egy euklideszi térben, , ha . Mutassuk meg, hogy lineárisan függetlenek.
b. Lengyen m = (n − 1)n / 2 + 1, egységvektorok, , ha . Mutassuk meg, hogy közül kiválasztható n lineárisan független vektor.
6. feladat
Az irányított G egyszerű gráf irányított kromatikus száma, χi(G) az a legkisebb k, amelyre k színnel színezhetők a csúcsok úgy, hogy egy él két vége különböző színű és bármely adott színpárban csak az egyik irányba vezethet él. Mutassuk meg, hogy nincs olyan függvény, melyre teljesül minden G-re, ahol χ(G) a megfelelő irányítatlan gráf kromatikus száma. Azaz az irányított kromatikus szám nem becsülhető a kromatikus szám ismeretében.
A szerkesztő megjegyzése
A feladatot értsük úgy, hogy csak olyan G gráfokat tekintünk, amelyekben semelyik két csúcs között nincs oda-vissza él (így az irányított kromatikus szám mindig véges).
7. feladat
Mutassuk meg, hogy ha és minden x > 0-ra , akkor .
8. feladat
Legyen . Mutassuk meg, hogy az számok egy véletlen permutációjánál
a. 1 / k valószínűséggel lesznek az számok ugyanabban a ciklusban,
b. 1 / k! valószínűséggel lesznek az számok csupa különböző ciklusban.
Megoldás
Vegyük az számok egy permutációját, és állítsuk elő ennek a ciklusfelbontását. Ebből megkaphatjuk az egy permutációját úgy, hogy valamelyik ciklusba valahova beszúrjuk az n számot. Mivel bármely t hosszú ciklusba t helyre lehet egy új elemet beszúrni, ez összesen n − 1 lehetőség. Ezen kívül kaphatunk még egy permutációt úgy is, hogy az n egy új, 1 hosszú ciklusba kerül. Nem nehéz látni, hogy ha vesszük az egy egyenletes eloszlású véletlen permutációját, és a talált n lehetséges kibővítés valamelyikét választjuk egyenletesen véletlenszerűen, akkor így az egy egyenletes eloszlású véletlen permutációját kapjuk.
Csakhogy ha , akkor a permutáció kibővítése nem változtat azon, hogy az számok közül melyek vannak egy ciklusban. Így aztán elég belátni az állítást a k = n esetben. A (b) állítás ilyenkor nyilvánvaló, mert a k szám csak az identikus permutációban kerül mindegyik elem külön ciklusba.
Az (a) állítást n-re teljes indukcióval láthatjuk be (mindig a k = n esetet véve). Tegyük fel, hogy az egy permutációját megint a fenti módon, egy eggyel rövidebb permutáció kibővítéseként kapjuk. Az összes eleme ekkor pontosan akkor van egy ciklusban, ha ez már a rövidebb permutációban is teljesült, és az n is ebbe a ciklusba kerül. Az indukciós feltétel miatt a rövidebb permutáció 1 / (n − 1) valószínűséggel áll egy ciklusból, és bármely ilyen permutációnak az n kibővítése közül csak egy olyan, hogy az n nem ebbe a ciklusba kerül, tehát a keresett valószínűség valóban .
Megoldás másképp
Ismert, hogy ha a ciklusfelbontást úgy írjuk fel, hogy minden ciklust a legkisebb elemével kezdjük, és a ciklusokat az első elem szerint csökkenő sorrendben írjuk egymás után, akkor elhagyhatjuk a ciklusokat határoló zárójeleket, mert az elhagyás után kapott permutáció az eredetit egyértelműen azonosítja. A zárójelek elhagyása után tehát ismét az egy egyenletes véletlen permutációját kapjuk. Az, hogy az eredeti permutációban az külön ciklusokba kerül, azzal ekvivalens, hogy az új permutációban ezek az elemek csökkenő sorrendben állnak, aminek a valószínűsége nyilván 1 / (k!). Másrészt az, hogy az eredeti permutációban az egy ciklusba kerül, ekvivalens azzal, hogy az új permutációban ezek közül az elemek közül az 1 áll legelöl, ennek pedig 1 / k a valószínűsége.
9. feladat
Legyenek P,Q ortogonális projekciók egy véges dimenziós térben. Mutassuk meg, hogy
10. feladat
Legyen f(z) reguláris a Rez > 0 félsíkon. Tegyük fel, hogy
Bizonyítsuk be, hogy tetszőleges δ > 0 esetén