KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4249. (February 2010)

B. 4249. Someone selected n not necessarily different non-negative integers. He wrote down on a sheet of paper all of the (2n-1) sums that can be formed out of the n numbers. Is it possible to determine the original numbers from this information?

(4 pont)

Deadline expired on 10 March 2010.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

>
69 students sent a solution.
4 points:Á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 points: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 points:11 students.
1 point:2 students.
0 point:3 students.
Unfair, not evaluated:3 solutions.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley