KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4373. (September 2011)

B. 4373. An international conference of polypodal creatures is organized on the top of the Glass Mountain. The numbers of legs of the participants, a1,...,an, all are positive even numbers. The side of the Glass Mountain is slippery. Each of the creatures gathering at the base of the mountain can only get to the top if they wear special climbing shoes on at least half their feet. At least how many shoes are needed altogether to get all participants up to the top if a shoe must always be worn on a foot when it travels up or down the mountain?

Suggested by G. Mészáros, Kemence

(4 pont)

Deadline expired on 10 October 2011.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

>
158 students sent a solution.
4 points:70 students.
3 points:12 students.
2 points:29 students.
1 point:23 students.
0 point:24 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley