 |
A B. 4281. feladat (2010. május) |
B. 4281. Valaki gondolt n darab nem feltétlenül különböző egész számra, és egy lapra felírta a belőlük képezhető összes (2n-1 darab) összeget, melyek között a 0 nem szerepelt. Meghatározhatók-e ebből az eredeti számok?
(5 pont)
A beküldési határidő 2010. június 10-én LEJÁRT.
Megoldás. A kérdésre igenlő a válasz. Ezt \(\displaystyle n\) szerinti teljes indukcióval bizonyítjuk úgy, hogy egyben rekurzí eljárást is adunk a számok meghatározására. Az \(\displaystyle 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 \(\displaystyle 2^n\) 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) \(\displaystyle 2^{n-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ó \(\displaystyle 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 \(\displaystyle n-1\) gondolt szám esetén már beláttuk, akkor aszerint a \(\displaystyle 2^{n-1}\) darab összegből a szóban forgó \(\displaystyle n-1\) szám meghatározható; ezekhez a már ismert legkisebb abszolút értékű számot hozzávéve megkapjuk mind az \(\displaystyle n\) gondolt számot.
A felírt számok közül a legkisebbet jelölje \(\displaystyle M\), a legnagyobbat \(\displaystyle N\). Ekkor \(\displaystyle M\) a gondolt számok közül a negatívak, \(\displaystyle 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 \(\displaystyle M\) vagy \(\displaystyle N\) értéke 0). A második legkisebb szám legyen \(\displaystyle M'\), a második legnagyobb \(\displaystyle N'\), ekkor \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle a\) vagy pedig \(\displaystyle -a\). A gondolt számokat jelölje \(\displaystyle x_1,\ldots,x_n\), ahol \(\displaystyle x_n\) a(z egyik) legkisebb abszolút értékű. A felírt számok között pontosan \(\displaystyle 2^{n-1}\) olyan szerepel amelynek összeadandói között \(\displaystyle x_n\) megtalálható, és ugyancsak \(\displaystyle 2^{n-1}\) olyan szerepel amelynek összeadandói között \(\displaystyle x_n\) nem található meg. Sőt, ezek párba állíthatók oly módon, hogy ha \(\displaystyle I\) az \(\displaystyle \{1,\ldots,n-1\}\) halmaz egy tetszőleges részhalmaza, akkor az \(\displaystyle s=\sum_{i\in I}x_i\) összeg párja \(\displaystyle 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 \(\displaystyle a\)-val egyenlő. Ha \(\displaystyle x_n=a\), akkor a két elem közül a kisebbik \(\displaystyle s\), a nagyobbik pedig \(\displaystyle s'\), \(\displaystyle x_n=-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 \(\displaystyle a\), akkor \(\displaystyle x_n=a\), az \(\displaystyle x_n\) elhagyásával kapott \(\displaystyle n-1\) darab számból képezhető \(\displaystyle 2^{n-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 \(\displaystyle -a\), akkor \(\displaystyle x_n=-a\), az \(\displaystyle x_n\) elhagyásával kapott \(\displaystyle n-1\) darab számból képezhető \(\displaystyle 2^{n-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 \(\displaystyle P_1=\{M,M'\}\). Hagyjuk el a \(\displaystyle 2^n\) darab felírt szám listájáról a \(\displaystyle P_1\) pár két elemét, így kapjuk a \(\displaystyle 2^n-2\) darab számból álló \(\displaystyle L_1\) listát. Ha a \(\displaystyle P_1,\ldots, P_t\) párokat és az elhagyásukkal kapott \(\displaystyle 2^n-2t\) számot tartalmazó \(\displaystyle L_t\) listát már meghatároztuk, és \(\displaystyle t<2^{n-1}\), akkor tekintsük az \(\displaystyle L_t\) lista (egyik) legkisebb elemét, legyen ez \(\displaystyle M_t\). Ennek a párja nyilván \(\displaystyle M_t+a\) kell legyen. Képezzük tehát a \(\displaystyle P_{t+1}=\{M_t,M_t+a\}\) párt, az \(\displaystyle L_t\) listáról pedig hagyjuk el az \(\displaystyle M_t,M_t+a\) számokat (mindegyiket csak egyszer), hogy megkapjuk az \(\displaystyle L_{t+1}\) listát. \(\displaystyle 2^{n-1}\) lépés után a lista kiürül, és egyben kész a keresett párosítás.
Statisztika:
17 dolgozat érkezett. 5 pontot kapott: Á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 pontot kapott: Strenner Péter, Weisz Gellért. 3 pontot kapott: 1 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2010. májusi matematika feladatai