KöMaL - Mathematical and Physical Journal for Secondary Schools
Hungarian version Information Contest Journal Articles News
Conditions
Entry form to the contest
Problems and solutions
Results of the competition
Problems of the previous years

 

 

Order KöMaL!

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Competitions Portal

B. 4281. Someone chose n not necessarily different integers, and formed sums out of them in all (2n-1) possible ways. Given that 0 was not obtained, is it possible to determine the original numbers from the sums?

(5 points)

Deadline expired.


Google Translation (Sorry, the solution is published in Hungarian only.)

A kérdésre igenlő a válasz. Ezt n szerinti teljes indukcióval bizonyítjuk úgy, hogy egyben rekurzí eljárást is adunk a számok meghatározására. Az n=1 esetben az állítás nyilvánvaló. Az egyszerűség kedvéért írjuk fel a 0-t is a felírt összegek mellé, erre úgy gondolunk, hogy a számok közül nulla darabot adtunk össze. A felírt 2n darab szám között ily módon a 0 pontosan egyszer fog szerepelni. A módszer lényege, hogy meghatározzuk az eredeti számok közül a(z egyik) legkisebb abszolút értékű számot, és ezzel egyidejűleg azt (a 0-t is beleértve) 2n-1 darab összeget, amelyet úgy kapunk, hogy az eredeti számok közül a(z egyik) legkisebb abszolút értékűt elhagyjuk, és a fennmaradó n-1 számból képezzük az összes lehetséges összeget. Legkisebb abszolút értékű számból több is lehet ugyan a gondolt számok között, de azok biztosan egyenlők, hiszen az összegek között a feladat szerint a 0 nem szerepelt; ugyanezért a gondolt számok között a 0 eleve nem szerepelhetett. Ha tehát az állítást bármely n-1 gondolt szám esetén már beláttuk, akkor aszerint a 2n-1 darab összegből a szóban forgó n-1 szám meghatározható; ezekhez a már ismert legkisebb abszolút értékű számot hozzávéve megkapjuk mind az n gondolt számot.

[] A felírt számok közül a legkisebbet jelölje M, a legnagyobbat N. Ekkor M a gondolt számok közül a negatívak, N pedig a pozitívak összege (ha egyáltalán nincs negatív vagy pozitív a gondolt számok között, akkor annak megfelelően M vagy N értéke 0). A második legkisebb szám legyen M', a második legnagyobb N', ekkor M'-M=N-N'=a éppen a legkisebb abszolút értékű gondolt szám abszolút értéke. Valóban, ha egy felírt összegben nem szerepel az összes pozitív szám, akkor annak értéke legfeljebb N-a, és ugyanez igaz akkor is, ha az összegben szerepel az összes pozitív szám mellett legalább egy negatív is. Hasonlóképpen, ha egy felírt összegben nem szerepel az összes negatív szám, akkor annak értéke legalább M+a, és ugyanez igaz akkor is, ha az összegben szerepel az összes negatív szám mellett legalább egy pozitív is. Ezzel tehát a legkisebb abszolút értékű szám a abszolút értékét egyértelműen meghatározhatjuk.

[] Ezek után el kell döntenünk, hogy a legkisebb abszolút értékű szám a vagy pedig -a. A gondolt számokat jelölje x_1,\ldots,x_n, ahol xn a(z egyik) legkisebb abszolút értékű. A felírt számok között pontosan 2n-1 olyan szerepel amelynek összeadandói között xn megtalálható, és ugyancsak 2n-1 olyan szerepel amelynek összeadandói között xn nem található meg. Sőt, ezek párba állíthatók oly módon, hogy ha I az \{1,\ldots,n-1\} halmaz egy tetszőleges részhalmaza, akkor az s=\sum_{i\in I}x_i összeg párja s'=s+x_n=\sum_{i\in I\cup \{ n\}}x_i legyen. Egy pár két eleme között a különbség mindig a-val egyenlő. Ha xn=a, akkor a két elem közül a kisebbik s, a nagyobbik pedig s', xn=-a esetén pedig éppen fordítva. A kérdés eldöntéséhez tehát elegendő ezeket a párokat meghatároznunk. Tegyük fel ugyanis, hogy ez sikerült. Ekkor egyértelműen létezik egy olyan pár, amelynek az egyik eleme 0. Ha ennek a másik eleme a, akkor xn=a, az xn elhagyásával kapott n-1 darab számból képezhető 2n-1 darab összeget pedig úgy olvashatjuk le, hogy mindegyik párból a kisebbik elemet tekintjük. Hasonlóképpen, ha a 0-t tartalmazó pár másik eleme -a, akkor xn=-a, az xn elhagyásával kapott n-1 darab számból képezhető 2n-1 darab összeget pedig úgy olvashatjuk le, hogy mindegyik párból a nagyobbik elemet tekintjük.

[] A megoldás elején vázolt indukciós lépéshez tehát elegendő a szóban forgó párok meghatározása a felírt számok alapján. Az egyik ilyen pár nyilván P1={M,M'}. Hagyjuk el a 2n darab felírt szám listájáról a P1 pár két elemét, így kapjuk a 2n-2 darab számból álló L1 listát. Ha a P_1,\ldots, P_t párokat és az elhagyásukkal kapott 2n-2t számot tartalmazó Lt listát már meghatároztuk, és t<2n-1, akkor tekintsük az Lt lista (egyik) legkisebb elemét, legyen ez Mt. Ennek a párja nyilván Mt+a kell legyen. Képezzük tehát a Pt+1={Mt,Mt+a} párt, az Lt listáról pedig hagyjuk el az Mt,Mt+a számokat (mindegyiket csak egyszer), hogy megkapjuk az Lt+1 listát. 2n-1 lépés után a lista kiürül, és egyben kész a keresett párosítás.


Statistics on problem B. 4281.
17 students sent a solution.
5 points:Ágoston Péter, Ágoston Tamás, Bunth Gergely, Damásdi Gábor, Dudás 002 Zsolt, Éles András, Gyarmati Máté, Janzer Olivér, Mester Márton, Nagy Róbert, Perjési Gábor, Sándor Áron Endre, Weisz Ágoston.
4 points:Strenner Péter, Weisz Gellért.
3 points:1 student.
0 point:1 student.


  • Problems in Mathematics of KöMaL, May 2010

  • Our web pages are supported by: Ericsson   Google   SzerencsejátĂ©k Zrt.   Emberi ErĹ‘források MinisztĂ©riuma   Emberi ErĹ‘forrás TámogatáskezelĹ‘   OktatáskutatĂł Ă©s FejlesztĹ‘ IntĂ©zet   ELTE   Nemzeti TehetsĂ©g Program