Problem B. 5100. (April 2020)

B. 5100. Show that it is always possible to select some numbers (at least one) out of \(\displaystyle n\) consecutive integers such that their sum is divisible by \(\displaystyle (1+2+\dots+n)\).

Based on the idea of B. Kovács and Zs. Várkonyi

(6 pont)

Deadline expired on May 11, 2020.

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

Megoldás. Felhasználjuk a következő, jól ismert tényt:

Lemma. Tetszőleges \(\displaystyle x_1,x_2,\ldots,x_k\) egészek közül kiválasztható néhány (legalább egy), amelyeknek az összege osztható \(\displaystyle k\)-val.

Bizonyítás: Tekintsük az

\(\displaystyle s=0,\quad s_1=x_1,\quad s_2=x_1+x_2, \quad s_3=x_1+x_2+x_3, \quad\ldots,\quad s_n=x_1+x_2+\ldots+x_n \)

számokat. Ez \(\displaystyle k+1\) szám; a skatulya-elv miatt van közöttük kettő, \(\displaystyle s_\ell\) és \(\displaystyle s_m\) (\(\displaystyle \ell<m\)), amely \(\displaystyle k\)-val osztva ugyananyi maradékot ad. Akkor pedig \(\displaystyle s_m-s_\ell=x_{\ell+1}+\ldots+x_m\) osztható \(\displaystyle k\)-val.

Ezután a feladat megoldását két esetre bontjuk az \(\displaystyle n\) paritása szerint.

1. eset: az \(\displaystyle n\) páratlan; \(\displaystyle n=2k-1\), és \(\displaystyle 1+2+\ldots+n=k(2k-1)\).

Minden \(\displaystyle 0\le i<(2k-1)\)-re van az \(\displaystyle n=2k-1\) szomszédos egész között egy, amely kongruens \(\displaystyle i\)-vel modulo \(\displaystyle 2k-1\); jelölje ezt a számot \(\displaystyle a_i\). Tekintsük a következő összegeket:

\(\displaystyle a_0, \quad a_1+a_{2k-2}, \quad a_2+a_{2k-3}, \quad\ldots,\quad a_{k-1}+a_k. \)

Ezek mindegyike osztható \(\displaystyle (2k-1)\)-gyel, és a Lemma szerint kiválaszthatunk közülük néhány olyat, amelynek az összege \(\displaystyle k\)-val is osztható. A kiválasztott összegek összege néhány különböző \(\displaystyle a_i\) összege, és osztható \(\displaystyle k\)-val és \(\displaystyle (2k-1)\)-gyel is. Mivel a \(\displaystyle k\) és a \(\displaystyle 2k-1\) relatív prímek, a kiválasztott \(\displaystyle a_i\) számok összege \(\displaystyle k(2k-1)\)-gyel is osztható.

2. eset: az \(\displaystyle n\) páros; \(\displaystyle n=2k\), és \(\displaystyle 1+2+\ldots+n=k(2k+1)\).

Az \(\displaystyle n=2k\) szomszédos egészhez vegyünk hozzá még egy "tiltott" számot. Az így kapott \(\displaystyle 2k+1\) szomszédos egész között minden \(\displaystyle 0\le i\le 2k\)-ra legyen \(\displaystyle a_i\) az, amelyik kongruens \(\displaystyle i\)-vel modulo \(\displaystyle 2k+1\).

Tekintsük a következő összegeket:

\(\displaystyle a_0, \quad a_1+a_{2k}, \quad a_2+a_{2k-1}, \quad\ldots,\quad a_k+a_{k+1}. \)

Ez \(\displaystyle k+1\) összeg, mindegyik osztható \(\displaystyle (2k+1)\)-gyel; az egyik összegben szerepel a tiltott szám.

A tiltott számot nem tartalmazó \(\displaystyle k\) összeg közül a Lemma szerint válasszunk ki néhányat, amelynek az összege osztható \(\displaystyle k\)-val. A kiválasztott összegek összege néhány eredeti (nem tiltott) \(\displaystyle a_i\) összege, és osztható \(\displaystyle k\)-val és \(\displaystyle (2k+1)\)-gyel is. A \(\displaystyle k\) és a \(\displaystyle 2k+1\) is relatív prímek, tehát a kiválasztott \(\displaystyle a_i\) számok összege osztható \(\displaystyle k(2k+1)\)-gyel, kész vagyunk.

Statistics:

23 students sent a solution.
6 points:	Baski Bence, Füredi Erik Benjámin, Kovács 129 Tamás, Nádor Benedek, Németh Márton, Sztranyák Gabriella.
5 points:	Bán-Szabó Áron, Hámori Janka, Kercsó-Molnár Anita, Móra Márton Barnabás.
4 points:	1 student.
3 points:	1 student.
2 points:	3 students.
1 point:	4 students.
0 point:	3 students.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, April 2020