Kezdőlap


Feladat:	F.2471	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Cynolter Gábor
Füzet:	1984/december, 442 - 443. oldal		PDF \| MathML
Témakör(ök):	Kombinációk, Feladat
Hivatkozás(ok):	Feladatok: 1984/április: F.2471

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.

Ha egy sorban álló $n$ lovag közül kellene $k$ darabot kiválasztanunk úgy, hogy ne legyen közöttük két szomszédos, a következőképpen járhatnánk el. Az $n - k$ lovag között, illetve a két szélen összesen $n - k + 1$ hely van. Ahányféleképpen a ,,kiválasztandó'' $k$ lovagot visszaállíthatjuk ezekre a helyekre, annyi a lehetséges kiválasztások száma, ez pedig $(\binom{n - k + 1}{k})$ .
Ha most a sorban álló lovagokat kerek asztal mellé ültetjük, akkor az előbbi kiválasztásokból éppen azok az esetek nem megengedettek, mikor mind a két szélsőt kiválasztottuk. Az ilyen esetek száma pedig

\begin{matrix} (\binom{(n - 4) - (k - 2) + 2}{k - 2}) = (\binom{n - k - 1}{k - 2}) . \end{matrix}

Artúr király tehát általában

(\binom{n - k + 1}{k}) - (\binom{n - k - 1}{k - 2})

-féleképp választhat.
A feladat adatai mellett ez

(\binom{36}{15}) - (\binom{34}{13}) = 4 639 918 800

Megjegyzés. Általános esetben a kérdés csak akkor értelmes, ha egyáltalán végrehajtható a kiválasztás, tehát ha

n - k + 1 \geq k

, azaz

k \leq \frac{n + 1}{2}

az egy sorban álló lovagok esetében, és ha

k \leq \frac{n}{2}

a kerek asztalnál, hiszen itt eggyel kevesebb a kiválasztottak után maradó helyközök száma.