Feladat:	F.3252	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Csirmaz Előd ,  Tóth Ágnes ,  Vizer Máté
Füzet:	2000/február, 94 - 96. oldal		PDF  |  MathML
Témakör(ök):	Kombinatorika, Feladat
Hivatkozás(ok):	Feladatok: 1998/november: F.3252

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. Tekintsünk egy megfelelő elrendezést, és nézzük a legnagyobb elemet, $n$-et. Akárhol áll a sorban, egyetlen szomszédja, $\left(n-1\right)$ meg kell előzze. Az $\left(n-1\right)$-et pedig meg kell előznie $\left(n-2\right)$-nek, hiszen másik szomszédja, $n$, mögötte van. Ez így folytatódik, amíg az elrendezés legelső eleméhez nem érünk. Ha ez $k$, akkor az elrendezésben a $k$, $k+1$, $\text{...}$, $n-1$, $n$ számok ebben a sorrendben szerepelnek. Tekintsük most a legkisebb elemet, az 1-et. Akárhol van ‐ kivéve ha az első helyen, azaz $k=1$ ‐ meg kell előzze egyetlen szomszédja, a 2. Ezt viszont a 3-nak kell megelőznie, hiszen a másik szomszédja, az 1 már mögötte van. Ez így folytatódik a $\left(k-1\right)$-ig, amit pedig szomszédja, $k$ megelőz, hiszen a legelső helyen áll. A $k$-val kezdődő elrendezésben tehát a $k$-nál kisebb számok sorrendje is egyértelmű: $k-1$, $k-2$, $\text{...}$, 2, 1. Ha rögzítjük a legelső elemet, $k$-t, akkor az $n-1$ szabad helyre $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$-féleképpen tudjuk a $k-1$, $k-2$, $\text{...}$, 2, 1 számokat ebben a sorrendben felírni, ezután pedig a $k$-nál nagyobb elemek beírása a megmaradt helyekre a kötött sorrend miatt már egyértelmű. A lehetséges sorbarendezések száma így $\begin{array}{c}{\displaystyle \sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)=2^{n-1}\mathrm{.}}\end{array}$  Csirmaz Előd (Fazekas M. Főv. Gyak. Gimn., 10. o.t.)   II. megoldás. Először azt igazoljuk, hogy egy megfelelő sorbarendezésnél a legutolsó helyen az 1 vagy pedig az $n$ áll. Tegyük fel, hogy ez nem igaz, legyen $1<i<n$, és tegyük fel, hogy a sorozat utolsó tagja $i$. Ekkor az $i$-t mindkét szomszédja, az $i+1$ és az $i-1$ is megelőzi. Ezután az $i$-nél nagyobb számok a kisebbik, az $i$-nél kisebbek pedig a nagyobbik szomszédjukat előzik meg, így a másik szomszédjuknak őket kell megelőzniük. Így két láncot kapunk: $\begin{array}{c}{\displaystyle \begin{array}{ccccccc}\hfill n\hfill & \hfill \leftarrow \hfill & \hfill \text{...}\hfill & \hfill \leftarrow \hfill & \hfill i+2\hfill & \hfill \leftarrow \hfill & \hfill i+1\hfill \\ \hfill \text{<div style="line-height: -2mm"> </div>}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \nwarrow \hfill \\ \hfill \text{<div style="line-height: -2mm"> </div>}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill i\hfill \\ \hfill \text{<div style="line-height: -2mm"> </div>}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \swarrow \hfill \\ \hfill \text{<div style="line-height: -2mm"> </div>}1\hfill & \hfill \leftarrow \hfill & \hfill \text{...}\hfill & \hfill \leftarrow \hfill & \hfill i-2\hfill & \hfill \leftarrow \hfill & \hfill i-1\hfill & \hfill \hfill \end{array}}\end{array}$ Ez azt jelenti, hogy az 1 és az $n$ mindketten a legelső helyen kell álljanak, ami nyilván nem lehetséges. Így valóban 1 vagy $n$ áll az utolsó helyen. Jelölje $f\left(n\right)$ azt, hogy hányféleképpen lehet $n$ darab különböző számot sorbarakni úgy, hogy az első helyen álló szám kivételével mindegyiket megelőzze legalább az egyik szomszédja. A szomszédság jelentése itt nyilvánvaló, és $f\left(n\right)$ valóban csak az $n$-től függ. Akár 1, akár pedig $n$ áll az utolsó helyen, a megmaradó számok $f\left(n-1\right)$-féle sorrendjének bármelyike megfelelő $n$ hosszúságú sorozatot ad, így $f\left(n\right)=2f\left(n-1\right)$. Mivel $f\left(1\right)=1$, azért $f\left(n\right)=2^{n-1}$.  Vizer Máté (Fazekas M. Főv. Gyak. Gimn., 11. o.t.)   III. megoldás. Legyen $1\le k\le n$, és tegyük a $k$-t a legelső helyre. A második elem így a $k$ valamelyik szomszédja, $k-1$ vagy $k+1$. (Ha $k=1$ vagy $k=n$, akkor a két eset közül persze csak az egyik lehetséges.) Az első két elem mindenesetre két szomszédos szám, a harmadik pedig e ,,szakasz'' valamelyik szomszédja, a kisebbik számnál 1-gyel kisebb vagy a nagyobbiknál 1-gyel nagyobb. Ugyanígy kapjuk, hogy az első $i$ darab elem $i$ darab szomszédos szám, és az $\left(i+1\right)$-edik elem e számok minimumánál 1-gyel kisebb vagy maximumánál 1-gyel nagyobb. Így minden sorozathoz ‐ a második elemtől kezdve ‐ hozzárendelhető egy 0-kból és 1-esekből álló sorozat. Az $\left(i+1\right)$-edik helyen álló 0 azt jelenti, hogy az első $i$ darab szám minimumánál 1-gyel kisebb, az 1 pedig azt, hogy az első $i$ darab szám maximumánál 1-gyel nagyobb szám került az $\left(i+1\right)$-edik helyre. Így egy $n-1$ hosszúságú 0‐1 sorozatot rendeltünk az első $n$ darab szám egy megfelelő sorbarendezéséhez. Ez a hozzárendelés kölcsönösen egyértelmű, ha ebből a 0‐1 sorozatból elő tudjuk állítani az első elemet, hiszen ezután a folytatás már egyértelmű. Vegyük észre, hogy az első elem, $k$, a sorozatban szereplő nullák számánál 1-gyel nagyobb, hiszen ekkor van $\left(k-1\right)$ lehetőségünk arra, hogy az addigi szakasz minimumát 1-gyel csökkentsük. Az $\left(n-1\right)$ hosszúságú 0‐1 sorozatok száma, mint ismeretes, $2^{n-1}$, ezért ennyi a feladatban kérdezett sorbarendezések száma is.  Tóth Ágnes (Hajdúszoboszló, Hőgyes E. Gimn., 9. o.t.)