 |
A B. 4249. feladat (2010. február) |
B. 4249. Valaki gondolt n darab nem feltétlenül különböző nemnegatív egész számra, és egy lapra felírta a belőlük képezhető összes (2n-1 darab) összeget. Meghatározhatók-e ebből az eredeti számok?
(4 pont)
A beküldési határidő 2010. március 10-én LEJÁRT.
Megoldás. A gondolt számokat jelölje nagyság szerint növekedő (nem csökkenő) sorrendben \(\displaystyle a_1, a_2, \ldots, a_n\). A lapra felírt számok közül a(z egyik) legkisebb nyilván \(\displaystyle a_1\). Tegyük fel, hogy valamely \(\displaystyle 1\le k< n\) esetén az \(\displaystyle a_1, a_2, \ldots, a_k\) számokat már meghatároztuk. Ekkor \(\displaystyle a_{k+1}\) is meghatározható a következő módon. Készítsük el az \(\displaystyle a_1, a_2, \ldots, a_k\) számokból képezhető összes összeget (ezek között azonosak is lehetnek). A lapra felírt számok közül húzzuk ki ezt a \(\displaystyle 2^k-1\) darab számot. A megmaradt \(\displaystyle 2^n-2^k\) szám mindegyike egy olyan összeg, amelynek valamelyik összeadandója \(\displaystyle a_{k+1},\ldots,a_n\) közül kerül ki. Ezért ezek közül a legkisebb éppen \(\displaystyle a_{k+1}\) lesz. A teljes indukció elve szerint tehát az \(\displaystyle a_1, a_2, \ldots, a_n\) számok meghatározhatók, és a fenti indoklás erre egy algoritmust is szolgáltat.
Statisztika:
69 dolgozat érkezett. 4 pontot kapott: Ágoston Péter, Ágoston Tamás, Barczel Nikolett, Beke Lilla, Böőr Katalin, Bősze Zsuzsanna, Bunth Gergely, Cséke Balázs, Csuka Róbert, Damásdi Gábor, Éles András, Énekes Péter, Gyarmati Máté, Hajdók Soma, Havasi 0 Márton, Janzer Olivér, Jernei Tamás, Karkus Zsuzsa, Karl Erik Holter, Keresztfalvi Tibor, Kiss 902 Melinda Flóra, Kiss 991 Mátyás, Korondi Zénó, Márkus Bence, Mester Márton, Mészáros András, Perjési Gábor, Sándor Áron Endre, Somogyi Ákos, Szabó 928 Attila, Tossenberger Tamás, Varga Vajk, Weisz Ágoston, Weisz Gellért, Zsakó András. 3 pontot kapott: Dolgos Tamás, Dudás 002 Zsolt, Hajnal Máté, Herczeg József, Kószó Simon, Kovács 235 Gábor, Kovács 444 Áron, Kovács 888 Adrienn, Köpenczei Gergő, Nagy Róbert, Solti Bálint, Tekeli Tamás, Tóth 222 Barnabás, Veres Andrea, Zelena Réka. 2 pontot kapott: 11 versenyző. 1 pontot kapott: 2 versenyző. 0 pontot kapott: 3 versenyző. Nem versenyszerű: 3 dolgozat.
A KöMaL 2010. februári matematika feladatai