Matematika verseny/2011

A MathWikiből
(Változatok közti eltérés)
(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.
  
=== A szerkesztő megjegyzése ===
+
== Megoldás ==
  
A feladatra van olyan megoldás, ami az a. és b. részt is megoldja, de olyan megoldás is, ami csak az a. részt oldja meg.
+
Vegyük az <math> 1, \dots, n - 1 </math> számok egy permutációját,
 +
és állítsuk elő ennek a ciklusfelbontását.
 +
Ebből megkaphatjuk az <math> 1, \dots, n </math> egy permutációját úgy,
 +
hogy valamelyik ciklusba valahova beszúrjuk az <math> n </math> számot.
 +
Mivel bármely <math> t </math> hosszú ciklusba <math> t </math> helyre lehet egy új elemet beszúrni,
 +
ez összesen <math> n - 1 </math> lehetőség.
 +
Ezen kívül kaphatunk még egy permutációt úgy is, hogy az <math> n </math> egy új,
 +
1 hosszú ciklusba kerül.
 +
Nem nehéz látni,
 +
hogy ha vesszük az <math> 1, \dots, n - 1 </math> egy egyenletes eloszlású
 +
véletlen permutációját,
 +
és a talált <math> n </math> lehetséges kibővítés valamelyikét
 +
választjuk egyenletesen véletlenszerűen,
 +
akkor így az <math> 1, \dots, n </math> egy egyenletes eloszlású véletlen permutációját kapjuk.
 +
 
 +
Csakhogy ha <math> k \le n - 1 </math>,
 +
akkor a permutáció kibővítése nem változtat azon,
 +
hogy az <math> 1, \dots, k </math> számok közül melyek vannak egy ciklusban.
 +
Így aztán elég belátni az állítást a <math> k = n </math> esetben.
 +
A (b) állítás ilyenkor nyilvánvaló,
 +
mert a <math> k </math> szám csak az identikus permutációban kerül
 +
mindegyik elem külön ciklusba.
 +
 
 +
Az (a) állítást <math> n </math>-re teljes indukcióval láthatjuk be
 +
(mindig a <math> k = n </math> esetet véve).
 +
Tegyük fel, hogy az <math> 1, \dots, n </math> 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 <math> n </math> is ebbe a ciklusba kerül.
 +
Az indukciós feltétel miatt a rövidebb permutáció <math> 1/(n-1) </math>
 +
valószínűséggel áll egy ciklusból,
 +
és bármely ilyen permutációnak az <math> n </math> kibővítése közül
 +
csak egy olyan, hogy az <math> n </math> nem ebbe a ciklusba kerül,
 +
tehát a keresett valószínűség valóban
 +
<math> (1/(n-1)) \cdot ((n-1)/n) = 1/n </math>.
 +
 
 +
== 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 <math> 1, \dots, n </math>
 +
egy egyenletes véletlen permutációját kapjuk.
 +
Az,
 +
hogy az eredeti permutációban az <math> 1, \dots, k </math> 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 <math> 1/(k!) </math>.
 +
Másrészt az,
 +
hogy az eredeti permutációban az <math> 1, \dots, k </math> egy ciklusba kerül,
 +
ekvivalens azzal,
 +
hogy az új permutációban ezek közül az elemek közül az <math> 1 </math> áll legelöl,
 +
ennek pedig <math> 1/k </math> a valószínűsége.
  
 
== 9. feladat ==
 
== 9. feladat ==

A lap 2013. április 18., 09:22-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ó  n \times n -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

 \int_{0}^{\infty} e^{-(y^2+y^{-2})}dy = ?

5. feladat

a. Legyenek  v_1, \dots, v_n egységvektorok egy euklideszi térben,  |\langle v_i, v_j\rangle| < 1/(n-1) , ha  i \ne j . Mutassuk meg, hogy  v_1, \dots, v_n lineárisan függetlenek.

b. Lengyen m = (n − 1)n / 2 + 1,  v_1, \dots, v_m egységvektorok,  |\langle v_i, v_j\rangle|^2 < 1/(m - 1) , ha  i \ne j . Mutassuk meg, hogy  v_1, \dots, v_m 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 : \mathbb{N} \to \mathbb{N} függvény, melyre  \chi_i(G) \le f(\chi(G)) 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  f \in C(0, \infty) és minden x > 0-ra  \lim_{n\to\infty} f(x/n) = 0 , akkor  \lim_{x \to 0+} f(x) = 0 .

8. feladat

Legyen  1 \le k \le n . Mutassuk meg, hogy az  1, 2, \dots, n számok egy véletlen permutációjánál

a. 1 / k valószínűséggel lesznek az  1, 2, \dots, k számok ugyanabban a ciklusban,

b. 1 / k! valószínűséggel lesznek az  1, 2, \dots, k számok csupa különböző ciklusban.

Megoldás

Vegyük az  1, \dots, n - 1 számok egy permutációját, és állítsuk elő ennek a ciklusfelbontását. Ebből megkaphatjuk az  1, \dots, n 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  1, \dots, n - 1 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  1, \dots, n egy egyenletes eloszlású véletlen permutációját kapjuk.

Csakhogy ha  k \le n - 1 , akkor a permutáció kibővítése nem változtat azon, hogy az  1, \dots, k 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  1, \dots, n 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  (1/(n-1)) \cdot ((n-1)/n) = 1/n .

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  1, \dots, n egy egyenletes véletlen permutációját kapjuk. Az, hogy az eredeti permutációban az  1, \dots, k 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  1, \dots, k 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

 \mathbf{Tr} e^{P+Q} \le \mathbf{Tr}(e^P e^Q).

10. feladat

Legyen f(z) reguláris a Rez > 0 félsíkon. Tegyük fel, hogy

 \lim_{z\to0, {\rm Re} z>0} \frac{f(z) - a_0}{z} = a_1.

Bizonyítsuk be, hogy tetszőleges δ > 0 esetén

 \lim_{z\to0, {\rm Re} z>\delta|{\rm Im} z|} f'(z) = a_1.

Megjegyzések

Személyes eszközök