![]() |
A B. 4793. feladat (2016. április) |
B. 4793. Hány olyan permutációja van az 1,2,3,…,n számoknak, amelyekben pontosan
a) egyszer,
b) kétszer fordul elő, hogy két szomszédos helyen álló szám közül a bal oldali a nagyobb?
(6 pont)
A beküldési határidő 2016. május 10-én LEJÁRT.
Megoldás. a) Legyen egy ilyen permutáció a1,a2,…,an. A feltétel szerint pontosan egy olyan 2≤i≤n van, amelyre ai−1>ai. Ekkor az a1<a2<⋯<ai−1 és az ai<ai+1<⋯<an részek is monoton növekedőek. Így, ha kiválasztjuk, hogy mi legyen az A={a1,a2,…,ai−1} halmaz, akkor a sorrendjük már egyértelmű, és a többi szám sorrendje szintén egyértelmű. Továbbá ai−1>ai csak akkor nem teljesül, ha a1<a2<⋯<an, vagyis ha {a1,a2,…,ai−1}={1,2,…,i−1}, azaz az első i−1 számot választottuk ki. Az A⊆{1,2,…,n}=N halmaz megválasztására 2n féle lehetőség van, ezek közül pontosan akkor nem kapunk megfelelő permutációt, ha A üres, minden elemet tartalmaz, vagy valamely 2≤i≤n mellett A={1,2,…,i−1}. Ez azt jelenti, hogy a megfelelő permutációk száma 2n−(n+1).
b) A feladat b) részében szereplő feltételt egy a1,a2,…,an permutáció pontosan akkor elégíti ki, ha valamely 2≤i<j≤n mellett a1<a2<⋯<ai−1, ai<ai+1<⋯<aj−1, aj<aj+1<⋯<an, továbbá ai−1>ai és aj−1>aj. Legyen A={a1,a2,…,ai−1}, B={ai,ai+1,…,aj−1}, C={aj,aj+1,…,an}. Az A,B,C⊆N halmazok páronként diszjunktak és A∪B∪C=N. A (feltételeket kielégítő) permutációt A,B,C egyértelműen meghatározza, hiszen a permutáció az A-beli elemek növekvő felsorolásával kezdődik, majd következnek B elemei szintén növekvő sorrendben, végül C elemei növekvő sorrendben. Pontosan akkor kapunk megfelelő permutációt, ha:
(i) A legnagyobb eleme nagyobb, mint B legkisebb eleme, továbbá
(ii) B legnagyobb eleme nagyobb, mint C legkisebb eleme.
Minden megfelelő permutációt csak egyetlen (A,B,C) hármasnál kapunk meg. Az {1,2,…,n} halmaz minden eleme 3 féle helyre kerülhet: A-ba, B-be, vagy C-be, így 3n darab (A,B,C) hármas adható meg úgy, hogy azok diszjunkt uniója N legyen. Számoljuk meg, hogy hány olyan van közöttük, ami nem a feltételnek megfelelő permutációt ad. Azon hármasok száma, amelyeknél A, B, C valamelyike üres 3⋅2n−3, ugyanis ha például A=∅, akkor a B halmaz 2n-féle lehet (és ez C-t már meghatározza), azonban az ebből adódó 3⋅2n darab hármas között azok a hármasok, amelyeknek két tagja is üres, kétszer szerepelnek. Ilyen hármasból három van: (∅,∅,N),(∅,N,∅),(N,∅,∅), vagyis azon hármasok száma, ahol a három halmaz közül legalább az egyik üres valóban 3⋅2n−3. A továbbiakban csak olyan hármasokkal foglalkozunk, amelyekben A,B,C egyike sem üres. Ha A legnagyobb eleme kisebb, mint B legkisebb eleme és B legnagyobb eleme kisebb, mint C legkisebb eleme, akkor az 1,2,…,n permutációt kapjuk, ami nem megfelelő. Ilyen hármasból (n−12) van, hiszen az A legnagyobb elemét és B legnagyobb elemét tartalmazó halmaz az N∖{n} halmaz tetszőleges 2 elemű részhalmaza lehet. Végül számoljuk meg, hány hármas esetén kapunk olyan permutációt, melyeknél (i) és (ii) közül pontosan az egyik teljesül. Egy ilyen hármas olyan permutációt ad, amiben pontosan egyszer fordul elő, hogy két szomszédos elem közül a bal oldali a nagyobb. Valamint annak is teljesülnie kell, hogy (i) sérülése esetén ettől a ponttól balra, (ii) sérülése esetén ettől a ponttól jobbra legalább két elem van.
Vegyünk egy a)-nak eleget tevő permutációt, és vizsgáljuk meg, hány (A,B,C) hármas adja ezt. Ha a bal oldali részben csak egy elem van, akkor ez az elem alkotja A-t, míg B megválasztására n−2 lehetőség van (a megmaradó elemek közül kell kiválasztunk az i darab legkisebbet valamely 1≤i≤n−2-re). Ehhez hasonlóan, ha a jobb oldali részben csak egy elem van, akkor C-ben csak ez az elem van, míg B-re n−2 lehetőség van. Ha a bal oldali részben 2≤k≤n−2 elem van, a jobb oldaliban pedig n−k, akkor ha a bal oldali rész lesz A∪B ((i) sérülése esetén), akkor a lehetőségek száma k−1, ha pedig a jobb oldali rész lesz B∪C ((ii) sérülése esetén), akkor a lehetőségek száma (n−k)−1. Így a lehetőségek száma összesen ismét (k−1)+(n−k−1)=n−2. Ez azt jelenti, hogy az a)-nak eleget tevő permutációk mindegyikét (n−2)-szer kapjuk meg egy hármasból.
Tehát a b)-nek megfelelő permutációk száma 3n−(3⋅2n−3)−(n−12)−(n−2)(2n−n−1)=3n−(n+1)2n+n2+n2. (Ha n≤2, akkor nincs ilyen permutáció, és a kapott formula is 0-t ad.)
Megjegyzés. A feladat kapcsolódik az A. 671. feladathoz.
Statisztika:
A KöMaL 2016. áprilisi matematika feladatai
|