Kezdőlap


Feladat:	B.4373	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Abonyi József
Füzet:	2012/április, 221 - 223. oldal		PDF \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Feladat
Hivatkozás(ok):	Feladatok: 2011/szeptember: B.4373

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.

Megoldás. A konferencia résztvevőinek sorszámozását szabadon megválaszthatjuk, ezért az általánosság megszorítása nélkül feltehetjük, hogy a lábak számának nagyságrendje $a_{1} \leq a_{2} \leq ... \leq a_{n}$ , ahol az $a_{i}$ ( $i = 1,2, ..., n \in N^{+}$ ) számok pozitív páros számok.
Nyilvánvaló, hogy ha a soklábú lények bizonyos számú cipővel valamilyen sorrend mellett fel tudnak jutni a hegy tetejére, akkor fordított sorrendben ugyanennyi cipővel le is tudnak onnan jönni, tehát elegendő csak azt vizsgálnunk, hogy minimálisan hány lábbeli szükséges a résztvevők feljutásához.
$n = 1$ esetén a feladat feltétele alapján az egyetlen résztvevőnek minimálisan $\frac{a_{1}}{2}$ cipőre van szüksége a hegy megmászásához.
$n \geq 2$ ( $n \in N^{+}$ ) esetén meg fogjuk mutatni, hogy a résztvevőknek

\begin{matrix} {max}_{}^{} {\frac{a_{1} + a_{2}}{2}, \frac{a_{n}}{2}} \end{matrix}

cipő szükséges a konferencián való részvételhez.
Első menetben küldjük fel az 1. és a 2. résztvevőt a hegy tetejére

\frac{a_{1}}{2}

, illetve

\frac{a_{2}}{2}

cipővel a lábukon, majd a 2. résztvevő az összes hegytetőre feljutott cipőt a lábára felhúzva hozza le. Ez az

\frac{a_{1} + a_{2}}{2} \leq \frac{2 a_{2}}{2} = a_{2}

becslés alapján meg is tehető. Így a hegy lábánál lesz az összes cipő.
Menjen fel azután a hegytetőre az

n

-edik soklábú

\frac{a_{n}}{2}

cipővel. Mivel

\begin{matrix} \frac{a_{n}}{2} \leq {max}_{}^{} {\frac{a_{1} + a_{2}}{2}, \frac{a_{n}}{2}}, \end{matrix}

ez megtehető. Ezután a hegytetőn tartózkodó 1. soklábú le-föl járkálva juttassa le az összes cipőt a hegy lábához, mégpedig úgy, hogy lefelé

a_{1}

, míg felfelé haladva

\frac{a_{1}}{2}

cipőt húzzon a lábaira. Ha az utolsó lejövetelkor nem jut

a_{1}

cipő a lábaira, akkor jöjjön le annyival, amennyi még maradt. Ez biztosan több, mint

\frac{a_{1}}{2}

, hiszen felfelé haladva már viselt ennyit a lábain.
Ezután az előbb vázolt eljárás az

(n - 1)

-edik soklábú feljuttatásával folytatódik. Felmegy együtt az 1. és a 2. résztvevő

\frac{a_{1}}{2}

, illetve

\frac{a_{2}}{2}

cipővel, majd a 2. résztvevő

\frac{a_{1} + a_{2}}{2}

cipővel

a lábain lejön a hegyről. Így az összes cipő lejut a hegy lábához és ezután az

(n - 1)

-edik soklábú fog felmenni a hegytetőre

\frac{a_{n - 1}}{2}

cipővel. Ez megtehető, mivel

\begin{matrix} \frac{a_{n - 1}}{2} \leq \frac{a_{n}}{2} \leq {max}_{}^{} {\frac{a_{1} + a_{2}}{2}, \frac{a_{n}}{2}} . \end{matrix}

Ezután az 1. résztvevő a korábban említett eljárással, le-fel ingázva juttatja le az összes cipőt a hegy lábához.
Az algoritmust tovább folytatva az

(n - 2)

-edik,

(n - 3)

-adik, végül a 2. és az 1. soklábú jut fel véglegesen a hegy tetejére. Mint már korábban említettük, a lejutás éppen fordított sorrend szerint történik. Ezzel beláttuk, hogy a megadott cipőszámmal biztosítható a résztvevők feljutása. Ezután azt fogjuk megmutatni, hogy kevesebb lábbelivel nem biztosítható a soklábúak részvétele a konferencián.
Mivel az

n

-edik résztvevőnek minimálisan

\frac{a_{n}}{2}

cipő szükséges a hegy tetejére való feljutáshoz, ezért a lábbelik száma legalább

\begin{matrix} \frac{a_{n}}{2} . \end{matrix}

(1)

Másrészt legalább két résztvevő esetén, ha az első két hegytetőre feljutó személy az

i

-edik és a

j

-edik résztvevő (

1 \leq i < j \leq n

i, j \in N^{+}

), akkor

a feljutásukhoz legalább

\frac{a_{i}}{2} + \frac{a_{j}}{2}

cipő szükséges, hiszen vagy együtt mennek felfelé, vagy külön-külön, de ez utóbbi esetben a második indulónak nem tud lehozni cipőt senki a hegytetőről. Ha az első induló visszajönne a hegytetőről, akkor legfeljebb fenn hagyhatna cipőt, de ez nem csökkentené a felhozott cipők számát ahhoz az állapothoz képest, amikor már legalább ketten tartózkodnak a konferencia helyszínén. Mivel

\begin{matrix} \frac{a_{i}}{2} + \frac{a_{j}}{2} \geq \frac{a_{1}}{2} + \frac{a_{2}}{2}, \end{matrix}

azért az (1)-es feltételt is figyelembe véve beláttuk, hogy a szükséges lábbelik minimuma nem lehet

{max}_{}^{} {\frac{a_{1} + a_{2}}{2}, \frac{a_{n}}{2}}

-nél kisebb.