 |
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