Problem B. 4055. (January 2008)
B. 4055. Prove that every number not greater than n! can be expressed as a sum of at most n different factors of the number n!.
(5 pont)
Deadline expired on February 15, 2008.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás: Az állítás n=1-re nyilván igaz. A teljes indukciós bizonyításhoz tegyük fel, hogy n2, és az állítást n helyett n-1 esetére már igazoltuk. Legyen 1kn!. Ha kn, akkor , vagyis egy darab osztó összegeként előáll. Feltehetjük tehát, hogy n+1kn!. Legyen k=nq+r, ahol 0rn-1 és 1q(n-1)!. Az indukciós feltevés miatt , ahol tn-1 és az (n-1)! különböző osztói. Ekkor
ahol az n! különböző osztói. Ezzel r=0 esetén a k számot az n! legfeljebb n-1 darab különböző osztójának összegeként írtuk fel, 1rn-1 esetén pedig legfeljebb n darab különböző osztó összegeként, hiszen r nem egyezhet meg egyik ndi számmal sem, lévén r<nndi.
Statistics:
50 students sent a solution. 5 points: Ágoston Tamás, Bálint Dániel, Bencs 111 Ferenc, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Csere Kálmán, Dinh Hoangthanh Attila, Dudás 002 Zsolt, Éles András, Énekes Péter, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gőgös Balázs, Grósz Dániel, Kalina Kende, Keresztfalvi Tibor, Kiss 243 Réka, Kovács 729 Gergely, Lajos Mátyás, Lovas Lia Izabella, Márki Róbert, Márkus Bence, Mészáros András, Misnyovszki Péter, Nagy 648 Donát, Nagy-Baló András, Németh Bence, Palincza Richárd, Somogyi Ákos, Szabó 895 Dávid, Szalkai Balázs, Szepesvári Dávid, Szigetvári Áron, Szőke Nóra, Tossenberger Anna, Tóth 369 László Márton, Tubak Dániel, Varga 171 László, Véges Márton, Wang Daqian, Zieger Milán. 4 points: Kovács 999 Noémi, Tóth 222 Barnabás. 1 point: 4 students. 0 point: 1 student.
Problems in Mathematics of KöMaL, January 2008