Fie multimea A formata din 2018 numere naturale. Sa se arate ca exista o submultime a lui A astfel incat suma elementelor sale sa fie divizibila cu 2018.
Răspunsuri la întrebare
Notam A={ a1,a2,….,a2018}; multimea cu 2018 elemente numere naturale
si submultimile: A1={ a1} ; A2={ a1, a2}; A3={ a1 ,a2 ,a3};....;A2018={a1,a2,….,a2018}; submultimile de 1, 2, 3,...,respectiv 2018 elemente
1. Daca suma elementelor unei astfel de submultimii este divizibila cu 2018, problema e rezolvata.
2. Daca nici o suma nu este divizibila cu 2018 => toate sumele vor da un rest la impartirea cu 2018
Restul ≠ 0 => obtinem 2017 resturi.
Fiind 2018 tipuri de sume si avand doar 2017 resturi => doua sume vor da acelasi rest la impartirea cu 2018.
Scazand suma mai mica din suma mai mare (avand acelasi rest)=> diferenta este divizibila cu 2018
Ex: fie Ai si Aj; i<j; cele doua submultimi, sumele elementelor dau resturi egale la impartirea cu 2018
=> a1+a2+….+aj-( a1+a2+….+ai)= ai+1+ ai+2 +...+ aj ; suma divizibila cu 2018
deci, exista o suma care este divizibila cu 2018.