A B. 5100. feladat (2020. április)

B. 5100. Mutassuk meg, hogy \(\displaystyle n\) szomszédos egész szám közül mindig kiválasztható néhány (legalább egy), melynek összege osztható \(\displaystyle (1+2+\ldots+n)\)-nel.

(6 pont)

Kovács Benedek és Várkonyi Zsombor ötletéből

(6 pont)

A beküldési határidő 2020. május 11-én LEJÁRT.

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.

Statisztika:

23 dolgozat érkezett.
6 pontot kapott:	Baski Bence, Füredi Erik Benjámin, Kovács 129 Tamás, Nádor Benedek, Németh Márton, Sztranyák Gabriella.
5 pontot kapott:	Bán-Szabó Áron, Hámori Janka, Kercsó-Molnár Anita, Móra Márton Barnabás.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	4 versenyző.
0 pontot kapott:	3 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2020. áprilisi matematika feladatai