Matematika verseny/2011
(→8. feladat) |
|||
72. sor: | 72. sor: | ||
az <math> 1, 2, \dots, k </math> számok csupa különböző ciklusban. | az <math> 1, 2, \dots, k </math> számok csupa különböző ciklusban. | ||
− | == Megoldás == | + | === Megoldás === |
Vegyük az <math> 1, \dots, n - 1 </math> számok egy permutációját, | Vegyük az <math> 1, \dots, n - 1 </math> számok egy permutációját, | ||
112. sor: | 112. sor: | ||
<math> (1/(n-1)) \cdot ((n-1)/n) = 1/n </math>. | <math> (1/(n-1)) \cdot ((n-1)/n) = 1/n </math>. | ||
− | == Megoldás másképp == | + | === Megoldás másképp === |
Ismert, hogy ha a ciklusfelbontást úgy írjuk fel, | Ismert, hogy ha a ciklusfelbontást úgy írjuk fel, |
A lap 2013. április 18., 10:23-kori változata
== 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.
Tartalomjegyzék |
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