A B. 4921. feladat (2018. január)

B. 4921. Bizonyítsuk be, hogy ha \(\displaystyle n\) és \(\displaystyle k\) pozitív egészek, akkor \(\displaystyle n+k\) egész szám közül mindig ki lehet választani legalább \(\displaystyle (k+1)\)-et úgy, hogy az összegük \(\displaystyle n\)-nel osztható legyen.

Javasolta: Gyenes Zoltán (Budapest)

(5 pont)

A beküldési határidő 2018. február 12-én LEJÁRT.

Megoldás. Az állítást \(\displaystyle k\)-ra vonatkozó teljes indukcióval bizonyítjuk nemnegatív egész \(\displaystyle k\)-ra és pozitív egész \(\displaystyle n\)-re. Az indukció kezdőlépéseként \(\displaystyle k=0\) mellett igazoljuk az állítást, ehhez azt kell megmutatnunk, hogy \(\displaystyle n\) egész szám közül ki lehet választani néhányat (legalább egyet) úgy, hogy a kiválasztott számok összege \(\displaystyle n\)-nel osztható legyen. Ez egy jól ismert állítás, és legkönnyebben a skatulya-elv segítségével igazolható. Legyenek ugyanis a számok \(\displaystyle a_1,a_2,\dots,a_n\), és tekintsük az \(\displaystyle s_i=a_1+a_2+\dots+a_i\) részletösszegeket, ahol \(\displaystyle 1\leq i\leq n\). Ha az \(\displaystyle s_1,s_2,\dots,s_n\) számok között van \(\displaystyle n\)-nel osztható, akkor készen is vagyunk. Ha viszont egyik sem osztható \(\displaystyle n\)-nel, akkor a skatulya-elv szerint van kettő, mondjuk \(\displaystyle s_i\) és \(\displaystyle s_j\) (ahol \(\displaystyle 1\leq i<j\leq n\)), melyek \(\displaystyle n\)-es maradéka megegyezik. Ekkor pedig \(\displaystyle s_j-s_i=a_{i+1}+a_{i+2}+\dots+a_j\) lesz megfelelő, \(\displaystyle n\)-nel osztható összeg.

Tegyük fel most, hogy valamely \(\displaystyle k\)-ra (és ezen \(\displaystyle k\) mellett minden \(\displaystyle n\)-re és minden szám-\(\displaystyle (n+k)\)-asra) már igazoltuk az állítást. Meg fogjuk mutatni, hogy \(\displaystyle (k+1)\)-re is teljesül. Legyenek tehát \(\displaystyle a_1,a_2,\dots,a_{n+k+1}\) tetszőleges egész számok. Az indukciós feltevés szerint kiválasztható közülük legalább \(\displaystyle k\), melyek összege osztható \(\displaystyle n\)-nel. (Hiszen bármelyik számot elhagyva, a maradék \(\displaystyle n+k\) szám közül is kiválasztható.) Ha az így kapott összeg legalább \(\displaystyle k+1\) tagú, akkor készen vagyunk. Ha pontosan \(\displaystyle k\) tagú az \(\displaystyle n\)-nel osztható összeg, akkor tegyük fel, hogy ez az összeg \(\displaystyle a_{n+1}+a_{n+2}+\dots+a_{n+k}\) (ez a szimmetria miatt feltehető). Az indukció kezdőlépését ismét használva az \(\displaystyle a_1,a_2,\dots,a_n\) számok közül kiválasztható néhány (de legalább egy) szám úgy, hogy az összegük \(\displaystyle n\)-nel osztható legyen. Ehhez az összeghez a \(\displaystyle k\) tagú \(\displaystyle a_{n+1}+a_{n+2}+\dots+a_{n+k}\) összeget hozzáadva egy legalább \(\displaystyle k+1\) tagú \(\displaystyle n\)-nel osztható összeget kapunk.

Ezzel a feladat állítását igazoltuk.

Statisztika:

73 dolgozat érkezett.
5 pontot kapott:	61 versenyző.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2018. januári matematika feladatai