Kezdőlap


Feladat:	Gy.2721	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Borbás Gergely , Bóta Ágnes , Csorba István , Dombi Gergely , Fazekas Sarolta , György András , Horváth István , Horváth Péter , Huszár Erika , Koblinger Egmont , Kóczy László , Marx Dániel , Megyesi Zoltán , Nagy Vilmos , Pizág Anett , Rákóczi Bálint , Turchányi Judit
Füzet:	1992/április, 160 - 161. oldal		PDF \| MathML
Témakör(ök):	Egész számok összege, Gyakorlat
Hivatkozás(ok):	Feladatok: 1991/október: Gy.2721

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.

Amikor egy ilyen kifejezést kiszámolunk, a végeredmény

\begin{matrix} 1 - 2 \pm 3 \pm 4 \pm ... \pm 1991 \end{matrix}

alakú lesz. Tehát a zárójelezéssel elérhető legkisebb érték

\begin{matrix} 1 - 2 - 3 - ... - 1991 = 1 - (2 + 3 + ... + 1991) = 1 - \frac{1993 \cdot 1990}{2} = - 1 983 034, \end{matrix}

a legnagyobb pedig

\begin{matrix} 1 - (2 - 3 - ... - 1991) = 1 - 2 + 3 + ... + 1991 = \frac{1991 \cdot 1992}{2} - 4 = 1 983 032. \end{matrix}

Ezek szerint legfeljebb

3 966 067

-féle eredményt kaphatunk.
Vizsgáljuk azokat a zárójelezéseket, amelyekben mindegyik zárójelen belül pontosan két tag van, s azok közül az első páros. Ilyenek például:

\begin{matrix} 1 - (2 - 3) - 4 - 5 - ...; 1 - 2 - 3 - (4 - 5) - (6 - 7) - ... stb . \end{matrix}

Számoljuk meg, hány ilyen zárójelezés van. Minden

(2 k; 2 k + 1)

párnál vagy elhelyezünk zárójelet, vagy nem. Mivel

995

ilyen pár van, ez

2^{995}

elrendezést jelent, és ezek mind különbözőek.
Ám

2^{995} > {(2^{10})}^{99} = 1024^{99} > 1000^{99} = 10^{297} > 3 966 067

, tehát már a vizsgált típusú zárójelezések között is van kettő olyan (sőt lényegesen több is), amelyek eredménye ugyanaz.

Koblinger Egmont (Fazekas M. Főv. Gyak. Gimn., I. o. t.) dolgozata alapján

Megjegyzés. Ennél egyszerűbben is be lehet bizonyítani az állítást: könnyen találhatók azonos eredményt adó zárójelezések. Például a következő kettő:

\begin{matrix} 1 - (2 - 3 - 4) - 5 - ... = 1 - 2 + 3 + 4 - 5 - ... = 1 - 2 - ... - 1991 + 2 \cdot 7, \\ 1 - 2 - 3 - 4 - 5 - (6 - 7) - ... = 1 - 2 - 3 - 4 - 5 - 6 + 7 - ... = \\ = 1 - 2 - ... - 1991 + 2 \cdot 7. \end{matrix}

Tisztázandó viszont, hogy mit értünk különböző zárójelezéseken. Minden ilyen típusú kifejezésnek van egy "természetes'' zárójelezése: ha nincs külön leírt zárójel, akkor a műveleteket balról jobbra végezzük; így az

(1 - 2) - 3

és az

1 - 2 - 3

ugyanazt a zárójelezést jelenti. Ezek alapján kézenfekvő, hogy két zárójelezést akkor tekintünk különbözőnek, ha a "fölösleges'' zárójeleket elhagyva belőlük (vagyis azokat, amelyek nem változtatják meg a műveletek balról jobbra történő végzését), eltérést mutatnak, nem ugyanott vannak bennük a zárójelek. Ezért például az

\begin{matrix} (1 - 2) - 3 - ... - 1991 = 1 - 2 - 3 - ... - 1991 \end{matrix}

ugyanaz a zárójelezés, s a feladat állítását nem bizonyítja.