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 file
Témakör(ök): Egész számok összege, Gyakorlat
Hivatkozás(ok):Feladatok: 1991/október: Gy.2721

Az
1-2-3-4-...-1991
kifejezésben zárójelpárok alkalmas elhelyezésével jelölhetjük ki a műveletek elvégzésének sorrendjét. Bizonyítsuk be, hogy vannak olyan zárójelezések, amelyek ugyanazt a végeredményt adják.

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

1-2±3±4±...±1991
alakú lesz. Tehát a zárójelezéssel elérhető legkisebb érték
1-2-3-...-1991=1-(2+3+...+1991)=1-199319902=-1983034,
a legnagyobb pedig
1-(2-3-...-1991)=1-2+3+...+1991=199119922-4=1983032.
Ezek szerint legfeljebb 3966067-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:
1-(2-3)-4-5-...;1-2-3-(4-5)-(6-7)-...stb.
Számoljuk meg, hány ilyen zárójelezés van. Minden (2k;2k+1) párnál vagy elhelyezünk zárójelet, vagy nem. Mivel 995 ilyen pár van, ez 2995 elrendezést jelent, és ezek mind különbözőek.
Ám 2995>(210)99=102499>100099=10297>3966067, 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ő:
1-(2-3-4)-5-...=1-2+3+4-5-...=1-2-...-1991+27,1-2-3-4-5-(6-7)-...=1-2-3-4-5-6+7-...==1-2-...-1991+27.



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
(1-2)-3-...-1991=1-2-3-...-1991
ugyanaz a zárójelezés, s a feladat állítását nem bizonyítja.