Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5000. feladat (2019. január)

B. 5000. Adott \(\displaystyle 4999\) különböző egész szám, az egyik a \(\displaystyle 42\). Igazoljuk, hogy kiválasztható közülük néhány, amelyek összege osztható \(\displaystyle 5000\)-rel.

(4 pont)

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


Megoldás. Jelölje a számokat \(\displaystyle a_1,a_2,\dots,a_{4999}\) és tekintsük az \(\displaystyle s_1:=a_1,s_2:=a_1+a_2,\dots,s_{4999}:=a_1+a_2+\dots+a_{4999}\) összegeket. Ha ezek között szerepel 5000-zel osztható, akkor készen vagyunk. Ha az összegek közül kettő, mondjuk \(\displaystyle s_i\) és \(\displaystyle s_j\) (\(\displaystyle i<j\) mellett) ugyanannyi maradékot ad 5000-zel osztva, akkor \(\displaystyle s_j-s_i=a_{i+1}+a_{i+2}+\dots+a_j\) megfelelő, 5000-zel osztható összeg. Vagyis minden esetben készen vagyunk, kivéve, ha az \(\displaystyle s_i\) összegek 5000-es maradéka \(\displaystyle 1,2,\dots,4999\) valamilyen sorrendben, vagyis minden nemnulla maradék pontosan egyszer fordul elő. Legyen \(\displaystyle s_1':=a_2\). Az \(\displaystyle s_1',s_2,\dots,s_{4999}\) összegekkel az előző gondolatmenet megismételhető, vagyis találunk megfelelő összeget, kivéve, ha ezek között is minden nemnulla maradék pontosan egyszer fordul elő. Ha még nem vagyunk készen, akkor viszont \(\displaystyle s_1=a_1\) és \(\displaystyle s_1'=a_2\) ugyanannyi maradékot adnak 5000-zel osztva, hiszen mind \(\displaystyle s_1\), mind \(\displaystyle s_1'\) azt a nemnulla maradékot adja, ami nem szerepel a másik 4998 összeg maradéka között. Azt kaptuk tehát, hogy az állítás biztosan teljesül, ha \(\displaystyle a_1\) és \(\displaystyle a_2\) maradéka különböző. Mivel a számokat tetszőlegesen átbetűzhetjük, valójában kiderült, hogy készen vagyunk, ha nem ad mind a 4999 szám ugyanannyi maradékot. Utóbbi esetben viszont mindegyikük 42 maradékot kell adjon mod 5000, így közülük 2500-at kiválasztva megfelelő összeget kapunk (hiszen \(\displaystyle 5000\mid 42\cdot 2500\)). Ezzel a feladat állítását igazoltuk.

II. Megoldás. Legyen a számok között szereplő páros számok száma \(\displaystyle t\geq 1\). Ekkor a páratlanok száma \(\displaystyle 4999-t\), vagyis párba állítva őket képezhetünk belőlük \(\displaystyle \left[ \frac{4999-t}{2} \right]\) kéttagú összeget. Ezeket, és a páros számokat (mint egytagú összegeket) tekintve összesen \(\displaystyle t+\left[ \frac{4999-t}{2} \right]\geq t+\frac{4999-t}{2}-\frac{1}{2}=\frac{t}{2}+2499\geq 2500\) páros összeget kapunk (hiszen \(\displaystyle t\geq 1\) a feltétel szerint). Legyen \(\displaystyle b_1=2c_1,\dots,b_{2500}=2c_{2500}\) az előbbi (egy-, vagy kéttagú) páros összegek közül 2500. A \(\displaystyle c_1,c_1+c_2,\dots,c_1+c_2+\dots+c_{2500}\) összegeket tekintve az 1. Megoldásban is alkalmazott gondolatmenetet követve most azt kapjuk, hogy van néhány a \(\displaystyle c_i\) számok között, melyek összege 2500-zal osztható. A megfelelő \(\displaystyle b_i\)-k összege tehát 5000-zel osztható, és mivel ez az összeg egyben különböző \(\displaystyle a_j\)-k összegeként is előáll, ez igazolja a feladat állítását.


Statisztika:

A B. 5000. feladat értékelése még nem fejeződött be.


A KöMaL 2019. januári matematika feladatai