Делимост на 197

[pal702004]

Да се докаже, че всяко множество от $100$ цели числа съдържа поне две числа, сбора или разликата на които се дели на $197$.

[math10.com]

Много готина задача и се решава на няколко реда

Лесно се съобразява че 100-те числа трябва да имат различни остатъци при делена на 197.Ако 2 от тях са с едналъв остатък то разликата им се дели на 197.Тогава разглеждаме 100-те остатъка при делене на 197 измежду множеството [tex]A=[/tex]{-98, -97, -96,.....,-1,0,1,.....,96,97,98}.Сега по пинципа на Дирихле ще имаме поне 2 числа с еднаква абсолютна стойност, откъдето сборът им ще се дели на 197.

[Евва]

Числата трябва ли да бъдат последователни ?

[pal702004]

Числата трябва ли да бъдат последователни ?

Не. Могат даже да са еднакви (ама няма да е добре)

[Tilko]

Да разгледаме множеството от 100 цели числа. Това множество може да бъде описано като:
S = {a1, a2, ..., a100}
Където ai е цяло число за i = 1, 2, ..., 100.
Нека сега разгледаме всички остатъци при деление на 197. Те са точно 197 на брой и можем да ги означим с:
R = {0, 1, 2, ..., 196}
Нека функцията f(x) означава остатъка при деление на 197 на дадено цяло число x.
Тоест, ако разделим x на 197 и получим остатъка r, то f(x) = r. Така f: Z → R е функцията, която дава остатъка при деление на цяло число на 197.
Сега можем да разгледаме следните 100+1 числа:
f(a1), f(a2), ..., f(a100), f(197)
Тези числа са елементи на множеството R. Понеже имаме 197 различни възможни остатъка, но само 100+1 числа,
то по принцип на Дирихле поне две от тези числа ще имат един и същи остатък при деление на 197.
Тоест, ще съществуват такива i и j, за които:
f(ai) ≡ f(aj) (mod 197)
и следователно:
f(ai) - f(aj) ≡ 0 (mod 197)
или
f(ai) + f(aj) ≡ 0 (mod 197)
Това означава, че разликата или сумата на ai и aj ще бъде кратна на 197.
Следователно, множеството от 100 числа съдържа поне две числа,
чиято сума или разлика се дели на 197.