Problem B. 4921. (January 2018)

B. 4921. Let \(\displaystyle n\) and \(\displaystyle k\) denote positive integers. Prove that given \(\displaystyle n+k\) integers it is always possible to select at least \(\displaystyle (k+1)\) numbers out of them such that their sum is divisible by \(\displaystyle n\).

Proposed by Z. Gyenes, Budapest

(5 pont)

Deadline expired on February 12, 2018.

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

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.

Statistics:

73 students sent a solution.
5 points:	61 students.
4 points:	2 students.
3 points:	1 student.
2 points:	5 students.
1 point:	3 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, January 2018