Feladat:	F.3287	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Barát Anna ,  Máthé András ,  Naszódi Gergely ,  Pálvölgyi Dömötör ,  Papp Dávid ,  Szabadka Zoltán ,  Vitéz Ildikó
Füzet:	2000/január, 35 - 36. oldal		PDF  |  MathML
Témakör(ök):	Részhalmazok, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1999/május: F.3287

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Jelöljük egy $n$ elemű halmaz partícióinak a számát $r\left(n\right)$-nel. Nyilván $r\left(1\right)=1=1!$, $r\left(2\right)=2=2!$, $r\left(3\right)=4<3!$. Tegyük fel, hogy $r\left(k\right)<k!$, és vizsgáljuk egy $k+1$ elemű $T=H\cup \left\{a\right\}$ halmaz partícióit ($a\notin H$). A $T$ minden partíciójából az $a$ elem elhagyásával a $H$ partícióját kapjuk. Megfordítva ez azt jelenti, hogy $T$ minden partíciója megkapható a $H$ alkalmas $H=K_1\cup \text{...}\cup K_t$ partíciójából úgy, hogy az $a$ elemet valamelyik $K_i$ részhalmazhoz csatoljuk, vagy képezzük a (mindegyik $K_i$-hez diszjunkt) $\left\{a\right\}$ halmazt. Adott $H$-beli partíció esetén ez éppen $t+1$ lehetőség. Mivel a $K_i$ halmazok egyike sem üres${}^{*}$, azért $t\le k$, $t+1\le k+1$. Tehát $r\left(k+1\right)\le \left(k+1\right)r\left(k\right)$, így (a megvizsgált kezdeti érték(ek)re támaszkodva) az $r\left(n\right)\le n!$ egyenlőtlenség teljes indukciós bizonyítását kaptuk.  Vitéz Ildikó (Miskolc, Földes F. Gimn., 11. o.t.)   II. megoldás. Az $\left\{\mathrm{1,}\mathrm{2,}\text{...}\mathrm{,}n\right\}$ halmaz mindegyik partíciójához rendeljük hozzá az 1, 2, $\text{...}$, $n$ számok egy sorbaállítását a következőképpen: először állítsuk a partíciót meghatározó részhalmazokat legkisebb elemük szerint $$növekvő̲ sorrendbe, az egyes részhalmazokban szereplő számokat pedig rendezzük $$csökkenő̲ sorrendbe. Egy ilyen módon kapott számsorból a partíció egyértelműen visszakapható, hiszen éppen ott vannak az egyes részhalmazokat kijelölő vágások, ahol a sorban egy szám után nála nagyobb szám következik. Tehát különböző partícióknak különböző számsorozatok felelnek meg, ezért a partíciók száma nem nagyobb az összes sorrend számánál, $n!$-nál.  Papp Dávid (Budapest, Szent István Gimn., 11. o.t.) ${}^{*}$Ez a nyilvánvalóan szükséges megszorítás a feladat szövegéből sajnos kimaradt.