Loading [MathJax]/jax/output/SVG/jax.js

Городская олимпиада по математике среди физ-мат школ
Алматы, 2012 год


Пусть дано натуральное число n, а m — целое число из множества {0, 1, ... , n21} такое, что число xn+ynm не делится на n2 ни при каких целых x и y. Докажите, что количество таких m не меньше n(n1)2. ( М. Кунгожин )
посмотреть в олимпиаде

Комментарий/решение:

  2
3 года 10 месяца назад #

Заметим такой факт: (x+n)nxn+C1nnxn1+...+nnxn(modn2)

Это означает что xn может давать максимум n различных остатков( 0n,1n,2n,...,(n1)n). Из этого вытекает что xn+yn дают не больше n(n+1)/2 различных остатков. Очевидно что таких m не меньше n2(n+1)n/2=n(n1)/2.