Kezdőlap


Feladat:	F.2280	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1981/április, 155. oldal		PDF \| MathML
Témakör(ök):	Logikai feladatok, Feladat
Hivatkozás(ok):	Feladatok: 1980/november: F.2280

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. Tegyük föl, hogy a lift a feladat feltételei szerint mozgott, és $s$ méternyi utat tett meg. Jelölje $n_{i}$ azt, hogy a lift mozgása során hányszor tette meg az $(i - 1)$ -edik és $i$ -edik szint közötti útszakaszt $(i = 1, 2, ..., 10$ , a $0$ -dik szint a földszint). Az egyes felfelé menetek kezdő és végpontjai különbözőek voltak, így az $(i - 1)$ -edik és az $i$ -edik szint közötti útszakaszt felfelé a lift legfeljebb min. $(i,10 - (i - 1))$ alkalommal tehette meg. Figyelembe véve, hogy lefelé haladva a lift a $0$ -dik szintre nem érkezhetett, ugyanezt az útszakaszt a lift lefelé haladva a végpontok különbözősége miatt legfeljebb min. $(i - 1, 10 - (i - 1))$ alkalommal tehette meg. Mivel $i \leq 5$ esetén min $(i, 10 - (i - 1)) = i$ és min $(i - 1, 10 - (i - 1)) = i - 1$ , továbbá $i > 5$ esetén min. $(i,10 - (i - 1)) = min (i - 1, 10 - (i - 1)) = 10 - (i - 1)$ , tehát az első esetben $n_{i} \leq 2 i - 1$ , a második esetben $n_{i} \leq 2 (11 - i)$ . Emiatt

\begin{matrix} S = 4 (n_{1} + ... + n_{10}) ≦ 4 (1 + 3 + 5 + 7 + 9 + 10 + 8 + 6 + 4 + 2) = 220. \end{matrix}

Tehát a lift legfeljebb

220

méternyi utat tett meg. Ennyi utat meg is tett, ha mozgása során például a szinteken a következő sorrendben állt meg:

0

;

10

;

1

;

9

;

2

;

8

;

3

;

7

;

4

;

6

;

5

II. megoldás. Tegyük föl, hogy a lift úgy mozgott, hogy maximális utat tett meg. Ekkor minden megállás után irányt változtatott. Ha ugyanis az

i

-edik,

j

-edik szintekre egymás után, irányváltoztatás nélkül érkezett volna, akkor az

i

-edik szinten való megállást kihagyva, majd az út befejezése után ide visszatérve, az így módosított út hosszabb, mint a lift által megtett út, amiről pedig feltettük, hogy maximális.
Jelölje

m_{i}

i

-edik megállás szintjét,

i = 1,2, ...,10

. A lift által megtett út

\begin{matrix} m_{1} + (m_{1} - m_{2}) + (m_{3} - m_{2}) + (m_{3} - m_{4}) + ... + (m_{9} - m_{10}) = \\ = 2 [(m_{1} + m_{3} + m_{5} + m_{7} + m_{9}) - (m_{2} + m_{4} + ... + m_{8})] - m_{10} . \end{matrix}

Látható, hogy a megtett út akkor maximális, ha a fenti összegben a

10

9

8

7

6

szintek pozitív, a megmaradó szintek negatív előjellel szerepelnek. Mivel a kivonandók közül

m_{10}

együtthatója a legkisebb, ezért

m_{10} = 5

, vagyis a lift végül az

5

-dik szinten állt meg. A további

m_{i}

értékek ‐ a fenti megszorítás mellett ‐ tetszőlegesek lehetnek. A fenti megszorításnak eleget tevő

m_{i}

értékekhez tartozó maximális úthossz

220

Megjegyzések. 1. Mindkét megoldásból nyilvánvaló, hogy a lift nemcsak egyetlen módon teheti meg a maximális

220

m-t. Az ilyen utak száma

5! \cdot 4! = 2880

.
2. A feladat könnyen általánosítható

n

emeletes házra. Ekkor a lift maximálisan

2 n (n + 1)

méternyi utat tesz meg. (R. ZS).