Aratati ca din 35 numere naturale se pot alege 16 care sa aiba suma patratelor divizibila cu 16.

Chiar din 31 se poate

S? consider?m propozi?ia P(n): din oricare 2n-1 numere întregi putem alege n a c?ror sum? este divizibil? cu n.

Voi demonstra c? dac? P(n) ?i P(m) sunt adev?rate, atunci P(mn) este adev?rat? (pentru m,n>1).

Fie, asadar, 2mn-1 numere întregi. Cum 2mn-1>2n-1, putem alege n cu suma divizibil? cu n, deci cu media aritmetic? num?r întreg. Din cele 2mn-1-n=2m(n-1)-1 numere ramase, mai alegem n cu media aritmetica numar intreg. Putem continua astfel pana cand alegem 2m-1 grupari da cate n numere cu media aritmetica numar intreg, deoarece 2mn-1-(2m-1)n>0. Dar, din cele 2m-1, putem alege m cu suma divizibila cu m, ceea ce conduce la faptul ca exista mn numere cu suma divizibila cu mn.

In fine, cum

, e suficient sa verificam pentru n=2, adica faptul ca din orice 3 numere intregi putem alege 2 cu suma divizibila prin 2, ceea ce e evident.

EDIT: Desigur, pentru a demonstra c? P(n) e adev?rat? pentru orice n, e suficient s? demonstr?m propozi?ia pentru n prim, dar acest lucru nu e deloc banal.

A, ?i am uitat: mai întâi ridic?m cele 31 de numere la p?trat
(cum resturile modulo 16 sunt astfel mai pu?ine, putem ob?ine o estimare mai bun? decât 31).