Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4373. feladat (2011. szeptember)

B. 4373. A soklábú lények nemzetközi konferenciája az Üveghegy tetején kerül megrendezésre. A résztvevőknek rendre a1,...,an lábuk van, valamennyi pozitív páros szám. Az Üveghegy csúszós, a hegy lábánál gyülekező lények csak akkor juthatnak fel a hegyre, ha lábaik számának legalább felére speciális mászócipőt húznak. Tudván, hogy mászócipő csak lábon hordva juthat fel a hegyre és onnan vissza, legalább hány cipő szükséges a konferencia résztvevőinek a feljutáshoz?

Javasolta: Mészáros Gábor (Kemence)

(4 pont)

A beküldési határidő 2011. október 10-én LEJÁRT.


Megoldás. Ha \(\displaystyle n=1\), akkor a válasz nyilván \(\displaystyle a_1/2\), a továbbiakban tehát feltesszük, hogy \(\displaystyle n\ge 2\) és \(\displaystyle a_1\le a_2\le \ldots \le a_n\). Jelölje \(\displaystyle S_i\) az \(\displaystyle i\)-edik lényt, melynek \(\displaystyle a_i\) lába van. Ahhoz, hogy \(\displaystyle S_n\) feljuthasson a hegyre, legalább \(\displaystyle a_n/2\) cipőre szükség van. Továbbá kell legyen két olyan felmenetel, melyek között nincs lemenetel, különben mindig csak legfeljebb egy lény lehetne fent a hegyen. Ehhez pedig szükséges legalább \(\displaystyle (a_1+a_2)/2\) darab cipő. Tehát szükség van legalább \(\displaystyle \max\{(a_1+a_2)/2,a_n/2\}\) darab mászócipőre. Megmutatjuk, hogy ennyi elegendő is.

Ha \(\displaystyle n=2\), akkor \(\displaystyle S_1\) és \(\displaystyle S_2\) egyszerre fel tudnak menni a hegyre. Ha \(\displaystyle n\ge 3\), akkor pedig előtte \(\displaystyle n-2\) menetben fel tudják juttatni a többieket a következő stratégiával. Az \(\displaystyle i\)-edik menetben először is \(\displaystyle S_1\) és \(\displaystyle S_2\) felmennek a hegyre \(\displaystyle (a_1+a_2)/2\) darab cipővel. \(\displaystyle S_1\) fenn marad, \(\displaystyle S_2\) pedig lejön az összes cipővel a lábán. Mivel most az összes cipő lent van, \(\displaystyle S_{i+2}\) fel tud menni \(\displaystyle a_{i+2}/2\) cipőt használva. Ezeket, ha kell több fordulóban \(\displaystyle S_1\) le tudja vinni a hegy lábához, és kezdődhet a következő menet. Ha az összes menet lezajlott, \(\displaystyle S_3,\ldots,S_n\) fent vannak a hegyen \(\displaystyle S_1\) és \(\displaystyle S_2\) pedig a hegy alján vannak az összes cipő társaságában. Eztán már csak fel kell menniük nekik is újra a hegyre.


Statisztika:

158 dolgozat érkezett.
4 pontot kapott:70 versenyző.
3 pontot kapott:12 versenyző.
2 pontot kapott:29 versenyző.
1 pontot kapott:23 versenyző.
0 pontot kapott:24 versenyző.

A KöMaL 2011. szeptemberi matematika feladatai