Математикадан Алматы қаласының олимпиадасы, 2012 жыл

$n$ қандай да бір берілген натурал сан, ал $\{0,1,\ldots,{{n}^{2}}-1\}$ жиынындағы $m$ саны, қандай да болмасын бүтін $x$ және $y$ сандары үшін ${{x}^{n}}+{{y}^{n}}-m$ саны ${{n}^{2}}$-қа бөлінбейтін сан болсын. Осы шартты қанағаттандыратын $m$ санының саны $\dfrac{n(n-1)}{2}$-ден кем емес екенін дәлелде. ( М. Кунгожин )

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

Заметим такой факт: $(x+n)^n \equiv x^n+C_{n}^1 n x^{n-1}+...+n^n \equiv x^n (mod n^2)$

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