Feladat:	B.4921	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Beke Csongor ,  Szabó Blanka
Füzet:	2018/szeptember, 347 - 348. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Oszthatóság, Skatulyaelv, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2018/január: B.4921

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Azt fogjuk bizonyítani, hogy ha $k$ természetes szám és $n$ pozitív egész szám, akkor igaz az állítás. Alkalmazzunk $k$-ra vonatkozó teljes indukciót. Tegyük fel, hogy minden természetes számra igaz az állítás $k$-ig, be kell látnunk, hogy $k+1$-re is igaz. Ha a számok $a_1\mathrm{,}{a}_2\mathrm{,}{a}_3\mathrm{,}\text{...}\mathrm{,}{a}_{n+k+1}$, akkor az indukciós feltevés alapján az $a_1\mathrm{,}{a}_2\mathrm{,}{a}_3\mathrm{,}\text{...}\mathrm{,}{a}_{n+k}$ számok közül kiválasztható $x\ge k+1$ darab, amelyeknek az összege osztható $n$-nel. Ha $x\ge k+2$, akkor az állítás igaz, ugyanezt a legalább $\left(k+1\right)+1$ darab számot ki tudjuk választani az $a_1\mathrm{,}{a}_2\mathrm{,}{a}_3\mathrm{,}\text{...}\mathrm{,}{a}_{n+k+1}$ számok közül is. Ha $x=k+1$, akkor vegyük ki a számhalmazból ezt a $k+1$ darab számot, az így megmaradó $b_1\mathrm{,}{b}_2\mathrm{,}\text{...}\mathrm{,}{b}_n$ számok közül, az indukciós feltevés miatt, szintén ki lehet választani legalább $0+1=1$ számot, úgy hogy az összegük $n$-nel osztható. Ezt a néhány számot és az előbb kivett $k+1$ számot összeadva szintén $n$-nel osztható lesz az összeg, ezért kiválasztható legalább $k+2$ darab szám. A befejezéshez már csak azt kell igazolnunk, hogy $k=0$-ra is igaz az állítás, azaz $n$ darab szám közül kiválasztható legalább $1$ darab úgy, hogy az összegük osztható $n$-nel. Ha a számok között van olyan, amelyik osztható $n$-nel, akkor vegyük ezt a számot. Ha nincs közöttük $n$-nel osztható, akkor a számokat $a_1\mathrm{,}{a}_2\mathrm{,}\text{...}\mathrm{,}{a}_n$-nel jelölve tekintsük az alábbi összegek $n$-es maradékait: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle S_1}& {\displaystyle =a_1\mathrm{,}}\hfill \\ \hfill {\displaystyle S_2}& {\displaystyle =a_1+a_2\mathrm{,}}\hfill \\ \hfill {\displaystyle S_3}& {\displaystyle =a_1+a_2+a_3\mathrm{,}}\hfill & {\displaystyle }\hfill \\ \hfill {\displaystyle ⋮}\\ \hfill {\displaystyle S_n}& {\displaystyle =a_1+a_2+\text{...}+a_n\mathrm{.}}\hfill \end{array}}$ Mivel mindegyik egész szám, és $n$-nel osztva az egész számok $n$-féle maradékot adhatnak, a skatulya elv miatt vagy van közöttük $0$ maradékot adó, vagy van legalább két azonos maradékot adó összeg. Ha előfordul a $0$ maradék, akkor találtunk néhány számot, amelyeknek az összege osztható $n$-nel. Ha pedig van legalább két azonos maradékú összeg, $S_i$ és $S_j$ ($i>j$), akkor $S_i-S_j=a_{j+1}+a_{j+2}+\text{...}+a_i$ osztható $n$-nel, ezért szintén találtunk közöttük olyan számokat, amelyeknek az összege osztható $n$-nel.    Beke Csongor (Budapest, Békásmegyeri Veres Péter Gimn., 10. évf.)  dolgozata alapján     II. megoldás. Felhasználjuk azt az ismert, és az előző megoldásban is bizonyított tényt, hogy $n$ egész szám közül mindig kiválasztható néhány úgy, hogy az összegük osztható $n$-nel. Ennek ismeretében eljárást adunk a megfelelő legalább $\left(k+1\right)$ darab egész szám megtalálására. Válasszunk ki az $n+k$ darab egész közül $n$ számot. Ebből az $n$ darab egész számból azt a néhányat, amelynek összege osztható $n$-nel, félretesszük. Ezután a megmaradó számok közül ismét kiválasztunk $n$ darabot. Ezek közül is félretesszük azokat, amelyek összege osztható $n$-nel. Ezt az eljárást addig ismételjük, amíg csak lehetséges, vagyis amint az eljárás véget ér, legfeljebb $n-1$ számot nem raktunk félre. A félretett számok száma tehát legalább $\left(k+1\right)$ és olyan csoportokban tettük félre, hogy mindegyik csoport összege osztható $n$-nel, tehát az összesnek az összege is az $n$ többszöröse. Ezzel az állítást igazoltuk.    Szabó Blanka (Debreceni Fazekas Mihály Gimn., 11. évf.)  dolgozata alapján